[알고리즘] 그래프의 기본 개념과 순회

1. 그래프란?

 

1) 그래프에서 사용되는 주요 용어

1] 인접, 부수

두 정점 x,y 사이에 간선이 있으면 정점 x와 y는 인접한다고 하며, 해당간선은 정점 x와 y에 부수되었다고 합니다.

2] 부분 그래프

원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프를 부분 그래프라고 합니다. 위 그림에서 G2는 G1의 부분 그래프라고 할 수 있습니다.

3] 경로

그래프에서 정점 v1으로부터 vn까지의 경로란 간선 (v1,v2), (v2,v3),....,(v(n-1),vn) 으로 연결된 v1,v2,...,vn을 의미하며 

이 때 경로상의 존재하는 간선의 개수를 경로의 길이라고 합니다.

4]차수

해당 정점에 부수된 간선의 수를 의미하며, 방향 그래프에서는 이러한 차수를 세분화하여 정점으로 들어오는 간선의 수를 진입차수라고 하고 그 정점에서 나가는 간선의 수를 진출차수라고 합니다.

5]단순경로

한 경로상에서 처음과 마지막 정점을 제외한 모든 정점이 서로 다른 경로를 의미합니다.

6]사이클

처음과 마지막 정점이 같은 단순경로를 의미하며 특히 사이클이면서 경로의 길이가 1인 경로를 루프라고합니다.

7]연결

무방향 그래프에서 서로 다른 정점 u,v의 모든 쌍에 대해서 u에서 v까지 경로가 있으면 그래프는 연결되었다고합니다. 방향 그래프의 경우에는 서로 다른 두 정점 u,v의 모든 쌍에 대해서 u에서 v로의 방향 경로와 v에서 u로의 방향경로가 존재하면 그 방향 그래프는 강력하게 연결되었다고 하고 그렇지 않으면 약하게 연결되었다고 합니다.

2) 그래프의 구현방법

3) 그래프 순회

그래프 순회란 그래프의 모든 정점을 체계적으로 한번씩 방문하는 것을 의미합니다.

 

1]  탐색 과정에서의 정점의 구분

2] 깊이 우선 탐색(DFS)

깊이 우선 탐색은 한 정점을 시작으로 매번 인접한 정점 중 한곳으로 이동하며 탐색하는 방법입니다.

 

깊이 우선 탐색은 스택구조를 사용해서 구현합니다. 

현재 정점에 인접한 정점이 없어서 더 이상 탐색을 진행할 수 없다면 거꾸로 되돌아가면서 아직 탐색하지 않은 인접한 정점을 찾아서 탐색을 진행합니다.

 

깊이 우선탐색의 처리과정은 아래와 같은 순서대로 진행합니다.

첫번째 시작정점을 스택에 삽입합니다.

두번째 스택의 top에 있는 정점에 대한 주변 정점이 존재하면 그 중 하나의 정점을 스택에 삽입하고 방문한 정점으로 처리합니다. 만약에 주변 정점이 없다면 스택의 top에 있는 정점을 제거합니다.

세번째 스택에 더 이상의 정점이 없을때까지 두번째과정을 반복합니다.

 

깊이 우선탐색의 알고리즘은 아래와 같습니다.

DepthFirstSearch(G,s){ // G: 입력 그래프, s: 시작정점
    Push(Stack,s);
    while(Stack != null){
      c = Stack의 top에 있는 정점;
      c.visted = true;
      정점C를 방문 정점으로 출력;
      do{
        for(v <- c의 모든 인접한 정점){
          if(v.visited == false)
            Push(Stack,v)후 while문으로 이동;
        }
          c = Pop(Stack);
      }while(Stack != null);
    }
  }

 

그림으로 예를 들면 아래와 같습니다.

 

DFS를 수행하는 과정에서 방문한 정점과 그때 사용된 간선으로 구성되는 트리를 깊이 우선 트리라고 합니다.

 

두번째 그림예제는 아래와 같습니다.

방문순서는 총 10가지가 나옵니다.

 

깊이 우선 탐색의 성능은 인접 리스트일 경우 O(정점의 개수+ 간선의 개수) 가 되며

인접행렬로 표현했을때는 O(정점의 개수의 제곱)으로 표현됩니다.

 

그리고 싶이 우선탐색은 아래 코드처럼 순환 알고리즘으로도 표현할 수 있습니다.

DFS_recursion(G,current){
    current.visited = true;
    방문정점으로 current 출력;
    for(next <- current의 모든 인접한 정점){
      if(next.visited == false)
        DFS_recursion(G,next);
    }
  }

 

3] 너비 우선 탐색

시작 정점을 기준으로 거리가 가장 가깝게 인접한 정점을 우선으로 모두 방문한 후 시작 정점과의 거리가 점점 멀어지는 순서로 인접 정점들을 탐색하는 방법입니다.

이때 거리란 시작 정점으로부터의 경로의 길이입니다.

너비 우선 탐색에서는 큐를 사용하여 주변 정점을 관리합니다.

 

너비 우선 탐색의 알고리즘은 아래와 같습니다.

BreadthFirstSearch(G,s){
    Enqueue(Queue,s);
    s.flag = true;
    while(Queue != null){
      c = Dequeue(Queue);
      정점 c를 방문 정점으로 출력;
      for(v <- c의 모든 인접한 정점)
        if(v.flag == false){
        Enqueue(Queue,v);
        v.flag = true;
        }
    }
  }

 

너비 우선 탐색의 예를 그림으로 확인해보겠습니다.

두번째 그림예제는 아래와 같습니다.

1의 주변 정점 2,4,6,7을 일렬로 나열하는 것과 같기 때문에 4!이 되어 24가지가 나타납니다.

 

4) 그래프 순회의 응용

1] 위상정렬

무사이클 방향 그래프에서 모든 간선이 한방향으로 향하도록 정점을 한줄로 나열하는 것을 위상정렬이라고 합니다.

 

이러한 위상정렬은 깊이 우선탐색을 활용하여 구합니다. 

즉 DFS를 수행하다가 더 이상 주변정점이 없어서 되돌아갈 때, 스택에서 삭제되는 정점을 역순으로 나열하면 됩니다.

 

예제를 그림으로 확인해보겠습니다.

5) 그래프의 연결성

1] 연결성분

무방향 그래프에서 임의의 두 정점간의 경로가 존재하는 최대 부분 그래프입니다.

이는 너비 우선 탐색 또는 깊이 우선 탐색을 활용하여 구합니다.

while(아직 탐색하지 않은 정점이 존재)
	탐색을 수행하다가 큐 또는 스택이 비게되면
    그때까지 탐색한 정점들을 하나의 연결성분으로 구성

2] 강연결성분

방향 그래프에서 임의의 두 정점 사이에 양방향의 경로가 존재하는 최대 부분 그래프를 강연결성분이라고합니다.

 

예제를 그림으로 표현하면 아래와 같습니다.