언제나 휴일

[C언어 알고리즘] 5.1.1 인접 행렬로 방향성 없는 그래프 소스 코드//방향성 없는 그래프 #include #include #include typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 }Graph; Graph *MakeGraph();//그래프 만들기 void ViewNeighbors(Graph *g);//이웃 정점 보여주기 void DeleteGraph(Graph *graph);//그래프 소멸 int main(void) { Graph *graph; graph = MakeGraph();//그래프 만들기 ViewNeighbors(graph); //이웃 정점 보여주기 DeleteGRaph(graph);//그래프 소멸 return ..

7.2 인접 행렬로 방향성 없는그래프 소스 코드 //Program.c //방향성 없는 그래프 #include #include #include typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 }Graph; Graph *MakeGraph();//그래프 만들기 void ViewNeighbors(Graph *g);//이웃 정점 보여주기 void DeleteGraph(Graph *graph);//그래프 소멸 int main(void) { Graph *graph; graph = MakeGraph();//그래프 만들기 ViewNeighbors(graph); //이웃 정점 보여주기 DeleteGRaph(graph);//그래프 소멸 return 0..

7.1 인접 행렬로 방향성 없는그래프방향성 없는 그래프는 정점 A에서 정점 B로 이동할 수 있으면 언제나 정정 B에서 정정 B로 이동할 수 있음을 보장하는 그래프예요. 방향성 없는 그래프를 표현하는 방법 중에 간단한 그래프에는 인접 행렬을 많이 사용해요. 인접 행렬로 방향성 없는 그래프를 표현하면 좌상단에서 우하단으로 이어지는 대각선에 대칭 형태죠. 먼저 그래프 형식을 정의하기로 해요. 인접 행렬로 그래프를 표현할 때 그래프에는 정점 개수와 인접 행렬이 필요하겠죠. typedef struct{//그래프 형식 정의 int vn; //정점 개수 int **matrix;//그래프 인접 행렬 }Graph; 여기에서는 그래프 생성, 소멸, 간선 추가, 이웃 정점을 보여주는 기능을 제공하기로 해요. Graph *M..

10.3.3 깊이 우선 탐색(인접 행렬) 코드 다음은 앞에서 작성한 인접 행렬로 구현한 그래프와 이를 이용한 깊이 우선 탐색 소스 코드입니다. 여기에서는 방향성 없는 그래프를 소개할게요. //Graph.h#pragma once#include #include using namespace std;typedef vector Neighbors;class Graph{ const int vn;//정점의 개수 int **matrix;//인접 행렬 public: Graph(int vn); ~Graph(void); void AddEdge(int start, int goal);//간선 추가 void ViewNeighbors()const; void ViewNeighbor(int vt)const; Neighbors FindN..

10.3.2 깊이 우선 탐색(인접 행렬) 구현 이번에는 인접행렬로 구현한 그래프를 이용하여 깊이 우선 탐색 알고리즘을 구현해 봅시다. 깊이 우선 탐색은 한 정점에서 갈 수 있는 이웃 정점으로 이동한 후에 다시 이웃 정점으로 이동하는 것을 반복합니다. 단 이미 방문한 정점은 방문하지 않으면서 목적지까지 경로를 찾는 알고리즘입니다. 그런데 깊이 우선 탐색에서 이동하다가 더 이상 갈 곳이 없으면 이전 갈림길에서 다른 길을 선택할 수 있어야 합니다. 이를 위해 현재까지 이동한 경로를 경험 정보로 관리하고 한 정점에서 갈 수 있는 이웃 정점을 추가한 다음 경험 정보를 스택에 보관해 두었다가 더 이상 갈 곳이 없으면 스택에서 꺼내와서 다른 경로를 찾게 구현할 거예요. 다음은 스택을 이용한 깊이 우선 탐색 알고리즘의..

10.3 인접 행렬을 이용한 깊이 우선 탐색 깊이 우선 탐색(Depth First Search)은 그래프의 한 정점에서 다른 정점으로 갈 수 있는 경로를 찾는 방법 중에 하나입니다. 하나의 정점에서 갈 수 있는 이웃 정점을 방문하고 다시 방문한 정점에서 이웃 정점을 방문하면서 원하는 목적 지점까지 방문하는 방법이예요. 이 때 방문했었던 정점을 다시 방문하지 말아야 합니다. 깊이 우선 탐색처럼 그래프에서 어떠한 문제를 해결하기 위해서는 그래프를 먼저 표현할 수 있어야 합니다. 정점의 개수가 비교적 적을 때는 인접행렬로 표현할 수 있습니다. 만약 정점의 개수가 많다면 인접 행렬은 이웃하지 않는 간선을 위한 영역도 포함하여 메모리 및 성능이 나빠집니다. 이럴 때는 정점과 간선의 집합으로 그래프를 표현하여 문제..