1. 쾨니히스베르크의 문제를 해결하기 위해 그래프 이론이 등장
- 모든 다리를 한 번씩만 건너서 처음 출발했던 장소로 돌아올 수 있는가
- 필요충분 조건 - 정점 (vertex) 별로 연결된 간선 (edge) 의 수가 모두 짝수이어야한다
2. 그래프의 이해와 종류
- 무방향 그래프 - 방향성이 없는 그래프
- 방향 그래프
- 완전 그래프
3. 가중치 그래프 (Weight Graph) 와 부분 그래프 (Sub Graph)
- 가중치 그래프 - 간선에 가중치 정보를 둔 그래프. 두 정점 사이의 거리라던가 두 정점을 이동하는데 걸리는 시간과 같은 정보가 가중치가 될 수 있다.
- 부분 그래프 - 부분 그래프는 원 그래프의 일부 정점 및 간선으로 이뤄진 그래프
4. 그래프의 집합 표현
- 그래프는 정점과 간선의 집합
- 그래프 자료구조의 ADT
|
1
2
3
4
5
6
7
8
9
|
void GraphInit(UALGraph * pg, int nv);
//그래프의 초기화를 진행한다
//두 번째 인자로 정점의 수를 전달한다
void GraphDestroy(UALGraph * pg);
//그래프 초기화 과정에서 할당한 리소스를 반환한다
void AddEdge(UALGraph * pg, int fromV, int toV);
//매개변수 fromV와 toV로 전달된 정점을 연결하는 간선을 그래프에 추가한다
void ShowGraphEdgeInfo(UALGraph * pg);
//그래프의 간선정보를 출력한다
|
cs |
- 그래프를 구현하는 두 가지 방법
- 인접 행렬 기반 그래프 - 정방 행렬을 활용
- 인접 리스트 기반 그래프 - 연결 리스트를 활용
- 인접 리스트 기반 헤더 파일 정의 및 구현 - 무방향 그래프 (방향 그래프보다 좀 더 복잡)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
//"ALGraph.h"
#ifndef __AL_GRAPH__
#define __AL_GRAPH__
#include "DLinkedList.h" //연결리스트를 가져다 쓴다
//정점의 이름을 상수화
enum {A, B, C, D, E, F, G, H, I, J};
typedef struct _ual
{
int numV; // 정점의 수
int numE; // 간선의 수
List * adjList; // 간선의 정보
} ALGraph;
//그래프의 초기화
void GraphInit(ALGraph * pg, int nv);
//그래프의 리소스 해제
void GraphDestroy(ALGraph * pg);
//간선의 추가
void AddEdge(ALGraph * pg, int fromV, int toV);
//간선의 정보 출력
void ShowGraphEdgeInfo(ALGraph * pg);
#endif
//"ALGraphMain.c"
#include <stdio.h>
#include "ALGraph.h"
int main(void)
{
ALGraph graph; // 그래프의 생성
GraphInit(&graph, 5); // 그래프의 초기화, 5개의 정점을 생성
AddEdge(&graph, A, B); // 정점 A와 B를 연결
AddEdge(&graph, A, D); // 정점 A와 D를 연결
ShowGraphEdgeInfo(&graph); // 그래프의 간선정보 출력
GraphDestroy(&graph); // 그래프의 리소스 소멸
return 0;
}
//"ALGraph.c"
void GraphInit(ALGraph * pg, int nv)
{
int i;
//정점의 수에 해당하는 길이의 리스트 배열을 생성한다
pg->adjList = (List*)malloc(sizeof(List)*nv); //간선정보를 저장할 리스트 생성
pg->numV = nv; // 정점의 수는 nv에 저장된 값으로 결정
pg->numE = 0; // 초기 간선의 수는 0개
//정점의 수만큼 생성된 리스트들을 초기화한다
for(i=0; i<nv; i++)
{
ListInit(&(pg->adjList[i]));
}
}
void GraphDestroy(ALGraph * pg)
{
//그래프 리소스의 해제
if(pg->adjList != NULL)
free(pg->adjList); //동적으로 할당된 연결 리스트의 소멸
}
void AddEdge(ALGraph * pg, int fromV, int toV) //fromV, toV 연결하는 간선 추가
{
// 무방향 그래프 이므로 두번 호출
//정점 fromV의 연결 리스트에 정점 toV의 정보 추가
LInsert(&(pg->adjList[fromV]), toV);
//정점 toV의 연결 리스트에 정점 fromV의 정보 추가
LInsert(&(pg->adjList[toV]), fromV);
pg->numE += 1;
}
void ShowGraphEdgeInfo(ALGraph * pg)
{
int i;
int vx;
for(i=0; i<pg->numV; i++)
{
printf("%c와 연결된 정점: ", i+65);
if(LFirst(&(pg->adjList[i]), &vx))
{
printf("%c ", vx + 65);
while(LNext(&(pg->adjList[i]), &vx)
printf("%c ", vx + 65);
}
printf("\n");
}
}
|
cs |
5. 그래프의 탐색
- 모든 정점을 돌아다니려면 어떻게 해야겠는가?
- 2가지 알고리즘
- 깊이 우선 탐색 Depth First Search: DFS
- 너비 우선 탐색 Breadth First Search: BFS
- DFS의 핵심 세가지
- 한 사람에게만 연락을 한다
- 연락할 사람이 없으면, 자신에게 연락한 사람에게 이를 알린다
- 처음 연락을 시작한 사람의 위치에서 연락은 끝이 난다
- BFS의 핵심
- 너비는 "한 사람을 기준으로 메세지를 전달하는 사람의 수(폭)" 으로 볼 수 있다
- 한 사람을 기준으로 자신에게 연결된 모든 사람에게 메시지를 전달하는 방식
6. 깊이 우선 탐색의 구현 모델
- DFS의 구현을 위해서 필요한 것 두가지
- 스택 - 경로 정보의 추적을 목적으로 한다 (방문한 정점을 떠날 때에는 떠나는 정점의 정보를 스택에 쌓는다)
- 배열 - 방문 정보의 기록을 목적으로 한다 (방문한 정점은 방문한 상태로 표시해 놓는다)
- DFS 구현에 필요한 파일 및 구현
- ALGraphDFS.h, ALGraphDFS.c - 그래프 관련
- ArrayBaseStack.h, ArrayBaseStack.c - 스택 관련
- DLinkedList.h, DLinkedList.c - 연결 리스트 관련
- DFSMain.c - main 함수 관련
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172//"ALGraphDFS.h"#ifndef __AL_GRAPH_DFS__#define __AL_GRAPH_DFS__#include "DLinkedList.h" //연결리스트를 가져다 쓴다//정점의 이름을 상수화enum {A, B, C, D, E, F, G, H, I, J};typedef struct _ual{int numV; // 정점의 수int numE; // 간선의 수List * adjList; // 간선의 정보int * visitInfo; // 탐색이 진행된 정점의 정보를 담기 위함} ALGraph;//그래프의 초기화void GraphInit(ALGraph * pg, int nv);//그래프의 리소스 해제void GraphDestroy(ALGraph * pg);//간선의 추가void AddEdge(ALGraph * pg, int fromV, int toV);//간선의 정보 출력void ShowGraphEdgeInfo(ALGraph * pg);//정점의 정보 출력 : DFS 기반void DFShowGraphVertex(ALGraph * pg, int startV);#endif//"ALGraphMain.c"#include <stdio.h>#include "ALGraph.h"int main(void){ALGraph graph; // 그래프의 생성GraphInit(&graph, 5); // 그래프의 초기화, 5개의 정점을 생성AddEdge(&graph, A, B); // 정점 A와 B를 연결AddEdge(&graph, A, D); // 정점 A와 D를 연결ShowGraphEdgeInfo(&graph); // 그래프의 간선정보 출력GraphDestroy(&graph); // 그래프의 리소스 소멸return 0;}//"ALGraphDFS.c"void GraphInit(ALGraph * pg, int nv){int i;//정점의 수에 해당하는 길이의 리스트 배열을 생성한다pg->adjList = (List*)malloc(sizeof(List)*nv); //간선정보를 저장할 리스트 생성pg->visitInfo = (int*)malloc(sizeof(int) * pg->numV); //정점의 수를 길이로 하여 배열을 할당memset(pg->visitInfo, 0, sizeof(int) * pg->numV); //배열의 모든 요소를 0으로 초기화pg->numV = nv; // 정점의 수는 nv에 저장된 값으로 결정pg->numE = 0; // 초기 간선의 수는 0개//정점의 수만큼 생성된 리스트들을 초기화한다for(i=0; i<nv; i++){ListInit(&(pg->adjList[i]));}}void GraphDestroy(ALGraph * pg){//그래프 리소스의 해제if(pg->adjList != NULL)free(pg->adjList); //동적으로 할당된 연결 리스트의 소멸//배열 리소스 해제if(pg->visitInfo != NULL)free(pg->visitInfo)}void AddEdge(ALGraph * pg, int fromV, int toV) //fromV, toV 연결하는 간선 추가{// 무방향 그래프 이므로 두번 호출//정점 fromV의 연결 리스트에 정점 toV의 정보 추가LInsert(&(pg->adjList[fromV]), toV);//정점 toV의 연결 리스트에 정점 fromV의 정보 추가LInsert(&(pg->adjList[toV]), fromV);pg->numE += 1;}void ShowGraphEdgeInfo(ALGraph * pg){int i;int vx;for(i=0; i<pg->numV; i++){printf("%c와 연결된 정점: ", i+65);if(LFirst(&(pg->adjList[i]), &vx)){printf("%c ", vx + 65);while(LNext(&(pg->adjList[i]), &vx)printf("%c ", vx + 65);}printf("\n");}}//DFShowGraphVertex에서 쓰일 함수// 두 번째 매개변수로 전달된 이름의 정점에 방문int VisitVertex(ALGraph * pg, int visitV){if(pg->visitInfo[visitV] == 0) //visitV에 처음 방문일 때 참인 if문{pg->visitInfo[visitV] = 1; // visitV에 방문한 것으로 기록printf("%c ", visitV + 65); // 방문한 정점의 이름을 출력return TRUE; // 방문 성공}return FALSE; // 방문 실패}// DFS 기반으로 정의된 함수: 정점의 정보 출력void DFShowGraphVertex(ALGraph * pg, int startV){Stack stack;int visitV = startV;int nextV;StackInit(&stack); //DFS를 위한 스택의 초기화VisitVertext(pg, visitV); //시작 정점을 방문SPush(&stack, visitV); //시작 정점의 정보를 스택으로!// visitV에 담긴 정점과 연결된 정점의 방문을 시도하는 while 문while(LFirst(&(pg->adjList[visitV]), &nextV)== TRUE)// LFirst 를 통해서 visitV에 연결된 정점 하나를 얻는다.// 이렇게 해서 얻은 정점의 정보는 nextV에 저장된다.{// visitV와 연결된 정점의 정보가 nextV에 담긴 상태에서 이하를 진행int visitFlag = FALSE;// nextV에 담긴 정점의 정보를 가지고 방문을 시도한다.if(VisitVertex(pg, nextV)== TRUE) // 방문에 성공했다면{// 방문 성공했으니 visitV의 정보는 스택에 푸쉬SPush(&stack, visitV); // visitV 담긴 내용을 PUSH// nextV에 담긴 정보를. visitV 에 담고 다시 반복문// 반복문을 다시 시작하는 것은 또 다른 정점의 방문을 시도하는 것 !visitV = nextV;visitFlag = TRUE;}// LFirst 함수를 통해서 얻은 정점의 방문에 실패한 경우 이하 실행else // 방문 실패하면 연결된 다른 정점들을 찾는다.{//아래의 반목은 visitV에 연결된 정점을 찾을 때 까지 반복된다.while(LNext(&(pg->adjList[visitV]), &nextV)== TRUE){//LNext 함수의 호출을 통해서 visitV에 연결된 정점 하나를 얻는다.// 이렇게 얻은 정점의 정보는 nextV에 저장된다.// 이 정보를 바탕으로 방문을 시도한다.if(VisitVertex(pg, nextV) == TRUE){SPush(&stack, visitV); // 방문 성공했으니 푸쉬visitV = nextV;visitFlag = TRUE;break;}}}// 정점 방문에 실패했다면 그에 따른 처리를 진행한다.if(visitFlag == FALSE) // 추가로 방문한 정점이 없었다면{// 길을 되돌아 가거나 시작 위치로 되돌아와서 프로그램을 종료하거나 ~!if(SIsEmpty(&stack)== TRUE) // 시작점으로 되돌아 왔음break;elsevisitV = SPop(&stack); // 길을 되돌아간다}}// 이후의 탐색을 위해서 탐색 정보 초기화memset(pg->visitInfo, 0, sizeof(int)*pg->numV);}cs
7. 너비 우선 탐색의 구현 모델
- BFS의 구현을 위해서 필요한 것 두가지
- 큐 - 방문 차례의 기록을 목적으로 한다, 연락을 취할 정점의 순서를 기록하기 위한 것
- 배열 - 방문 정보의 기록을 목적으로 한다
- BFS 구현에 필요한 파일 및 구현
- ALGraphBFS.h, ALGraphBFS.c - 그래프 관련
- CircularQueue.h, CircularQueue.c - 큐 관련
- DLinkedList.h, DLinkedList.c - 연결 리스트 관련
- BFSMain.c - main 함수 관련
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778//"ALGraphBFS.h"#ifndef __AL_GRAPH_BFS__#define __AL_GRAPH_BFS__#include "DLinkedList.h" //연결리스트를 가져다 쓴다//정점의 이름을 상수화enum {A, B, C, D, E, F, G, H, I, J};typedef struct _ual{int numV; // 정점의 수int numE; // 간선의 수List * adjList; // 간선의 정보int * visitInfo; // 탐색이 진행된 정점의 정보를 담기 위함} ALGraph;//그래프의 초기화void GraphInit(ALGraph * pg, int nv);//그래프의 리소스 해제void GraphDestroy(ALGraph * pg);//간선의 추가void AddEdge(ALGraph * pg, int fromV, int toV);//간선의 정보 출력void ShowGraphEdgeInfo(ALGraph * pg);//정점의 정보 출력 : BFS 기반void BFShowGraphVertex(ALGraph * pg, int startV);#endif//"ALGraphMain.c"#include <stdio.h>#include "ALGraph.h"int main(void){ALGraph graph; // 그래프의 생성GraphInit(&graph, 5); // 그래프의 초기화, 5개의 정점을 생성AddEdge(&graph, A, B); // 정점 A와 B를 연결AddEdge(&graph, A, D); // 정점 A와 D를 연결ShowGraphEdgeInfo(&graph); // 그래프의 간선정보 출력GraphDestroy(&graph); // 그래프의 리소스 소멸return 0;}//"ALGraphBFS.c"// ... 이하 동일 with ALGraphDFS.c// BFS 기반으로 정의된 함수: 정점의 정보 출력void BFShowGraphVertex(ALGraph * pg, int startV){Queue queue;int visitV = startV;int nextV;QueueInit(&queue); //BFS를 위한 큐의 초기화VisitVertext(pg, visitV); //시작 정점을 탐색한다// 아래의 while문에서는 visitV와 연결된 모든 정점에 방문한다while(LFirst(&(pg->adjList[visitV]), &nextV) == TRUE){if(VisitVertex(pg, nextV)==TRUE)Enqueue(&queue, nextV); // nextV에 방문했으니 큐에 저장while (LNext(&(pg->adjList[visitV]), &nextV)==TRUE){if(VisitVertex(pg, nextV)==TRUE)Enqueue(&queue, nextV); // nextV에 방문했으니 큐에 저장}if(QIsEmpty(&queue) == TRUE) // 큐가 비었다~ 종료 !break;elsevisitV = Dequeue(&queue); // 큐에서 하나 꺼내서 다시 반복문 시작!~}memset(pg->visitInfo, 0, sizeof(int)*pg->numV); // 탐색 정보 초기화}cs 8. 최소비용 신장트리 (Spanning Tree)
- 단순 경로 : 간선을 중복하여 포함하지 않는 경로
- 사이클 : 단순 경로이면서 시작과 끝이 같은 경로
- 신장 트리 : 어떻게 경로를 구성하더라도 사이클을 형성하지 않는 그래프 / 그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있다 / 그래프 내에서 사이클을 형성하지 않는다
- 최소 비용 신장 트리의 이해와 적용
- 가중치 그래프를 대상으로도, 간선에 방향성이 부여된 방향 그래프를 대상으로도 신장 트리를 구성할 수 있다
- 신장 트리의 모든 간선의 가중치 합이 최소인 그래프를 가리켜 '최소 비용 신장 트리' 또는 '최소 신장 트리'라 한다
- 최소 비용 신장 트리의 구성을 위한 크루스칼 알고리즘1
- 가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 또는 삭제해 나가는 방식
- 오름차순 정렬 방법
- 가중치를 기준으로 간선을 오름차순으로 정렬한다
- 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가한다
- 사이클을 형성하는 간선은 추가하지 않는다
- 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성된다. (간선의 수 + 1 = 정점의 수)
- 내림차순 정렬 방법
- 높은 가중치의 간선을 하나씩 빼는 방법으로 알고리즘이 전개된다
- 두 정점이 다른 경로를 통해서도 연결되어 있는 경우에만 해당 간선을 삭제할 수 있다
- 간선의 수가 정점의 수보다 하나 적을 때 MST는 완성된다
- 내림차순으로 간선을 제거해 나가는 크루스칼 알고리즘 구현
- DLinkedList.h, DLinkedList.c - 연결 리스트
- ArrayBaseStack.h, ArrayBaseStack.c - 배열 기반 스택
- ALGraphDFS.h, ALGraphDFS.c - 깊이 우선 탐색을 포함하는 그래프
- ALGraphKruskal.h, ALGraphKruskal.c - 크루스칼 알고리즘 기반의 그래프
- PriorityQueue.h, PriorityQueue.c - 우선순위 큐
- UsefulHeap.h, UsefulHeap.c - 우선순위 큐의 기반이 되는 힙
- ALEdge.h - 가중치가 포함된 간선의 표현을 위한 구조체
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245//"ALEdge.h" - "간선의 가중치 정보 저장"#ifndef ALEdge_h#define ALEdge_htypedef struct _edge{int v1; // 간선이 연결하는 첫 번째 정점int v2; // 간선이 연결하는 두 번째 정점int weight; // 간선의 가중치}Edge;#endif//"ALGraphKruskal.h"#ifndef ALGraphKruskal_h#define ALGraphKruskal_h#include "PriorityQueue.h"#include "DLinkedList.h"#include "ALEdge.h"// 정점의 이름 상수화enum {A,B,C,D,E,F,G,H,I,J};typedef struct _ual{int numV; // 정점의 수int numE; // 간선의 수List * adjList; // 간선의 정보int * visitInfo;PQueue pqueue; // 간선의 가중치 정보 저장}ALGraph;//그래프의 초기화void GraphInit(ALGraph * pg , int nv);//그래프의 리소스 해제void GraphDestroy(ALGraph * pg);//간선의 추가void AddEdge(ALGraph * pg, int fromV, int toV,int weight);// 간선의 정보 출력void ShowGraphEdgeInfo(ALGraph * pg);// 정점의 정보 출력 : DFS 기반void DFShowGraphVertex(ALGraph * pg, int startV);// 새로운 함수void ConKruskalMST(ALGraph * pg); // 최소 비용 신장 트리의 구성//새로운 함수void ShowGraphEdgeWeightInfo(ALGraph * pg); // 가중치 정보 출력#endif//"ALGraphKruskal.c"int PQWeightComp(Edge d1, Edge d2){return d1.weight - d2.weight;}void GraphInit(ALGraph * pg, int nv) // 그래프의 초기화{int i;// 정점의 수에 해당하는 길이의 리스트 배열을 생성하낟.pg->adjList = (List*)malloc(sizeof(List)*nv); // 간선정보를 저장할 리스트 생성pg->visitInfo = (int*)malloc(sizeof(int)*pg->numV); // 정점의 수를 길이로 하여 배열을 할당pg->numV = nv; // 정점의 수는 nv에 저장된 값으로 결정pg->numE=0;// 초기의 간선수는 0개memset(pg->visitInfo,0,sizeof(int)*pg->numV);// 정점의 수만큼 생성된 리스트들을 초기화한다.for(i=0;i<nv;i++){ListInit(&(pg->adjList[i]));SetSortRule(&(pg->adjList[i]), WhoIsPrecede); //정렬기준유도}//우선 순위 큐의 초기화PQueueInit(&(pg->pqueue), PQWeightComp);}void AddEdge(ALGraph * pg, int fromV, int toV,int weight){Edge edge = {fromV, toV, weight}; // 간선의 가중치 정보를 담음// 정점 form V의 연결 리스트에 정점 toV 의 정보 추가LInsert(&(pg->adjList[fromV]), toV);// 정점 toV의 연결 리스트에 정점 fromV의 정보 추가LInsert(&(pg->adjList[toV]), fromV);pg->numE+=1;// 간선의 가중치 정보를 우선순의 큐에 저장PEnqueue(&(pg->pqueue), edge);}void ConKruskalMST(ALGraph * pg) // 최소 비용 신장 트리를 구성하는 함수{Edge recvEdge[20]; // 복원할 간선의 정보 저장Edge edge;int eidx = 0;int i;// MST를 형성할 때까지 아래의 반복문 실행while(pg->numE+1 > pg -> numV) // MST 간선의 수 + 1 == 정점의 수{// 우선순위 큐에서 가중치가 제일 높은 간선의 정보를 꺼낸다.edge = PDequeue(&(pg->pqueue));// 우선순위 큐에서 꺼낸 간선을 실제로 그래프에서 삭제한다.RemoveEdge(pg,edge.v1,edge.v2);// 간선을 삭제하고 나서도 두 정점을 연결하는 경로가 있는지 확인한다.if(!IsConnVertex(pg,edge.v1,edge.v2)){// 경로가 없다면 삭제한 간선을 다시 살린다.RecoverEdge(pg,edge.v1,edge.v2,edge.weight);// 복원한 간선의 정보를 별도로 저장한다.recvEdge[eidx++] = edge;}}// 우선순위 큐에서 삭제된 간선의 정보를 회복for(i=0;i<eidx;i++)PEnqueue(&(pg->pqueue), recvEdge[i]);}void ShowGraphEdgeWeightInfo(ALGraph * pg) // 간선의 가중치 정보 출력{PQueue copyPQ = pg -> pqueue;Edge edge;while(!PQIsEmpty(©PQ)){edge = PDequeue(©PQ)printf("(%c ~ %c, w:%d \n", edge.v1+65,edge.v2+65,edge.weight);}}//무방향 그래프 이므로 소멸시킬 간선의 정보가 두개이다void RemoveEdge(ALGraph * pg, int fromV, int toV) // 간선의 소멸{RemoveWayEdge(pg, fromV, toV);RemoveWayEdge(pg, toV, fromV);(pg->numE)--;}void RemoveWayEdge(ALGraph * pg, int fromV, int toV) // 한쪽 방향의 간선 소멸{int edge;if(LFirst(&(pg->adjList[fromV]), &edge)){if(edge==toV){LRemove(&(pg->adjList[fromV]));return;}while(LNext(&(pg->adjList[fromV]), &edge)){if(edge==toV){LRemove(&(pg->adjList[fromV]));return;}}}}void RecoverEdge(ALGraph * pg, int fromV, int toV, int weight){LInsert(&(pg->adjList[fromV]), toV);LInsert(&(pg->adjList[toV]), fromV);(pg->numE)++;}//전달받은 두 정점이 연결되어 있는지 보는 함수int IsConnVertex(ALGraph * pg, int v1, int v2){// 시작 정점의 방문이 일어난다 !Stack stack;int visitV = v1; // 1int nextV;StackInit(&stack); // DFS를 위한 스택의 초기화VisitVertex(pg, visitV); // 시작 정점을 방문SPush(&stack, visitV); // 시작 정점의 정보를 스택으로 !// visitV에 담긴 정점과 연결된 정점의 방문을 시도하는 while 문while(LFirst(&(pg->adjList[visitV]), &nextV)== TRUE)// LFirst 를 통해서 visitV에 연결된 정점 하나를 얻는다.// 이렇게 해서 얻은 정점의 정보는 nextV에 저장된다.{// visitV와 연결된 정점의 정보가 nextV에 담긴 상태에서 이하를 진행int visitFlag = FALSE;// 정점을 돌아다니는 도중에 목표를 찾는다면 트루를 반환if(nextV == v2){// 함수가 반환되기 전에 초기화 진행memset(pg->visitInfo, 0, sizeof(int)*pg->numV);return TRUE; // 목표 찾았으니 트루 반환}// nextV에 담긴 정점의 정보를 가지고 방문을 시도한다if(VisitVertex(pg, nextV)== TRUE) // 방문에 성공했다면{// 방문 성공했으니 visitV의 정보는 스택에 푸쉬SPush(&stack, visitV); // visitV 담긴 내용을 PUSH// nextV에 담긴 정보를 visitV 에 담고 다시 반복문// 반복문을 다시 시작하는 것은 또 다른 정점의 방문을 시도visitV = nextV;visitFlag = TRUE;}// LFirst 함수를 통해서 얻은 정점의 방문에 실패한 경우 이하 실행else // 방문 실패인 경우 연결된 다른 정점들을 찾는다.{//아래의 반목은 visitV에 연결된 정점을 찾을 때 까지 반복된다.while(LNext(&(pg->adjList[visitV]), &nextV)== TRUE){//LNext 함수의 호출을 통해서 visitV에 연결된 정점 하나를 얻는다.// 이렇게 얻은 정점의 정보는 nextV에 저장된다.if(nextV == v2){memset(pg->visitInfo, 0, sizeof(int)*pg->numV);return TRUE;}// 이 정보를 바탕으로 방문을 시도한다.if(VisitVertex(pg, nextV) == TRUE){SPush(&stack, visitV); // 방문 성공했으니 푸쉬visitV = nextV; // 담고 브레윀!visitFlag = TRUE;break;}}}// 정점 방문에 실패했다면 그에 따른 처리를 진행한다.if(visitFlag == FALSE) // 추가로 방문한 정점이 없었다면{// 길을 되돌아 가거나 시작 위치로 되돌아와서 프로그램을 종료하거나if(SIsEmpty(&stack)== TRUE) // 시작점으로 되돌아 왔음break;elsevisitV = SPop(&stack); // 길을 되돌아간다}}// 이후의 탐색을 위해서 탐색 정보 초기화memset(pg->visitInfo, 0, sizeof(int)*pg->numV);return FALSE; // 목표를 찾지 못했다 !}cs
728x90
'Data Structures & Algorithms' 카테고리의 다른 글
| [Algorithms] Basic-정다면체 문제 (0) | 2022.05.12 |
|---|---|
| [Algorithms] Basic-대표값 찾기 (0) | 2022.05.12 |
| [Data Structures] 테이블(Table)과 해쉬(Hash) (0) | 2022.05.09 |
| [Data Structures] 탐색 (Search) (0) | 2022.05.09 |
| [Data Structures] 정렬 (Sorting) (0) | 2022.05.09 |