[C로 쓴 자료구조] 그래프(Graph)

Graph

 

완전 그래프

Edge의 수가 최대인 그래프 n개의 vertex 일 때 최대 edge 수 : n(n-1)/2

 

경로의 길이

경로 상에 있는 edge의 수

 

단순 경로(simple path)

처음과 마지막을 제외한 vertex가 다른 경로

 

 

그래프 표현 방법 분석

 

G에 존재하는 edge 수 검사, or G가 연결되었는지 검사

인접 행렬 : n(n-1)/2 개의 항 조사 -> O(n^2)

인접 리스트 : O(n+e)

 

Digraph에서 vertex의 in-degree 조사

인접 행렬 : O(n)

인접 리스트 : O(n+e)

 

 

---

DFS (깊이 우선 탐색)

 

 

 

로직

 

1. 출발 정점 v의 인접 리스트부터 방문

2. v에 인접하면서 아직 방문하지 않은 정점 w를 선택

3. w를 시작점으로 하여 다시 dfs 시작

4. recursion을 이용하여 구현

 

코드

 

void dfs(int v) {
	struct node* w;
	visited[v] = TRUE;
	printf("%5d", v);

	for (w = graph[v]; w; w = w->link)
		if (!visited[w->vertex])
			dfs(w->vertex);
}

 

---

 

BFS (너비 우선 탐색)

 

로직

 

1. 출발 정점 v의 인접 리스트부터 방문

2. v에 인접한 모든 정점들을 먼저 방문

3. 그 다음, v에 인접한 첫 번째 정점에 인접한 정점 중에서 아직 방문하지 않은 정점들을 다시 차례대로 방문 (Queue)

 

코드

 

void bfs(int v) {
	node_pointer w;
	struct queue* front = NULL, * rear = NULL;

	printf("%5d", v);
	visited[v] = TRUE;
	addq(&front, &rear, v);

	while (front) {
		v = deleteq();
		for(w=graph[v]; w; w= w->link)
			if (!visited[w->vertex]) {
				printf("%5d", w->vertex);
				addq(&front, &rear, w->vertex);
				visited[w->vertex] = TRUE;
			}
	}
}

 

---

 

Spanning Trees

 

그래프 G에 포함된 edge들로 구성되며, G의 모든 정점들을 포함하는 트리

 

DFS나 BFS를 이용하여 Spanning tree 구성

 

단절점(articulation point)

그래프 G의 정점 v 로서 v와 v에 부속된 edge들을 삭제할 경우, G가 두 개 이상의 연결 요소들로 분할되는 정점

 

단절점을 조사하기 위한 두 가지 규칙

1. DFS 트리의 루트가 두 개의 children을 가질 경우

2. DFS 트리에서 정점 u가 child로 w를 가지고 있으며, w와 w의 descendants, 그리고 하나의 back edge로 u의 ancestor에 갈 수 없을 경우

 

 

최소 비용 신장 트리

 

가중치가 부여된 무방향 그래프에서 신장트리(cycle을 형성하지 않는 트리)의 비용 = 신장 트리를 구성하는 edge들의 비용의 합이라고 할 때 가장 비용이 적은 spanning tree

 

모든 최소 비용 신장트리 알고리즘의 제약 조건

1. 그래프 내에 존재하는 edge들만 사용

2. n-1개의 edge만 사용(정점의 수 = n)

3. cycle을 형성할 수 었는 edge는 사용 불가

 

 

Kruskal (크루스칼 알고리즘)

 

그래프의 edge가 적을 때 사용

 

1. 한 번에 하나의 edge씩 추가하면서 최소비용 트리 T를 생성

2. edge들을 비용의 오름차순으로 정렬한 후, 가장 비용이 적은 edge부터 선택

3. 선택된 edge는 기존에 선택된 edge들과 사이클을 형성하지 않을 경우에만 T에 포함

4. 그래프 G가 연결되었으며, n>0개의 정점이 존재할 경우, 정확히 n-1개의 edge가 선택됨

 

 

비용이 최소인 edge를 어떻게 찾을까

1. edge를 비용 순으로 정렬 : O(n log n)

2. min heap을 이용 : 다음 차례 edge발견 -> O(log n)

                                   heap 구성 -> O(n)

 

