14장 그래프(Graph)

Posted on: 2019년 04월 08일 2019년 04월 08일
Categories: 강의자료, 자료구조

그래프의 역사
1. 수학자 오일러(Euler)에 의해 고안
2. 1736년 쾨니히스베르크 다린 문제
  1. 모든 다리를 한 번씩만 건너서 처음 출발한 장소로 돌아올 수 있을까?
  2. 정점 별로 연결된 간선의 수가 모두 짝수이어야 간선을 한 번씩만 지나서 처음 출발했던 정점으로 돌아올 수 있다.
그래프 용어
1. 정점(vertex)
2. 간선(edge)
3. 무방향 그래프(undirected graph)
4. 방향 그래프(directed graph, digraph)
5. 완전 그래프(complete graph) : 모든 점점들끼리 간선으로 연결되어 있는 그래프
6. 가중치 그래프(weight graph)
7. 부분 그래프(sub graph)
8. V(그래프) : 그래프의 정점 집합
9. E(그래프) : 그래프의 간선 집합
10. 그림출처 : https://brilliant.org/wiki/breadth-first-search-bfs/
그래프를 구현하는 두 가지 방법
1. 인접 행렬(adjacent matrix) 기반 그래프
  1. 위 그래프를 인접 행렬로 표현하시오.
2. 인접 리스트(adjacent list) 기반 그래프
  1. 위 그래프를 인접 리스트로 표현하시오.
깊이 우선 탐색(Depth First Search; DFS)
1. 여러 개의 간선 중 하나만 선택해서 계속 다음 정점으로 찾아간다.
2. 더 이상의 정점이 없으면 이전 정점으로 되돌아가서 다른 정점을 찾는다.
3. 첫 정점까지 되돌아오면 DFS는 끝난다.
4. 위 그래프에 대해 DFS를 구하시오(정점 0부터 시작해서 찾는 순서는 0시부터 시계방향 순서로)
너비 우선 탐색(Breadth First Search; BFS)
1. 첫 정점에 연결된 모든 정점을 찾아간다.
2. 각 정점들은 탐색되지 않았고, 자신과 연결되어 있고 정점을 찾아간다.
3. 더 이상의 탐색되지 않은 정점이 없으면 BFS는 끝난다.
4. 위 그래프에 대해 BFS를 구하시오(정점 0부터 시작해서 찾는 순서는 0시부터 시계방향 순서로)
최소비용 신장트리(Minimum Cost Spanning Tree; MST)
1. 신장트리
  1. 트리 정의 : 사이클(Cycle)을 형성하지 않는 그래프
  2. 신장트리 특징
    1. 그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있다.
    2. 그래프 내에서 사이클을 형성하지 않는다.
2. 최소비용신장트리
  1. 신장 트리의 모든 간선의 가중치 합이 최소인 그래프
3. 최소비용신장트리의 사용처
  1. 고속도로 노선
  2. KTX 노선
4. 최소비용 신장트리 알고리즘
  1. 크루스칼(Kruskal) 알고리즘 : 가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 또는 삭제해 나가는 방식
  2. 프림(Prim) 알고리즘 : 하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식
