그래프
태그 :
- 개념
- 정점(Vertex)의 집합 V와 두 정점을 잇는 선분인 간선(Edge)의 집합 E로 이루어지는 도형
I. 그래프 (Graph)의 개요
가. 그래프의 정의
- 정점(Vertex)의 집합 V와 두 정점을 잇는 선분인 간선(Edge)의 집합 E로 이루어지는 도형
G1 = (V, E) V(G1) = {0, 1, 2, 3} E(G1) = {(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)} |
나. 그래프의 제한 사항
- 자기 자신을 향하는 간선을 없다. (no self loop)
- 중복된 간선을 허용하지 않는다. (no multigraph)
다. 그래프에 관련된 용어
용어 |
설명 |
|
한글 |
영어 |
|
완전 그래프 |
complete graph |
그래프에서 간선의 수가 최대인 그래프 |
인접 |
adjacent |
무방향 그래프에서 정점 a,b에 대하여 간선(a,b)가 있으면 정점a는 정점b에 인접(adjacent)하다고 한다. |
부속 |
incident |
무방향 그래프에서 정점 a,b에 대하여 간선(a,b)가 있으면 간선(a,b)는 정점a와 b에 부속(incident)하다고 한다. |
경로 |
path |
정점 a에서 정점 b로 가는 간선의 집합 |
경로의 길이 |
length of path |
경로 상에 있는 간선의 수 |
단순 경로 |
simple path |
경로 상의 정점이 중복되지 않는 경로 |
사이클 |
cycle |
단순 경로 중 경로가 다시 원점으로 돌아오는 경우 |
Ⅱ. 그래프의 표현
가. 인접 행렬 (adjacency matrix)
- 그래프를 이차원 행렬에 저장하는 방법으로서
- 무방향 그래프에서는 행렬이 대각선을 중심으로 대칭이다. |
||
⇒ |
나. 인접 리스트 (adjacency list)
|
||||
⇒ |
⇒ |
|||
#define MAX_VERTICES 50 struct list_node { int vertex; struct list_node * link; }; typedef struct list_node node; typedef node * node_ptr; node_ptr graph[MAX_VERTEX]; |
Ⅲ. 그래프의 탐색
가. 깊이 우선 탐색 (DFS : Depth First Search)
- 트리의 전위탐색 방법을 그래프에 적용한 것 - 자동차로 여행할 경우, 방문지가 있으면 무조건 방문하는 방법 (1) 하나의 노드를 택한다. (2) 노드를 방문하여 필요한 작업을 한 다음, 연결된 다음 노드를 찾는다. 현재 방문 노드는 스택에 저장하고, 2단계를 반복하면서 막히면 3단계로 간다. (3) 더 이상 방문할 노드가 없으면 스택에서 노드를 빼내 다음 노드를 찾아 2단계를 반복함. |
||
⇒ |
||
/* 정점 v에서 시작하여 그래프의 깊이 우선 방문 */ void dfs(int v) { node_ptr w; visited[v] = TRUE; /* 1 방문지 표시 */ printf(“%5d”, v); for(w = graph[v]; w; w = w->link) /* 2 연결리스트 탐색 */ if(!visited[w->vertex]) dfs(w->vertex); } |
나. 너비 우선 탐색 (BFS : Breath First Search)
- 트리의 레벨우선 탐색을 그래프에 적용한 것 - 자동차로 여행할 경우, 가까운 곳부터 방문하는 방법 (1) 하나의 노드를 택한다. (2) 노드를 방문하여 필요한 작업을 한 다음, 연결된 다음 노드를 찾는다. 노드들을 큐에 저장한다. 더 이상 방문할 곳이 없으면 3단계로 간다. (3) 큐의 맨 앞의 노드를 빼내 2단계를 반복한다. |
||
⇒ |
||
/* 정점 v에서 시작하여 그래프의 너비 우선 방문 */ void bfs(int v) { node_ptr w; queue_ptr front, rear; front = rear = NULL;/* initialize queue */ printf(“%5d”, v); visited[v] = TRUE; /* 1 방문지 기록 */ insert(&front, &rear, v); while(front) /* 2 방문지 있는 동안 반복 */ { v = delete(&front); for(w = graph[v]; w; w = w->link; if(!visited[w->vertex]) { printf(“%5d”, w->vertex); insert(&front, &rear, w->vertex); visited[w->vertex] = TRUE; }}} |