11.1 최소 비용 신장 트리
11.2 Kruskal의 MST 알고리즘
11.3 Prim의 MST 알고리즘
11.4 최단 경로
11.5 Dijkstra의 최단 경로 알고리즘
11.6 Floyd의 최단 경로 알고리즘
11.7 위상 정렬
11.1 최소 비용 신장 트리
신장트리 (spanning tree)
- 그래프 내의 모든 정점을 포함하지만 사이클은 아닌 트리
- n개의 정점 신장트리 -> n-1개 간선
- 적은 링크만 사용한다고 최소비용은 x -> 링크 구축 비용( 간선 가중치)까지 고려해서 최소 신장 트리 선택해야함
신장트리 알고리즘
| depth_first_search(v): 1. v를 방문되었다고 표시; 2. for all u ∈ (v에 인접한 정점) do 3. if (u가 아직 방문되지 않았으면) 4. then (v, u)를 신장 트리 간선이라고 표시; 5. depth_first_search(u) depth_first_search(v): // 10장 1. v를 방문되었다고 표시; 2. for all u ∈ (v에 인접한 정점) do 3. if (u가 아직 방문되지 않았으면) 4. then depth_first_search(u) |
최소 비용 신장 트리 (MST: minimum spanning tree)
- 모든 정점들을 가장 적은 수의 간선과 비용으로 연결
- 사용된 간선 가중치 합이 최소인 신장트리
- Kruskal, Prim 알고리즘이 대표적 ( 1. 간선 가중치 합 최소 / 2. (n-1)개 간선만 사용 / 3. 사이클 포함 x )
11.2 Kruskal의 MST 알고리즘
Kruskal's MST 알고리즘
- greedy method => 각 단계에서 최선의 답을 선택하여 최종적인 해답에 도달 (but 보장 없어서 항상 최적 해답 검증 필요)
- Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명 됨
- 먼저 간선들을 가중치의 오름차순으로 정렬 -> 사이클 형성 x 간선 찾아 현재의 최소 비용 신장 트리의 집합에 추가 -> 만약 사이클 형성하면 간선 제외하기
| //Kruskal 알고리즘으로 최소 비용 스패닝트리 구하기 //입력: 가중치 그래프 G = (V,E) , n은 노드 개수 //ecounter: MST에 포함된 edge 개수 //k: 현재(가중치 작은 순서부터) 검사한 edge의 개수 //출력: Et, 최소비용 신장 트리 이루는 간선 집합 kruskal(G) E를 w(e1) <= ... <= w(ee)가 되게 정렬 (오름차순으로) Et <- 공집합; ecounter <- 0 k <- 0 while ecounter < (n-1) do //트리의 성질을 loop 종료 조건에 k <- k+1 //다음 가장 weight이 적은 간선의 index if ( Et U {ek}가 사이클을 포함x ); //union-find 연산 활용 then Et <- Et U {ek}; ecounter <- ecounter + 1 return Et |
Union-find 연산
- 같은 집합에 속하는 간선 추가하면 사이클이 형성됨 ==> 따라서 지금 추가하는 간선의 양끝 정점이 같은 집합에 속한지 검사 필요
- 원소가 어떤 집합에 속하는지 알아냄
- Kruskal의 MST 알고리즘에서 사이클 검사에 사용
Union-find 알고리즘
- 부모 포인터 표현: 각 노드에 대해 그 노드의 부모에 대한 포인터만 저장
=> "두 노드가 같은 트리에 있습니다?" 질문에 대답하는데 필요한 정보 저장.
| UNION(a,b): 1. root1 = FIND(a); // 노드a의 루트를 찾는다 2. root2 = FIND(b); // 노드b의 루트를 찾는다. 3. if root1 =/ root2 // 합한다. 4. parent[root1] = root2; //parent[root2] = -1로 초기화 FIND(curr): //curr의 루트를 찾는다. 1. if (parent[curr] == -1) //자기 자신 2. return curr; //루트 3. while (parent[curr] != -1) //O(log|V|) curr = parent[curr]; 4.return curr; |
a와 b의 root node가 같은가? == a와 b가 같은 그룹에 속했는가? == a와 b 사이에 edge를 추가하면 cycle이 생기는가?
union-find 프로그램
int parent[MAX_VERTICES]; //부모 노드
void set_init(int n) //n은 정점의 개수
{
for(int i=0; i<n; i++)
parent[i] = -1;
}
//curr가 속하는 집합을 반환한다
//return (루트 or 대표노트(X)), where parent[x] == -1
int set_find(int curr)
{
if(parent[curr] == -1)
return curr; //루트
while(parent[curr] != -1)
curr = parent[curr];
return curr;
}
//두개의 원소가 속한 집합을 합친다.
void set_union(ina a, int b)
{
int root1 = set_find(a); //노드 a의 루트를 찾는다
int root2 = set_find(b); //노드 b의 루트를 찾는다
if (root1 != root2) //합한다.
parent[root1] = root2; //a의 대표노드의 부모를 b의 대표노드로 변경
}
union-find 이용한 Kruskal's 프로그램
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000
int parent[MAX_VERTICES]; //부모 노드
void set_init(int n) //초기화
{
for (int i=0; i<n; i++)
parent[i] = -1;
}
//curr가 속하는 집합을 반환한다.
int set_find(int curr)
{
if (parent[curr] == -1)
return curr; //루트
while (parent[curr] != -1) curr = parent[curr];
return curr;
}
//두개의 원소가 속한 집합을 합친다.
void set_union(int a, int b)
{
int root1 = set_find(a); //노드 a의 루트를 찾는다.
int root2 = set_find(b); //노드 b의 루트를 찾는드ㅏ.
if (root1 != root2) //합한다.
parent[root1] = root2;
}
struct Edge { //간선을 나타내는 구조체
int start, end, weight;
};
typedef struct GraphType {
int n; //간선의 개수
int nv; //정점의 개수
struct Edge edges[2*MAX_VERTICES];
} GraphType;
//그래프 초기화
void graph_init(GraphType* g)
{
g->n = 0;
g->nv = 0;
for (int i = 0; i < 2 * MAX_VERTICES; i++) {
g->edges[i].start = 0;
g->edges[i].end = 0;
g->edges[i].weight = INF;
}
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end, int w)
{
g->edges[g->n].start = start;
g->edges[g->n].end = end;
g->edges[g->n].weight = w;
g->n++;
}
// qsort()에 사용되는 함수
int compare(const void* a, const void* b)
{
struct Edge*x = (struct Edge*)a;
struct Edge*y = (struct Edge*)b;
return (x->weight - y->weight); //return 값 < 0 : a<b
//return 값 = 0 : a==b
//return 값 > 0 : a>b
}
//kruskal의 최소 비용 신장 트리 프로그램
void kruskal(GraphType* g)
{
int edge_accepted = 0; // 현재까지 선택된 간선의 수
int uset, vset; // 정점 u와 정점 v의 집합 번호
struct Edge e;
set_init(g->nv); // 집합 초기화 ∀𝑖 parent[i] = -1
qsort(g->edges, g->n, sizeof(struct Edge), compare);
\\After qsort() ===>> g->edges[0].weight ≤ g->edges[1].weight ≤ … ≤ g->edges[(g->n)−1].weight
printf("크루스칼 최소 신장 트리 알고리즘 \n");
int i = 0; // 오름차순으로 검색한 edge 들의 개수
while (edge_accepted < (g->nv - 1) ) { // 간선의 수 < (|V|-1) => tree의 조건
e = g->edges[i]; //다음 최소 ㅣㅂ용 간선
uset = set_find(e.start); // 정점 u의 집합 번호
vset = set_find(e.end); // 정점 v의 집합 번호
if (uset != vset) { // 서로 속한 집합이 다르면
printf("간선 (%d,%d) %d 선택\n", e.start, e.end, e.weight);
edge_accepted++;
set_union(uset, vset); // 두개의 집합을 합친다.
} // if문은 간선e를 MST 그래프에 포함시킴
i++;
} // end of while
}
int main(void)
{
GraphType* g;
g = (GraphType*)malloc(sizeof(GraphType));
graph_init(g);
//g->nv=7;
insert_edge(g, 0, 1, 29);
insert_edge(g, 1, 2, 16);
insert_edge(g, 2, 3, 12);
insert_edge(g, 3, 4, 22);
insert_edge(g, 4, 5, 27);
insert_edge(g, 5, 0, 10);
insert_edge(g, 6, 1, 15);
insert_edge(g, 6, 3, 18);
insert_edge(g, 6, 4, 25);
kruskal(g);
free(g);
return 0;
}
실행결과
Kruskal's MST 알고리즘 분석
- Kruskal 알고리즘에서는 간선 정렬해야해서 간선들의 집합으로 저장 (GraphType 안에 간선들만 저장)
- 정렬 알고리즘으로는 qsort() 함수 사용
- Kruskal 알고리즘은 간선 정렬 시간에 좌우 ( 사이클 테스트 작업은 영향 적음)
- 네트워크 간선 e개를 퀵정렬과 효율적인 알고리즘으로 정렬하면 Kruskal 알고리즘의 시간 복잡도는 O(e*loge)
- worst case의 big O ==>> complete graph , |E|=(|V|x|V|-1)/2 , O(|V|^2log|V|^2)
11.3 Prim의 MST 알고리즘
Prim's MST 알고리즘
- 시작 정점에서부터 출발해서 신장 트리 집합을 단계적으로 확장함
- 신장 트리 집합에 인접한 정점 중 최저 간선으로 연결된 정점 선택해서 신장 트리 집합에 추가
- 시작 정점만으로 시작했다가 최저 간선 정점 선택하여 확장하다가 n-1 간선 가질 때까지 계속
Prim's MST 알고리즘
| //최소 비용 신장 트리 구하는 Prim 알고리즘 //입력: 네트워크 G=(V,E), s는 시작 정점 //출력: 최소 비용 신장 트리 이루는 정점 집합 //**Uniqueness of MST => yes only when 모든 weight이 다르다면 Prim(G,s) for each u ∈V do dist[u] <- 무한집합 dist[s] <- 0 //우선 순위큐 Q에 모든 정점을 삽입(우선순위는 dist[]) min heap for i <- 0 to n-1 do u <- delete_min(Q) 화면에 u를 출력 for each v { (u의 인접 정점) //**dist[v]: v가 현 MST와 직접연결된 간선의 weight //**Update dist[] : 방금 MST에 포함된 vertex와 직접연결된 (아직 MST에 포함 안된 ) 노드들의 dist[]를 변경 if ( v ∈ Q and weight [u][v] < dist[v] ) //여전히 Q에 있는 노드 = 아직 MST에 포함 X 노드 -> selected[] then dist[v] <- weight[u][v] |
Prim's MST 프로그램
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000L
typedef struct GraphType
{
int n; // 정점의 개수
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int selected[MAX_VERTICES];
int distance[MAX_VERTICES];
// 최소 dist[v] 값을 갖는 정점을 반환
int get_min_vertex(int n)
{
int v, i;
for (i = 0; i < n; i++)
if (!selected[i]) {
v = i;
break;
}
for (i = 0; i < n; i++)
if (!selected[i] && (distance[i] < distance[v])) v = i; //**v는 아직 MST에 포함X 노드 아무거나
return (v); //**v는 아직 MST에 포함되지 않은 노드들 중 distance[]값 가장 작은 것
}
//시간복잡도는 O(|V|^2)
void prim(GraphType* g, int s) //s는 시작정점
{
int i, u, v;
for (u = 0; u < g->n; u++)
distance[u] = INF;
distance[s] = 0; //|V|개의 노드가 모두 MST에 포함될 때까지 or
for (i = 0; i < g->n; i++) {
u = get_min_vertex(g->n); // u = 최소 dist[v] 값을 갖는 정점
selected[u] = TRUE;
if (distance[u] == INF) return; //g is a disconnected graph
printf("정점 %d 추가\n", u); // MST ∪= {u}
for (v = 0; v < g->n; v++) //u의 모든 간선들
if (g->weight[u][v] != INF)
if (!selected[v] && g->weight[u][v] < distance[v])
distance[v] = g->weight[u][v]; //이전 MST와의 거리(dist[v])보다 방금 전 MST에 포함된
//노드(u)를 통한 거리가 더 가까우면 Update dist[v]
}
}
int main(void)
{
GraphType g = { 7,
{ { 0, 29, INF, INF, INF, 10, INF },
{ 29, 0, 16, INF, INF, INF, 15 },
{ INF, 16, 0, 12, INF, INF, INF },
{ INF, INF, 12, 0, 22, INF, 18 },
{ INF, INF, INF, 22, 0, 27, 25 },
{ 10, INF, INF, INF, 27, 0, INF },
{ INF, 15, INF, 18, 25, INF, 0 } }
}; // 가중치 인접행렬
prim(&g, 0);
return 0;
}
typedef struct GraphType
{
int n; // 정점의 개수
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType실행결과
Prim's MST 알고리즘 분석
- 주 반복문이 정점의 수 n만큼 반복하고, 내부반복이 n번 반복하므로 Prim의 알고리즘은 O(n2)의 복잡도
Kruskal vs Prim
- Kruskal은 edge weight이 가장 작은 노드들부터 시작 vs Prim은 임의 노드에서 시작
- Kruskal은 간선들이 비용 순서대로 한번씩만 처리 vs Prim 은 최소 거리 얻기 위해 하나의 노드 여러번 방문(update dist[x]) 함.
- Kruskal은 Disconnected graph에서도 동작 vs Prim은 Connected graph에서만 동작
- Kruskal 은 모든 edge들 정렬해야 하니까 sparse graph에서 더 빨리 실행 vs Prim은 dense graphs에서 더 빨리 실행
- Kruskal 알고리즘은 간선 기반 vs Prim 알고리즘은 정점 기반
- Kruskal은 Forest(disconnected components) 생산 vs Prim은 한개의 connected component 생산
- Kruskal 알고리즘에서는 이전 단계에서 만들어진 신장 트리와는 상관 xx 무조건 최저 간선만을 선택 vs Prim 알고리즘은 이전 단계에서 만들어진 신장 트리 확장 방식
- Kruskal 알고리즘 복잡도는 O(eloge) => 희소 그래프 적합 vs Prim 알고리즘 복잡도는 O(n^2)이므로 밀집 그래프 적합
11.4 최단 경로
최단경로
- 네트워크에서 정점 u와 정점 v를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로
- 가중치 인접행렬
최단경로 알고리즘
- Dijkstra 알고리즘 : 하나의 시작 정점 ~ 모든 다른 정점까지의 최단경로 계산
- Floyd 알고리즘 : 모든 정점 ~ 모든 다른 정점까지의 최단경로 계산
- 인접행렬 : 간선이 없으면 인접 행렬 값 0 <-> 가중치 인접 행렬 : 간선이 없으면 무한대 값 (가중치 0이 가능하므로)
11.5 Dijkstra's 최단경로 알고리즘
- 집합 S: 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합
- distance 배열: 최단경로가 알려진 정점들만을 이용한 다른 정점들까지의 최단경로 거리
- 매 단계에서 가장 작은 distance 값 정점을 집합 S에 추가
[ 증명 ]
1. 각 단계에서 S안에 있지 않은 정점 (아직 시작정점 source node로부 부터의 최단 경로가 발견 X 노드) 중에서 가장 distance값이 작은 정점(v로 부터 이미 최단 경로가 결정된 노트들만을 이용해 가장 짧은 길이로 도달할 수 있는 노드)을 S에 추가
2. 정점 w를 거쳐 정점 u로 가는 가상적인 더 짧은 경로가 있다고 가정
3. (정점 v ~ 정점 u) = (정점 v ~ 정점 w) + (정점 w ~ 정점 u)
4. but. 항상 (정점 v ~ 정점 w) > 최단경로 ==> bcz 현재 distance 값이 최소인 정점은 u이기 때문
5. 새로운 정점이 S에 추가되면 distance 값 갱신
=> distance[w] = min(distance[w], distance[u] + weight[u][w])
| //입력: 가중치 그래프 G, 가중치는 음수x **강조하심 //출력: distance 배열, distance[u]는 v에서 u까지의 최단거리. shortest_path(G,v): 1. S <- {v} 2. for 각 정점 wㅌG do 3. distance[w] <- weight[v][w]; //v와 직접 연결되지 않은 노드는 INF 4. while 모든 정점이 S에 포함되지 않으면 do 5. u <- 집합 S에 속하지 않는 정점 중 최소 distance 정점; 6. S <- S U {u} 7. for u에 인접하고 S에 있는 각 정점 z do 8. if distance[u] + weight[u][z] < distance[z] 9. then distance[z] <- distance[u] + weight[u][z]; |
Dijkstra's 최단경로 프로그램
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000000 /* 무한대 (연결이 없는 경우) */
typedef struct GraphType
{
int n; // 정점의 개수
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int distance[MAX_VERTICES]; /* 시작정점으로부터의 최단경로 거리 */
int found[MAX_VERTICES]; /*방문한 정점 표시*/
int choose(int distance[], int n, int found[]) //O(|V|) 시간복잡도 (min heap은 O(log|V|)
{
int i, min, minpos;
min = INT_MAX;
minpos = -1;
for (i = 0; i < n; i++)
if (distance[i] < min && !found[i]) {
min = distance[i];
minpos = i;
}
return minpos;
}
void shortest_path(GraphType* g, int start) //O(|V|^2) 시간복잡도 (min heap은 O(|V|log|V|))
{
int i, u, w;
for (i = 0; i < g->n; i++) { /* 초기화 */
distance[i] = g->weight[start][i];
found[i] = FALSE;
}
found[start] = TRUE; /* 시작 정점 방문 표시 */
distance[start] = 0;
for (i = 0; i < g->n - 1; i++) {
print_status(g);
u = choose(distance, g->n, found); //O(log|V|)
found[u] = TRUE;
for (w = 0; w < g->n; w++)
if (!found[w])
if (distance[u] + g->weight[u][w] < distance[w])
distance[w] = distance[u] + g->weight[u][w];
} //heap 자료구조에서 key를 update 하지 말고 줄어든 key값을 가지는 새로운 노드를 추가하는 방식으로 구현
} (동일 노트 & 다른 distance[]를 허용) =>> O(log|V|)
void print_status(GraphType* g)
{
static int step = 1;
printf("STEP %d :", step++);
printf("distance: ");
for (int i=0; i<g->n; i++) {
if (distance[i] == INF)
printf(" * ");
else
printf("%2d ", distance[i]);
}
printf("\n");
printf(" found: ");
for (int i=0; i<g->n; i++)
printf("%2d ", found[i]);
printf("\n\n");
}
int main(void)
{
GraphType g = { 7,
{ { 0, 7, INF, INF, 3, 10, INF },
{ 7, 0, 4, 10, 2, 6, INF },
{ INF, 4, 0, 2, INF, INF, INF },
{ INF, 10, 2, 0, 11, 9, 4 },
{ 3, 2, INF, 11, 0, INF, 5 },
{ 10, 6, INF, 9, INF, 0, INF },
{ INF, INF, INF, 4, 5, INF, 0 } }
};
shortest_path(&g, 0);
return 0;
}실행 결과
Dijkstra's 최단경로 알고리즘 복잡도
- 네트워크에 n개의 정점이 있다면, Dijkstra의 최단경로 알고리즘은 주반복문을 n번 반복하고 내부 반복문을 2n번 반복하므로 O(n^2)의 복잡도 가짐
--> min heap은 O(|V|log|V|)
11.6 Floyd의 최단 경로 알고리즘
- 모든 정점 사이의 최단 경로를 구하려면 앞의 Dijkstra 알고리즘을 정점 수만큼 반복 실행하면 됨 but Floyd는 더 간단 좋
Floyd warshall 최단경로 알고리즘
| floyd(G): 1. for k <- 0 to n-1 2. for i <- to n-1 3. for j <- 0 to n-1 4. A[i][j] = min(A[i][j], A[i][k] + A[k][j]) |
- 모든 정점 사이의 최단 경로 찾음
- 2차원 배열 A를 이용하여 3중 반복 루프로 구성
- Ak[i][j] : 0부터 k까지의 정점만을 이용한 정점 i에서 j까지의 최단 경로 길이
- A-1(가중치 행렬 초기 상태) -> A0 -> A1 -> ... -> An-1 순으로 최단 경로 구해감
- Ak-1까지 구해진 상태에서 k번째 정점이 추가로 고려된다면....
==> shortest_path(i to j) = min(shortest_path(i to k) + shortest_path(k to j))
- 0부터 k까지의 정점만을 사용해 정점 i에서 j까지의 최단 경로 길이 구하는 2가지 방법
- 정점 k 거치지 X
Ak[i][j]는 k보다 큰 정점 통과 X => 최단거리는 여전히 Ak-1[i][j]
즉, Ak[i][j] = Ak-1[i][j]
2. 정점 k 거치는 O
i에서 k까지 최단거리 Ak-1[i][j] + k에서 j까지 최단거리 Ak-1[k][j]
즉, Ak[i][j] = Ak-1[i][k] + Ak-1[k][j]
Floyd의 최단경로 프로그램
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000000 /* 무한대 (연결이 없는 경우) */
typedef struct GraphType {
int n; //정점의 개수
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int A[MAX_VERTICES][MAX_VERTICES];
void printA(GraphType *g)
{
int i, j;
printf("====================\n");
for (i=0; i<g->n; i++) {
for (j=0; j<g->n; j++) {
if (A[i][j] == INF)
printf(" * ");
else printf("%3d ", A[i][j]);
}
printf("\n");
}
printf("====================\n");
}
//
void floyd(GraphType* g)
{
int i,j,k;
for (i=0; i < g->n; i++)
for (j=0; j < g->n; j++)
A[i][j] = g->weight[i][j];
printA(g);
for (k=0; k < g->n; k++)
{
for (i=0; i < g->n; i++)
for (j=0; j < g->n; j++)
if (A[i][j] + A[i][j] < A[i][j])
A[i][j]= A[i][k] + A[k][j];
printA(g);
}
}
//main 함수
int main(void)
{
GraphType g = { 7,
{ { 0, 7, INF, INF, 3, 10, INF },
{ 7, 0, 4, 10, 2, 6, INF },
{ INF, 4, 0, 2, INF, INF, INF },
{ INF, 10, 2, 0, 11, 9, 4 },
{ 3, 2, INF, 11, 0, INF, 5 },
{ 10, 6, INF, 9, INF, 0, INF },
{ INF, INF, INF, 4, 5, INF, 0 } }
};
floyd(&g);
return 0;
}
Floyd 최단경로 알고리즘 시간 복잡도
- 네트워크에 n개의 정점이 있다면, Floyd의 최단경로 알고리즘은 3중 반복문을 실행되므로 시간 복잡도는 O(n^3) 이 된다 - 모든 정점 상의 최단경로를 구하려면 Dijkstra의 알고리즘 O(n^2)을 n번 반복해도 되며, 이 경우 전체 복잡도는 O(n^3)
11.7 위상정렬 (topological sort)
- **방향 그래프에서 간선 <u, v>가 있다면 정점 u는 정점 v를 선행
- 방향 그래프 정점들의 선행 순서를 위배하지 않으면서도 모든 정점 나열하여 선행 관계 표현함
위상 순서
-> (0,1,2,3,4,5) , (1,0,2,3,4,5) 동일한 그래프에 여러 위상정렬 ok
but (2,0,1,3,4,5)는 위상 순서 x 왜냐하면 2번이 0번 앞
위상정렬 알고리즘
| //Input: 그래프 G=(V,E) //Output: 위상 정렬 순서 topo_sort(G) for i<-0 to n-1 do if (모든 정점이 선행 정점을 가지면) //방향그래프에서만 가능!! then 사이클이 존재하고 위상 정렬 불가; 선행 정점을 가지지 않는 정점 v 선택; //a vertex with no incoming edges ..즉, in_degree == 0 v 출력 v와 v에서 나온 모든 간선들을 그래프에서 삭제; |
위상정렬 프로그램
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50
typedef struct GraphNode {
int vertex;
struct GraphNode* link'
} GraphNode;
typedef struct GraphType {
int n; // |V|
GraphNode* adj_list[MAX_VERTICES];
} GraphType;
//그래프 초기화
void graph_init(GraphType* g) {
g->n = 0;
for(int i=0; i<MAX_VERTICES; i++)
g->adj_list[i] = NULL;
}
//정점 삽입 연산
void insert_vertex(GraphType *g, int v)
{
if (((g->n) + 1) > MAX_VERTICES) {
fprintf(stderr, "그래프: 정점의 개수 초과");
return;
}
g->n++;
}
//간선 삽입 연산, v를 u의 인접 리스트에 삽입
void insert_edge(GraphType *g, int u, int v)
{
GraphNode *node;
if (u>=g->n || v>=g->n) {
fprintf(stderr, "그래프: 정점 번호 오류");
return;
}
node = (GraphNode *)malloc(sizeof(GraphNode));
node->vertex = v;
node->link = g->adj_list[u];
g->adj_list[u] = node;
}
#define MAX_STACK_SIZE 100
typedef int element;
typedef struct {
element stack[MAX_STACK_SIZE];
int top;
} StackType;
//스택 초기화 함수
void init(StackType *s)
{
s->top = -1;
}
//공백 상태 검출 함수
int is_empth(StackType *s)
{
return (s->top == -1);
}
//포화 상태 검출 함수
int is_full(StrackType *s)
{
return (s->top == (MAX_STACKSIZE - 1));
}
//삽입함수
void push(StackType *s, element item)
{
if (is_full(s)) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
else s->stack[++(s->top)] = item;
//삭제함수
element pop(StackType *s)
{
if (is_empth(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->stack[(s->top)--];
}
//위상정렬 수행
int topo_sort(GraphType* g)
{
int i;
StackType s;
GraphNode* node;
//모든 정점의 진입 차수 계산
int* in_degree = (int*)malloc(g->n*sizeof(int));
for (i=0; i < g->n; i++) //초기화
in_degree[i] = 0;
for (i=0; i < g->n; i++) {
GraphNode* node = g->adj_list[i]; //정점 i에서 나오는 간선들
while (node!= NULL) {
in_degree[node->vertex]++; //edge(i,node->vertex)
node = node->link;
}
}
//진입차수가 0인 정점을 스택에 삽입 ==> why stack? 큐를 쓴다면? 가능!!
init(&s); //스택 초기화
for (i=0; i<g->n; i++) {
if (in_degree[i] == 0) push(&s, i); //in_degree가 0인 노드들을 모두 push
}
//위상 순서 생성
while(!is_empty(&s)) {
int w;
w = pop(&s);
printf("정점 %d ->", w); //정점 출력 output) 1 4 0 2 3 5
node = g->adj_list[w]; //각 장점의 진입 차수 변경
while (node != NULL) {
int u = node->vertex;
in_degree[u]--; //진입 차수 감소
if(in_degree[u] == 0) push(&s, u);
node = node->link; //다음 정점
} //end of inner while
} //end of outer while
free(in_degree);
printf("\n");
return (i == g->n); //반환값이 1이면 성공, 0이면 실패~
//main 함수
int main(void)
{
GraphType g;
graph_init(&g);
insert_vertex(&g,0); insert_vertex(&g,1);
insert_vertex(&g,2); insert_vertex(&g,3);
insert_vertex(&g,4); insert_vertex(&g,5);
//정점 0의 인접 리스트 생성
insert_edge(&g,0,2); insert_edge(&g,0,3);
//정점 1의 인접 리스트 생성
insert_edge(&g,1,3); insert_edge(&g,1,4);
//정점 2의 인접 리스트 생성
insert_edge(&g,2,3); insert_edge(&g,2,5);
//정점 3의 인접 리스트 생성
insert_edge(&g,3,5);
//정점 4의 인접 리스트 생성
insert_edge(&g,4,5);
//위상 정렬
topo_sort(&g);
//동적 메모리 반환 코드 생략
return 0;
}
실행 결과
정점 1 -> 정점 4 -> 정점 0 -> 정점 2 -> 정점 3 -> 정점 5 ->
'Study > Data Structure' 카테고리의 다른 글
| 자료구조 전체 (0) | 2023.12.08 |
|---|---|
| [자료구조 스터디] chap.13 탐색 (0) | 2023.12.01 |
| [자료구조 스터디] chap.12 정렬 (0) | 2023.11.21 |
| [자료구조 스터디] chap.10 그래프 I (0) | 2023.11.20 |
