[자료구조] CH8. 그래프(그래프의 구조~그래프의 순회)

참조 : C로 배우는 쉬운 자료구조(이지영 저)

공부 날짜 : 21.03.10

 

<Section1> 그래프의 구조

 

1. 그래프의 개념

 그래프는 m:n 관계를 표현하는 비선형 자료구조이다.

객체를 나타내는 정점(Vertex)와 객체를 연결하는 간선(Edge)의 집합으로 구성된다. 

G=(V,E)

 

2. 그래프의 종류

 

 1) 무방향 그래프

  두 정점을 연결하는 간선에 방향이 없는 그래프이다.

  정점 Vi과 Vj를 연결하는 간선을 (Vi,Vj)라고 표현하고, (Vi,Vj)와 (Vj,Vi)는 같은 간선을 나타낸다. 

  그래프는 정점의 집합 V(G), 간선의 집합 E(G)를 사용해서 나타낼 수 있다. 

 

 2) 방향 그래프

  간선에 방향이 있는 그래프로 다이그래프라고도 한다. 

  정점 Vi에서 Vj를 연결하는 간선을 <Vi,Vj>로 표현한다. 이때 Vi가 꼬리(Tail), Vj가 머리(Head)이다. 

 

 3) 완전 그래프

  각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프이다. 

  정점이 n개일때, 무방향 그래프의 최대 간선 수는 n(n-1)/2개,

  방향 그래프의 최대 간선 수는 n(n-1)개이다. 

 

 4) 부분 그래프

  원래 그래프에서 정점이나 간선을 일부 제외한 그래프

 

 5) 가중 그래프

  정점을 연결하는 간선에 가중치를 할당한 그래프이다. 

  가중치 그래프 또는 네트워크라고도 한다. 

 

3. 그래프 관련 용어

 

 * 두 정점 Vi와 Vj가 연결되어 있는 간선 (Vi,Vj)가 있을 때

 1) 두 정점 Vi와 Vj는 인접(Adjacent)해 있다.

 2) 간선 (Vi,Vj)는 정점 Vi와 Vj에 부속(Incident)되어 있다.

 3) 정점에 부속되어 있는 간선의 수를 차수(Degree)라고 한다. 

 

 * 방향 그래프일 때

 4) 정점을 머리로 하는 간선 수는 진입 차수(In-degree)

 5) 정점을 꼬리로 하는 간선 수는 진출 차수(Out-degree)

 6) 정점의 차수는 진입 차수 + 진출 차수

 

 * 그래프 공통 

 7) 간선을 따라갈 수 있는 길을 순서대로 나열한 것은 경로(Path)라고 한다. 

 8) 경로를 구성하는 간선 수는 경로 길이(Path Length)이다. 

 9) 모두 다른 정점으로 구성된 경로는 단순 경로(Simple Path)이다.

 10) 경로의 시작 정점과 마지막 정점이 같은 경로를 사이클(Cycle)이라고 한다. 

 11) 방향 그래프이면서 사이클이 없는 그래프를 DAG(Directed Acyclic Graph)라고 한다.

 12) 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프를 연결 그래프라고 한다.

 13) 연결되지 않는 정점이 있는 그래프를 단절 그래프라고 한다. 

 

<Section2> 그래프의 구현

 

1. 순차 자료구조를 이용한 그래프의 구현 : 인접 행렬

 정점 수에 대한 정방 행렬을 사용한다. 

 정점을 n개 가진 그래프는 n*n정방 행렬을 만들어준다. 

 두 정점이 인접되어 있으면 정점을 나타내는 행과 열에 대한 행렬값을 1, 인접되어 있지 않으면 0으로 한다. 

 

2. 연결 자료구조를 이용한 그래프의 구현 : 인접 리스트

 노드는 정점을 저장하는 필드와 다음 인접 정점을 연결하는 링크 필드로 구성한다. 

 어떤 정점의 연결 리스트는 그 정점에 그 정점에 인접한 정점의 수만큼 , 그 정적의 차수만큼 노드가 연결되어 있다. 

 정점에 대한 인접 리스트의 헤드 포인터는 정점 개수만큼 필요하다. 

 간선 삽입을 진행할 때는 삽입이 일어날 때마다 인접 리스트의 첫 번째 노드로 삽입한다.

 

<Section3> 그래프의 순회

 

1. 그래프 순회의 개념과 종류

 한 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하는 것을 그래프 순회 또는 그래프 탐색이라고 한다. 

 

2. 깊이 우선 탐색(DFS:Depth First Search)

 

 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속하여 결국 모든 정점을 방문하는 순회 방법이다.

 후입선출의 스택을 사용한다!

 

DFS(v) //정점 v에 대한 깊이 우선 탐색

 

     for (i ← 0; i<n;i←i+1) do{

         visited[i]←false;

      } // visited배열에 모든 인덱스에 방문하지 않았다는 의미로 false를 초기화해줌

 

      stack ← createStack();

      visited[v] ← true;

      v 방문; // 시작 정점

 

      while (not isEmpty(stack)) do { //공백 스택이 될 때까지 반복

          if (visited[v의 인접 정점 w] = false) then { //인접 정점w를 아직 방문하지 않았을 때

              push(stack,v); // 정점 v를 push

              visited[w] ← true;

              w 방문;

              v←w;

          }

          else v ← pop(stack); //이미 w를 방문했으면 pop하고 정점을 반환하여 v에 저장한다. 

      }end DFS()

 

3. 너비 우선 탐색(BFS: Breadth First Search)

 

 가까운 정점을 먼저 방문하고 멀리 있는 정점을 나중에 방문하는 순회 방법이다. 인접한 정점에 대해 차례로 다시 너비 우선 탐색을 반복해야 하므로 탐색 과정에서 정점 순서를 관리하기 위해 선입선출의 구조를 갖는 큐를 사용한다.

 

 BFS(v) //시작정점을 v로 하는 너비 우선 탐색

 

     for (i ← 0;i < n;i ← i+1) do {

         visited[i] ← false;

     } // visited배열에 모든 인덱스에 방문하지 않았다는 의미로 false를 초기화해줌

 

     Q ← createQueue(); // 공백 큐 생성

     visited[v] ← true; 

     v 방문; //시작정점

 

     while (not isEmpty(Q)) do {

           while (visited[v]의 인접 정점 w] = false) do {

                visited[w] ← true;

                w방문; //정점 v의 인접정점 w를 방문

                enQueue(Q , w); //방문 후 큐에 삽입

           }

           v ← deQueue(Q); //이미 인접 정점을 방문 하였으면 deQueue를 통해 반환된 원소를 v에 저장

     } //큐가 공백이 될 때까지 반복

 end BFS()