16. 그래프
선형자료구조 16.1 그래프 배열, 스택, 큐, 리스트를사용하여해결할수있다. 비선형자료구조 순환, 트리, 이진트리로복잡한문제를해결한다. 그래프 (graph) ; 인터넷과같은통신네트워크나고속도로나철도와같은교통네트워크에적합하다. 그래프 (graph) 링크에의해연결되어있는노드들로구성된구조이다. 노드를정점 (vertex) 이라고부르고, 링크를간선 (edge) 이라고부른다. 그래프는 V 와 E 가집합이고, E 의모든원소가 V 의두 - 원소부분집합일때쌍 G=(V, E) 로표현된다. V 의원소를정점이라고부르고, E 의원소를간선이라고부른다.
유럽인터넷연결망과동등한그래프
용어 그래프는노드의지리적인위치가중요하지않기때문에위상기하학 (topology) 이라고도한다. 정점의개수를그래프의크기 (size) 라한다. 경로의길이 (length) 는간선의개수 k이다. 모든정점이서로다른것이라면경로 p를단순경로라한다. 어떤정점이다른모든정점으로부터도달가능하다면, 이것을연결그래프라고한다. 그래프 G의연결요소 (connected component) G' 은최대연결서브그래프이다. 사이클 (cycle) 은하나의노드에서다시자기자신으로돌아오는경로이다. 단순사이클 (simple cycle) 은처음과마지막정점이같은사이클이다 사이클이없는그래프를비순환 (acyclic) 그래프라한다. 연결된비순환그래프를자유트리 (free tree) 라고부른다. 트리는특별한종류의그래프로보아야한다.
서브그래프 G' 을가지고있는그래프 G 4 개의요소를가지고있는그래프
에탄올을표현하는자유트리
16.2 인접행렬구현 - 그래프를저장하는두가지일반적인방법으로인접행렬 (adjacency matrix) 과인접리스트가있다. - 그래프를위한인접행렬은 boolean 원소의 2 차원배열이다 그래프와인접행렬
인접행렬을사용한그래프의저장 LISTING 16.1: Storing a Graph with an Adjacency Matrix 1 class Graph { 2 int size; 3 String[] vertices; 4 boolean[][] a; // adjacency matrix 5 6 public Graph(String[] args) { 7 size = args.length; 8 vertices = new String[size]; 9 System.arraycopy(args, 0, vertices, 0, size); 10 a = new boolean[size][size]; 11 } 13 public void add(string v, String w) { 14 int i = index(v), j = index(w); 15 a[i][j] = a[j][i] = true; 16 }
18 public String tostring() { 19 if (size == 0) return "{ }"; 20 StringBuffer buf = new StringBuffer("{" + vertex(0)); 21 for (int i = 1; i < size; i++) 22 buf.append("," + vertex(i)); 23 return buf + "}"; 24 } 26 private int index(string v) { 27 for (int i = 0; i < size; i++) 28 if (vertices[i].equals(v)) return i; 29 return a.length; 30 } 32 private String vertex(int i) { 33 StringBuffer buf = new StringBuffer(vertices[i] + ":"); 34 for (int j = 0; j < size; j++) 35 if ( a[i][j] ) buf.append(vertices[ j]); 36 return buf + ""; 37 } 38 }
Graph 클래스의테스팅 LISTING 16.2: Testing the Graph Class 1 class TestGraph { 2 public static void main(string[] args) { 3 Graph g = new Graph(new String[]{"A", "B", "C", "D", "E"}); 4 System.out.println(g); 5 g.add("a", "B"); 6 g.add("a", "C"); 7 g.add("b", "C"); 8 g.add("b", "D"); 9 g.add("c", "D"); 10 g.add("d", "E"); 11 System.out.println(g); 12 } 13 }
16.3 인접리스트구현 - 그래프를위한인접리스트는각정점당하나의리스트를가진연결리스트의배열이다. 그래프와인접리스트 11
인접행렬을사용한그래프의저장 Listing 16.3: Storing a Graph with an Adjacency List 1 class Graph { 2 int size; 3 List[] a; // adjacency list 5 public Graph(String[] args) { 6 size = args.length; 7 a = new List[size]; 8 for (int i=0; i<size; i++) 9 a[i] = new List(args[i]); 10 } 12 public void add(string v, String w) { 13 a[index(v)].add(index(w)); 14 a[index(w)].add(index(v)); 15 }
17 public String tostring() { 18 if (size == 0) return "{}"; 19 StringBuffer buf = new StringBuffer("{" + a[0]); 20 for (int i = 1; i < size; i++) 21 buf.append("," + a[i]); 22 return buf + "}"; 23 } 25 private int index(string v) { 26 for (int i = 0; i < size; i++) 27 if (a[i].vertex.equals(v)) return i; 28 return a.length; 29 } 13
31 private class List { 32 String vertex; Node edges; 35 List(String vertex) { this.vertex = vertex; } 39 public void add(int j) { edges = new Node(j, edges); } 43 public String tostring() { 44 StringBuffer buf = new StringBuffer(vertex); 45 if (edges!= null) buf.append(":"); 46 for (Node p = edges; p!= null; p = p.next) 47 buf.append(graph.this.a[p.to].vertex); 48 return buf + ""; 49 } 51 private class Node { 52 int to; Node next; 54 Node(int to, Node next) { 55 this.to = to; this.next = next; 56 } 57 } 58 } 60 }
16.4 너비우선탐색 그래프에서정점 A 로부터시작하여레벨순서순회 ( 알고리즘 11.1) 을적용시킨다고하자. A 에인접한두개의정점 (B 와 E) 은그래프가루트를 A 로하는트리라면 A 의자식이된다. 따라서레벨순서순회에서첫번째로방문하는세개의정점은 A, B, E 이다. 다음으로첫번째자식 B 의자식들을방문한다. 그것들은 B 와인접해야하는동시에 B 보다는 A 에서더멀리떨어져있어야하므로 C 와 F 가되고, 이렇게되면정점 E 는자식이없는상태가된다. 따라서 C 와 F 를방문하고, C 의자식인 D 와 H 로간다음, 마지막으로 F 의자식인 G 를방문한다. 따라서레벨순서순회는 A, B, E, C, F, D, H, G 의순서로정점들을방문한다.
16.4 너비우선탐색 위에설명한순회는항상지역적으로동작하기때문에 갈망알고리즘 (greedy algorithm) 이라고불린다. 너비우선탐색 (breadth-first search: BFS) 그래프에적용하기위해레벨순서순회알고리즘을일반화시킨것
너비우선탐색 (BFS) 알고리즘 너비우선탐색 (BFS) 알고리즘 - 입력 : 그래프 G=(V,E) 와최초정점 v V. - 출력 : BFS 순서로모든정점을가지고있는리스트 L. 1. 지역큐 Q와정점의출력리스트 L을초기화. 2. v를방문했다고마크하고 Q에삽입. 3. Q로부터 x를삭제하고 L에삽입. 4. x에인접한각각의정점 y에대해단계 5를반복. 5. 만일 y를아직방문하지않았다면, 이것을방문했다고마크하고 Q에삽입. 6. 만일 Q가공백이아니면, 단계 3으로이동.
너비우선탐색의수행과정 아래그래프에대해정점 A 에서시작하는경우, 알고리즘수행과정을살펴보자. 정점들은앞에서설명한것과같이 A, B, E, C, F, D, H, G 의순서로방문되는데, 이것은출력리스트 L 에삽입되는순서이다. 방문되는정점들이넓게퍼지기때문에 너비우선 이라는용어를사용한다. 이것은그림 16.10 을보면잘알수있다. 이것은방문된정점 ( 녹색으로표시 ) 의집합의경계상에있는정점들을각각방문하는일련의단계를통해진행된다. 이과정을통해방문되는마지막정점은시작정점인 A 로부터가장멀리떨어져있다.
16.5 신장트리 그래프를위한신장트리 (spanning tree) 그래프의모든정점을연결하는서브트리이다. 연결순환그래프가몇개의신장트리를갖는것은쉽게보일수있다. 아래오른쪽 ( 그림 16.10) 서브트리는왼쪽 ( 그림 16.8) 에보인그래프를위한신장트리이다. 신장트리의유용성 그림 16.1 에보인유럽인터넷연결망에서, 신장트리는하나의노드에서다른노드로가는유일한통신선을정의하고있다. 19
BFS 신장트리알고리즘 BFS 신장트리알고리즘 입력 : 그래프 G=(V,E) 와최초정점 v V. 출력 : G 를위한신장트리 T. 1. 지역큐 Q와정점의출력트리 T를초기화. 2. v를방문했다고마크하고 Q에삽입한다음, 그것을 T의루트로삽입. 3. Q로부터 x를삭제. 4. x에인접한각각의정점 y에대해단계 5를반복. 5. 만일 y를아직방문하지않았다면, 이것을방문했다고마크하고 Q에삽입한다음 x의다음자식으로 T에삽입. 6. 만일 Q가공백이아니면, 단계 3으로이동.
너비우선탐색과 BFS 신장트리 그림 16.11 BFS 신장트리
16.6 깊이우선탐색 정점 A 에서시작하여첫번째로만나는자식은정점 B 이고, 이것의첫번째자식은정점 C 가되고, 이것의첫번째자식은정점 D 가되고, 이것의첫번째자식은정점 H 가된다. 이런다음방문하는다음정점은마지막으로방문한부모가자식을더가지고있을경우다음자식이된다. 이것은부모 B 에갈때까지되추적 (backtrack) 되는데, 이것의다음자식은정점 F 가되고, 이것의첫번째자식은정점 G 가된다. 마지막으로정점 E 가 A 의두번째자식으로방문된다. 따라서완전한순회는 A, B, C, D, H, F, G, E 의순서로정점들을방문한다.
16.6 깊이우선탐색 각각의노드를역순 ( 오른쪽에서왼쪽 ) 으로처리하는 " 역 (reverse)" 전위순회라는것을제외하고는동일한프로세스를적용해보자. 이버전의순회는 A, E, F, G, B, C, H, D 의순서로정점을방문한다. 이것은알고리즘 16.1 에큐대신스택을사용한경우와정확하게일치하는데, 이것을깊이우선탐색 (depth-first search) 라고부른다.
깊이우선탐색 (DFS) 알고리즘 깊이우선탐색 (DFS) 알고리즘 입력 : 그래프 G=(V,E) 와최초정점 v V. 출력 : DFS 순서로모든정점을가지고있는리스트 L. 1. 지역스택 S 와정점의출력리스트 L 을초기화. 2. v 를방문했다고마크하고 S 에삽입. 3. S 로부터 x 를삭제하고 L 에삽입. 4. x 에인접한각각의정점 y 에대해단계 5 를반복. 5. 만일 y 를아직방문하지않았다면, 이것을방문했다고마크하고 S 에삽입. 6. 만일 S 가공백이아니면, 단계 3 으로이동.
깊이우선탐색의수행과정 그림 16.12 는이전과동일한그래프에대한수행과정을보이고있다. 출력리스트는 A, E, F, G, B, C, H, D 를가지고있는데, 이것은이전에살펴본역전위순회의경우와같다. 깊이우선 이라는용어는순회가다른시이퀀스를따라되추적되기전에정점들이갈수있는만큼깊이들어가는하나의시이퀀스를따라간다는사실을반영하고있다. 따라서, 첫번째시이퀀스 {A, E, F, G} 이되고, 다음시이퀀스는 {B, C, H, D} 가된다.
깊이우선탐색과 DFS 신장트리 그림 16.13 DFS 신장트리
순환깊이우선탐색 (DFS) 알고리즘 순환깊이우선탐색 (DFS) 알고리즘 입력 : 그래프 G=(V,E) 와최초정점 v V. 출력 : DFS 순서로모든정점을가지고있는리스트 L. 1. v 를방문했다고마크하고 L 에삽입. 2. v 에인접한각각의정점 y 에대해단계 3 을반복. 3. 만일 y 를아직방문하지않았다면, L=depthFirstSearch(G,y,L) 로설정.
16.7 가중치그래프 가중치그래프 (V, E) 가그래프이고, w:e R 은각각의간선 e E 에이간선의가중치 ( 비용또는길이 ) 라고불리는숫자 w(e) 를할당하는함수일때, 삼원소쌍 G=(V, E, w) 이다. 만일 p=(v0, v1, v2,, vk) 가가중치그래프의경로라고하면, 경로 w(p) 의가중치 ( 비용또는길이 ) 는경로상에있는모든간선들의가중치의합으로정의된다.
예 16.3: Air Mileages ( 비행거리 ) 남미도시간의비행거리
가중치그래프를위한인접행렬 30
가중치그래프를위한인접리스트 31
16.8 Dijkstra 의알고리즘 가중치그래프에서하나의정점으로부터다른정점으로가는최단경로를계산하는알고리즘 1959 년에 Edsger Dijkstra 는 e 가간선의개수이고 n 이그래프에있는정점의개수일때, O(e logn) 시간내에하나의정점에서다른각각의정점으로가는최단경로를찾는알고리즘을발견하였다. 이것은각각의정점에서 boolean visited 필드외에 prev 필드와 dist 필드등두개의필드를더필요로한다. prev 필드는시작정점으로부터최단거리에있는이전정점을가리키고, dist 필드는최단거리의길이를가지고있다. 또한, 이알고리즘은최소 dist 가가장높은우선순위를가지는정점들의우선순위큐를사용한다.
16.8 Dijkstra 의알고리즘 Dijkstra 의알고리즘은원형적 (prototypical) " 갈망 알고리즘이다. 이것은간선의가중치함수에의해제어되는수정된너비우선탐색을사용한다. 각각의반복에서, 이것은처음정점 v 에가장가까운미방문정점 x 를방문한다음, x 에인접한모든정점 y 의 y.prev 와 y.dist 필드를갱신한다.
dist[w] min{dist[w], dist[w] + cost[u][w]} visited v 0 v 1.. v n-1 If v i S, visited[i]=true If v i S, visited[i]=false dist
Dijkstra 의최단경로알고리즘 입력 : 가중치그래프 G=(V,E,w) 와최초정점 v0 V. 출력 : prev 와 dist 필드집합을가지고있는정점집합 V. 후조건 : 각각의정점 v V 에대해, prev 포인터에의해정의되는경로는 v0 에서 v 로가는최단경로이고, v.dist 는이것의길이가된다. 1. 모든정점 v v0 에대해 v.dist= 로설정 2. 모든정점들을방문할때까지단계 3-6 을반복. 3. x 를최소 dist 를가지는미방문정점으로설정하고, x 를방문했다고마크. 4. x 에인접한각각의미방문정점 y 에대해단계 5-6 을반복. 5. dy=x.dist+w(x,y) 로설정. 6. 만일 dy<y.dist 이면, y.dist=dy 와 y.prev=x 로설정. ( 더짧은경로가발견됨.)
Dijkstra 알고리즘의수행과정
Listing 16.4 : Dijkstra 알고리즘 public class WeightedGraph { Vertex start; private static class Vertex { private Object object; Edge edges; Vertex nextvertex; boolean done; int dist; Vertex back; } public String tostring( ) {... } void printpath( ) {... } private static class Edge { Vertex to; int weight; Edge nextedge; } Edge(vertex to, int weight, Edge nextedge) { this.to=to; this.weight=weight; this.nextedge= nextedge; } public String tostring( ) {... } public Weightedgraph(String[ ] args){ Vertex v = start = new Vertex(args[0]); for (int i=1; i<args.length; i++) { v = v.nextvertex = new Vertex(args[i]); v.dist = Integer.MAX_VALUE; // infinity } }
public void addedge(string vstring, String wstring, int weight) {...} public void findshortestpaths() { // implements Dijkstra s Algorithm... } public void printpaths() {... } public String tostring() {... } private Vertex find(object object) { // returns the vertex that contains the specified object:... } private Vertex closestvertex() { // returns the undone vertex with smallest dist field:... } }
16.9 다이그래프 (Digraphs) 다이그래프 (digraph) 방향그래프 (directed graph) 라고도함. 간선들이하나의방향을가지고있다. 공식적인정의는간선을두정점의무순서집합이아니라두정점의시이퀀스로정의한다. 가중치다이그래프 (weighted digraph) 는각각의방향간선에숫자를할당하는가중치함수를가지는다이그래프이다. 가중치다이그래프를네트워크 (network) 라고부른다. 40
가중치다이그래프 세가지종류의그래프를생각해볼수있다. 1. 가중치가없는다이그래프 ( 가중치를무시 ), 2. 가중치그래프 ( 간선들이양방향이라고해석 ), 3. 그래프자신이다. 41
가중치다이그래프와내장구조 다이그래프와네트워크를저장하는데사용되는자료구조 인접행렬과인접리스트를사용한다. 다이그래프에서유일하게다른점은인접행렬이대칭일필요가없으며, 인접리스트는간선당두개가아니라하나의리스트노드만사용한다는것이다. 42
가중치다이그래프를위한인접행렬과인접리스트 그래프는여섯개의방향간선을가지고있으므로, 인접행렬은양의유한항목을여섯개가지고있고, 인접리스트는여섯개의노드만을가지고있다. 43