5. 다음 그래프의 최소비용신장트리를 구하시오(그림 출처:https://www.geeksforgeeks.org/problem-solving-minimum-spanning-trees-kruskals-prims/)
연습문제 :
1. 다음 그래프에 대하여 답하시오.(순서는 12시 방향에서 시계방향 순으로)
  1. 깊이우선 탐색 DFS(시작 정점 e) : e, g, f, c, b, d, -, a, -, -, -, -, -,
  2. 너비우선 탐색 BFS(시작 정점 e) : e, g, f, d, b, c, a
  3. Kruskal 최소비용 신장트리 : be, ac, ef, bc, fg, cd
    1. 정점(7개), 간선(6개), 총 가중치(21)
  4. Prim 최소비용 신장트리(시작 정점 e) : eb, ef, fg, bc, ca, cd
    1. 정점(7개), 간선(6개), 총 가중치(21)
2. 다음 그래프에 대하여 답하시오.(순서는 12시 방향에서 시계방향 순으로)
  
  출처 : https://www.zerocho.com/category/Algorithm/post/584bcd42580277001862f1a7
  1. 깊이우선 탐색 DFS(시작 정점 b)
  2. 너비우선 탐색 BFS(시작 정점 b)
  3. Kruskal 최소비용 신장트리
  4. Prim 최소비용 신장트리(시작 정점 b)
3. 다음 그래프에 대하여 답하시오.(순서는 12시 방향에서 시계방향 순으로)
  1. 깊이우선 탐색 DFS(시작 정점 2)
  2. 너비우선 탐색 BFS(시작 정점 2)
  3. Kruskal 최소비용 신장트리
  4. Prim 최소비용 신장트리(시작 정점 2)
4. 다음 그래프에 대하여 답하시오.(순서는 12시 방향에서 시계방향 순으로)
  
  출처 : https://ptwiddle.github.io/Graph-Theory-Notes/s_graphalgorithms_exercises.html
  1. 깊이우선 탐색 DFS(시작 정점 c)
  2. 너비우선 탐색 BFS(시작 정점 c)
  3. Kruskal 최소비용 신장트리
  4. Prim 최소비용 신장트리(시작 정점 c)
============== 프로그램 소스 코드 부분 ==============

희소행렬 표현한 그래프 : S014_AdjacentMatrix.c

#include <stdio.h>
#include <stdlib.h>
#define EDGE_MAX 20
#define N 7

typedef struct edge_type{
	int v1;
	int v2;
	int w;
} EDGE;

EDGE edge[EDGE_MAX];
int e_cnt = 0;

void main(){
	int i, x, y;
	int p1, p2;

	int gr[N][N] = {
		{0,5,3,0,0,0,0},
		{5,0,4,6,2,0,0},
		{3,4,0,5,0,6,0},
		{0,6,5,0,6,6,0},
		{0,2,0,6,0,3,5},
		{0,0,6,6,3,0,4},
		{0,0,0,0,5,4,0}
	};

	e_cnt = 0;
	for(y=0; y<N; y++){
		for(x=0; x<N; x++){
			if(gr[y][x] > 0){
				edge[e_cnt].v1 = y;
				edge[e_cnt].v2 = x;
				edge[e_cnt].w = gr[y][x];
				e_cnt++;
			}
		}
	}


	for(i=0; i<e_cnt; i++){
		printf("%d-v2(%d)\n",edge[i].v1, edge[i].v2, edge[i].w);
	}
}

#include <stdio.h>

#include <stdlib.h>

#define EDGE_MAX 20

#define N 7

typedef struct edge_type{

int v1;

int v2;

int w;

} EDGE;

EDGE edge[EDGE_MAX];

int e_cnt = 0;

void main(){

int i, x, y;

int p1, p2;

int gr[N][N] = {

{0,5,3,0,0,0,0},

{5,0,4,6,2,0,0},

{3,4,0,5,0,6,0},

{0,6,5,0,6,6,0},

{0,2,0,6,0,3,5},

{0,0,6,6,3,0,4},

{0,0,0,0,5,4,0}

};

e_cnt = 0;

for(y=0; y<N; y++){

for(x=0; x<N; x++){

if(gr[y][x] > 0){

edge[e_cnt].v1 = y;

edge[e_cnt].v2 = x;

edge[e_cnt].w = gr[y][x];

e_cnt++;

}

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

printf("%d-v2(%d)\n",edge[i].v1, edge[i].v2, edge[i].w);

}

인접 리스트 기반의 그래프 완성 버전 : S014_ListGraph.c

..

1

..
깊이 우선 탐색(Depth First Search; DFS) 완성버전 : S014_GraphDFS.c

...

1

...
너비 우선 탐색(Breadth First Search; BFS) 완성버전 : S014_GraphBFS.c

...

1

...
최소 비용 신장 트리(Minimum Cost Spanning Tree; MST) 완성버전 : S014_GraphKruskal.c

...

1

...

whan0623

517