그래프, DFS, BFS

그래프의 정의 

정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때, G = (V, E)이다.

정점 사이의 인접 관계를 나타내는 방법에는 크게 두 가지가 있다.

행렬을 이용하는 방법은 인접 행렬(Adjacency Matrix)이라 하고 리스트를 이용하는 방법은 인접 리스트(Adjacency List)라고 한다.

인접 행렬 

장점 : vertex간의 인접 여부를 빠르게 알 수 있다.

단점 : 정점의 크기 * N^2 만큼의 메모리가 사용된다.

그래프 순회

DFS (깊이 우선 탐색)

1. 시작 정점을 밟은 후 이 정점을 ‘방문했음’으로 표시한다.

2. 그리고 이 정점과 이웃하고 있는 정점(인접 정점) 중에 아직 방문하지 않은 곳을 선택하여 이를 시작 정점으로 삼아 다시 깊이 우선 탐색을 시작한다. 즉 1단계를 반복한다.

3. 정점에 더 이상 방문하지 않은 인접 정점이 없으면 이전 정점으로 돌아가서 2단계를 수행한다.

4. 이전 정점으로 돌아가도 더 이상 방문할 이웃이 없다면 그래프의 모든 정점을 방문했다는 뜻이므로 탐색을 종료한다.

 

void DFS( Vertex* V)

{

Edge* E= NULL;

printf("%d ", V->Data);

V->Visited = Visited;

//인접 정점이 있는지 확인하고 있다면 탐색한다.

for(E = V->AdjacencyList; E!= NULL; E = E->Next)

{

if(E->Target != NULL && E->Target->Visited == NotVisited)

DFS(E->Target);

}

}

 

BFS (너비 우선 탐색)

1. 시작 정점을 방문했음으로 표시하고 큐에 삽입한다.

2. 큐에서 정점을 제거하고 인접 정점들 중 방문하지 않은 정점들을 방문했음으로 표시하고 큐에 삽입한다.‘

3. 큐가 비게되면 끝나는 것. 큐가 빌 때가지 2를 반복한다.

 

Void BFS(Vertex* V, LinkedQueue* Queue)

{

Edge* E = NULL;

printf("%d ", V->Data);

V->Visited = Visited;

LQ_Enqueue(&Queue, LQ_CreateNode(V) ); //시작 정점을 큐에 삽입

while( !LQ_IsEmpty(Queue) )

{

Node* Popped = LQ_Dequeue(&Queue);

V = Popped->Data;

E = V->AdjacencyList;

 

while( E != NULL)

{

V = E->Target;

if( V != NULL && V->Visited == NotVisited) //미방문 정점만 방문

{

printf("%d ", V->Data);

V->Visited = Visited;

LQ_Enqueue(&Queue, LQ_CreateNode(V));

}

E = E->Next;

}

}

}