Cycle 체크

union-find 사용 

 

총 알고리즘 복잡도 : O(n log n) 그래프가 많아지면 O(n^2 log n^2)까지 증가

 

 

Prim (프림 알고리즘)

 

그래프 edge가 많다면 prim 사용

 

1.  임의의 정점 v에서 시작

2. 각 단계에서 트리를 구성하도록 한 번에 하나의 edge를 선택

3. 트리 T에 포함된 정점과 포함되지 않은 정점을 연결하는 edge들 중에서 비용이 최소인 edge를 T에 추가

 

우선순위 큐 사용

시간 복잡도 : O(n^2)

 

 

 

 

---

Dijkstra (다익스트라 알고리즘)

 

시간 복잡도 : O(n^2)

 

코드

 

int choose(int distance[], int n, short int found[]) {
	//아직 s에 포함되지 않은 정점중에서 최소 거리를 갖는 정점 return
	int i, min, minpos;

	min = INT_MAX;
	minpos = -1;
	for (i = 0; i < n; i++)
		if (distance[i] < min && found[i] == FALSE) {
			min = distance[i];
			minpos = i;
		}
	
	return minpos;
}
	
void shortestpath(int v, int cost[][MAX_VERTICES], int distance[], int n, short int found[]) {
	
	int i, u, w;

	for (i = 0; i < n; i++) {
		found[i] = FALSE; 
		distance[i] = cost[v][i];
	}

	found[v] = TRUE;
	distance[v] = 0;

	for (i = 0; i < n - 2; i++) {
		u = choose(distance, n, found);
		found[u] = TRUE;
		for (w = 0; w < n; w++)
			if (found[w] == FALSE)
				if (distance[u] + cost[u][w] < distance[w])
					distance[w] = distance[u] + cost[u][w];
	}

}

 

---

다이나믹 프로그래밍 - 플로이드 워셜

 

시간 복잡도 : O(n^3)

 

코드

 

void allcosts(int cost[][MAX_VERTICES], int distance[][MAX_VERTICES], int n) {

	int i, j, k;

	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			distance[i][j] = cost[i][j];

	for (k = 0; k < n; k++)
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				if (distance[i][k] + distance[k][j] < distance[i][j])
					distance[i][j] = distance[i][k] + distance[k][j];
}

 

---

 

위상 정렬 (Topological Sort)

 

정점들 간의 선행 관계를 고려하여 모든 정점의 선형 순서를 정의

여러 개의 topological order가 존재 가능하다

 

void topological_sort(hdnode graph[], int n) {

	int i, j, k, top;
	struct node* ptr;

	top = -1;
	for (i = 0; i < n; i++) {
		if (!graph[i].count) { //in-degree가 없는것을 stack에 push(i)
			graph[i].count = top;
			top = i;
		}
	}

	for (i = 0; i < n; i++)
		if (top == -1) {
			fprintf(stderr, "Network has a cycle\n");
			exit(1);
		}
		else {
			j = top;
			top = graph[top].count; //pop()
			printf("v%d, ", j);

			for (ptr = graph[j].link; ptr != NULL; ptr = ptr->link) {
				k = ptr->vertex; //Successor vertex들의 count 감소
				graph[k].count--;
				if (!graph[k].count) { //새로운 vertex를 stack에 삽입
					graph[k].count = top; //push(k)
					top = k;
				}
			}

		}
}

 

 

void calculateEarliestTime(hdnode graph[], int n, int earliest[]) {

	int i, j, k;
	struct node* ptr;

	for (i = 0; i < n; i++) {
		if (graph[i].count == 0)
			push(i);
		earliest[i] = 0;
	}

	for (i = 0; i < n; i++) {

		if (StackEmpty() == true)
			return;
		else {
			j = pop();
			
			for (ptr = j; ptr != NULL; ptr = ptr->link) {
				k = ptr->vertex; //Successor vertex들의 count 감소
				graph[k].count--;
				if (graph[k].count == 0)  //새로운 vertex를 stack에 삽입
					push(k);
			
				//if (earliest[k] < earliest[j] + ptr->dur)
				//	earliest = earliest[j] + ptr->dur;
            }
	}
}