그래프와 관련 알고리즘(DFS,BFS)

1. Graph란?

: 일련의 노드(Vertex) 집합 V와 간선(Edge) 집합 E로 구성된 자료구조의 일종이다. 일반적으로 Vertex에는 데이터가, Edge에는 Vertex와 Vertex 사이의 관계 정보가 포함되어 있다.

 

2. Graph가 사용되는 예시

-> 문제를 풀기 위해 이를 자료구조로 만들어 컴퓨터가 이해할 수 있도록 해야 한다.

 

 1) Airline Routes 

 -> 이 graph의 각 vertex는 공항 이름이고, 간선이 존재하면 항공 노선이 존재한다는 것이다.

 

Q) 가장 비행기를 덜 갈아탈수 있는 노선은?

- 최단 거리 노선을 탐색하면 된다. (중간 경유지를 최소화함)

: 이는 BFS를 이용해 해결할 수 있다.

 

 

 

 

 

 

 

2) FlowChart

 : 순서도 자체가 그래프라고 할 수 있다.

-> 방향성이 있는 그래프로 바꿀 수가 있다.

: 이를 Digraph라고 한다.

 

 

 

 

 

 

 

 

 

 

3) Binary Relation

: x가 y의 약수일때 x->y (outgoing edge) 로 향하는 그래프를 그린다.

 

 

 

 

 

 

 

 

 

 

4) Computer Networks

: 컴퓨터 네트워크, 교통망, 인적 네트워크등을 표시할 수 있다.

-> 만약 노드끼리 모두 연결하면서 최소비용으로 망을 설치하고자 할때 : Minimum Spanning Tree기법을 사용할 수 있다.

 

 

 

 

 

 

 

3. Graph의 종류

 

 1) Digraph, 유향 그래프 : G=(V,E)

- V는 vertices라고 불리는 정점의 집합이며, E는 V의 ordered pair의 집합이다. (노드와 노드 사이의 간선)

- Directed Edge (v,w)는 v->w 의 방향을 나타내며 v가 꼬리, w가 머리이다.

- E는 ordered pair이기 때문에 순서가 존재하며, (v,w), (w,v)는 서로 다른 집합이다.  간단하게 vw로도 표현가능하다.

 

2) Undirected Graph, 무향 그래프 : G=(V,E)

- 무향 그래프에서 E는 각각의 다른 정점을 잇는 unordered pair set을 의미한다.

- {v,w}는 Undirected Edge라고 명명되며, 순서가 존재하지 않아 vw, wv 모두 같은 그래프를 의미한다.

 

# Incident : 정점과 간선 사이의 관계를 의미한다. 정점 v가 간선 vw와 incident하다고 한다.

  Adjacent : 정점과 정점 사이의 관계를 의미한다.

 

 

3) Weighted Graph, 가중치 그래프: G= (V, E, W)

- W는 E를 input으로 넣으면 가중치를 리턴하는 함수이다.

- W(e)는 e의 가중치를 의미한다.

 

 

4. Graph Representation

: 그래프를 표현하는 방법에는 두 가지가 있다.

-> 대부분의 추상 자료형을 구현하는 방법은 배열, 연결 리스트 두 가지이다. 

  - 배열 : 한꺼번에 메모리를 할당함 

  - 연결 리스트 : 필요할때마다 동적으로 할당받음

: 각 자료구조의 특성을 잘 고려해서 필요한 자료구조를 선택해서 구현하면 됨.

 

1) Adjacency Matrix Representation

: Graph를 NxN matrix 형태로 표현한다

- 두 정점 사이에 간선이 존재하면 1, 존재하지 않으면 0으로 표현한다.

- Matrix에 정점을 추가& 삭제시 : W(n)=O(n^2) 시간이 걸린다.

- 장점 : 간선을 추가할때 index로 접근 가능하며, O(1) 시간이 걸린다. 

         : v. isAdjacentTo w - 두 정점이 인접한지 확인할때 O(1) 시간에 가능하다.

- 단점 : IncidentEdge를 구할 때 O(n)시간이 걸린다. n열을 모두 확인해야 함.

 

 

2) Array of Adjacencty lists representation

: Graph를 array와 list형태로 구현한다.

 

- 장점: incidentEdge를 구할때 효율적이다. 

- 단점 : 두 정점이 adjacent한지 구할때 v vertex에서 w vertex가 나올때까지 리스트를 따라가야 한다. = O(degree(v))

  EX) 만약 6-7 이 adjacent할때, 6의 incidentEdge가 4개, 7은 1개라면 Degree(인접한 노드 개수) 가 작은 vertex에서 찾는게 유리하다. 

 

Q) 왜 두가지 방법으로 구현하는가?

: 각 성능의 시간복잡도가 서로 다르기 때문에, 많이 쓰는 성능의 시간복잡도가 적은 방법을 선택하면 좋다.

 

 

- Example 1: weighted digraph일때

1) 인접 배열 : 해당 배열이 대칭이 아니므로 방향성이 존재한다. i->j로 연결될때 M[i][j]에 가중치를 표시한다.

2) 인접 리스트 : 각 array cell에 가중치를 추가해주면 된다.

 

- Example 2 : Incidence sequence for each vertex

 

: 일련의 vertex들이 인접할때, 각 간선을 edge object로 표현할 수 있다. 이 vertex와 edge사이를 잇는 reference를 하나 추가하는데, 이를 incidence sequence라고 한다.

 

: 간선에서 노드를 가리키고, 또 incidence sequence를 가리켜준다. 이는 간선 삭제를 용이하게 하기 위함이다.

 

 

 

 

 

 

 

 

- Example 3 : 2D-array Adjacency array

 

: 이번엔 matrix를 사용해서 edge와 vertex사이를 연결해준다.

: 해당 자료구조의 총 크기는 한 포인터의 크기가 4byte이므로 

-> 4n^2+ m* ( size of edge object)

-> 각 cell에 edge를 직접 저장하는 대신 공간 낭비를 줄일 수 있다.

: 각 matrix에는 edge object의 주소값이 존재한다.

 

 

 

 

 

 

 

 

 

5. Graph와 관련된 용어 

-  Subgraph 

 : 임의의 그래프 G=(V, E) 가 주어졌을때 Subgraph G'=(V',E')는 다음과 같은 조건을 만족해야 한다.

  - E'는 E의 부분집합이며, V'는 V의 부분집합이다.

 

-  Complete Graph

: 모든 정점 사이에 간선이 존재하는 그래프로, 이를 very dense하다고 한다.

: m = n(n-1)/2 = O(n^2) (m은 edge개수, n은 vertex 개수)

 

-  Adjacency Relation

: 정점-정점 사이가 인접할때 Adjacent하다고 한다.

 

-  path, simple path, reachable

 1) path: 연속된 edge들의 나열

 2) simple path : 경로 중에 어떤 정점들도 중복하여 지나가지 않는다.

 3) reachable:  정점 사이에 path가 존재한다.

 

- connected, strongly connected

1) Connected : 모든 정점들이 reachable할 때 사용하며, undirected graph에서 사용하는 용어이다.

2) Strongly Connected : connected와 동일한 의미로, directed graph에서 사용하는 용어이다.

 EX) 만약 A->B,A->C,B->C 이런식으로 연결되어있으면 모든 vertex가 서로에게 reachable하다고 보기 어렵다.

 

- Cycle, Simple cycle

1) Cycle: 출발점 = 도착점인 path

2) Simple Cycle : 한번 간 정점은 방문하지 않는 cycle

 

- Acyclic 

: Cycle이 존재하지 않는 그래프로, 여러 문제들이 효율적으로 풀리게 된다. EX) DAG

 

- Undirected forest

: 그래프 중에 Acyclic한 connected graph를 tree라고 불린다. 이 tree가 여러개 있는 graph를 forest라고 한다.

 

- Free tree, Undirected tree, Rooted Tree

 1) Free tree: root 개념이 없는 tree로, graph에선 root개념이 존재하지 않는다.

 2) Rooted Tree : root가 존재하지 않는 Tree. 

 

- Connected Component

  - 그래프는 여러개의 고립된 부분 그래프 (Isolated Subgraphs)로 구성될 수 있다.

  - 즉, 이 무향 그래프에서 서로 연결되어있는 maximal subgraph를 의미한다. (유향에선 Strongly가 붙음)

-> 연결 성분에 속한 모든 정점을 연결하는 경로가 있어야 하며, 다른 연결 성분에 속한 정점과 연결하는 경로가 있으면 안된다.

 

6. Traversing Graph

: Graph내에서 저장하고 있는 vertex들을 모두 방문할 수 있어야 한다. Tree,Graph는 이가 까다로워 알고리즘을 따로 필요로 한다. Graph 내에서 모든 vertex를 탐색하기 위해서 DFS/BFS를 사용한다.

 

1) DFS (깊이 우선 탐색, Depth-first search)

: Root 노드 (혹은 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

- 일단 갈수 있을 때까지 최대한 들어가봤다가 막히면 전 지점으로 돌아오는 strategy로, 미로 탐색과 비슷하다.

  : 단, 이미 탐색한 곳을 다시 가지 않고, 현재 위치를 기록하기 위해 표시를 해두는게 특징이다.

- 모든 노드를 방문하는 법을 찾고 싶을 때 사용하는 방법이다.

- DFS는 재귀적으로 동작하며, Stack을 사용하여 구현할 수도 있다.

 

- DFS이전에 초기화하는 시간 복잡도

: 모든 edge와 vertex를 unexplored 상태로 만들어야 한다. Adjacency list를 사용하면 O(n+m)이며, linear time이다.

 

 

- DFS의 과정

  1) vertex를 visit 처리한다

  2) 해당 vertex의 incident edge를 확인한다. 

  3) 반대편 정점이 visit되었는지 확인한다 - O면 해당 정점으로 간다, X 면 return한다.

: 일단 최대한 깊게 들어가는 strategy를 사용한다. dead end에 다다르기 전까지는 다음 vertex를 탐색하지 않음.

  4) 만약 root에 대한 모든 분기의 탐색이 끝난 경우엔, 탐색하지 않은 다음 정점으로 간다.

 

 

- DFS의 시간 복잡도 (Adjacency List일 때)

: 각 정점마다 degree의 v만큼 이동한다.

=> O(DFS)= ∑ 1+deg(V) = O(n+m) :즉, linear time 안에 처리가 가능하다. 

 

- DFS에서의 Edge 분류

 1) Tree edge : Unexplored Vertex로 가는 Edge

 2) Back Edge : Parent Vertex로 가는 edge

 3) Descendent Edge : 후손 Vertex로 가는 edge

 4) Cross Edge : 그 외의 Edge

 

 

 

 

 

 

- 파이썬으로 구현한 DFS

#Stack으로 구현한 DFS
def dfs(graph, start_node):
    stack, visited = list(), list()
    stack.append(start_node)

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack.extend(reversed(graph[node]))

    print(visited)


#재귀로 구현한 DFS
visited2 = []
def dfs2(graph, node):

    if node in visited2:
        return
    print(node)
    visited2.append(node)

    for i in graph[node]:
        dfs2(graph, i)


graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
dfs2(graph, 'A')
print(visited2)

 

 

 

2) BFS(너비 우선 탐색, Breadth-First Search)

BFS란, 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방식이다.

- 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 것이다.

- 즉, 깊게(Deep) 탐색하기 이전에 넓게 (Wide) 탐색하는 것이다.

- 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

 EX) Ashley와 Jamie 사이에 존재하는 관계를 찾을 때, BFS는 Ashley와 가까운 사이부터 탐색하므로 적합하다.

- BFS는 방문한 노드들을 차례대로 저장한 후 꺼낼 수 있는 자료구조인 Queue를 사용한다.

 

 

-BFS 과정

1) 초기 상태의 큐에는 시작 노드를 저장한다.

2) 큐의 가장 앞 vertex를 꺼내고, 그를 방문한다.

3) 해당 vertex에 incidentEdge들을 모두 호출한다.

   : edge에 대응하는 반대편 정점들이 차례로 방문하며 unexplored 상태인 노드들을 enqueue하고, visited 상태로 바꿔준다.

   : 만약 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다.

4) queue가 빌때까지 이 과정을 반복한다.

 

- BFS의 시간 복잡도

: 각 정점마다 degree의 v만큼 이동한다.

=> O(DFS)= ∑ 1+deg(V) = O(n+m) :즉, linear time 안에 처리가 가능하다. 

 

 

 

7. Strongly Connected Component Algorithm

 - Strongly Connected

: 유향 그래프에서 모든 정점 사이가 연결되어 있는 상태를 의미한다.

 

- Strongly Connected Component

: G의 Maximal Strongly Connected Subgraph(최대로 연결된 부분 그래프)를 의미한다.

-> 아래의 예시에선 서로가 reachable한 이상 전부 연결되어있어야만 S.C.C가 됨을 확인할 수 있다.

EX) G->D로 갈수는 있지만, D->G로 갈수 있는 방법이 없으므로 이 둘은 같은 subgraph내에 있을 수 없다.

 

-> 모든 정점이 Reachable 한 최대 연결 부분 그래프를 찾아야 한다. 어떤 방법으로 찾을 수 있을까?

 

- Strategy

: 이는 DFS를 두번 함으로써 찾을 수 있다.

Phase 1 : Standard DFS를 그대로 수행하고, 탐색이 끝난 정점들은 순서대로 Stack에 집어넣어둔다

 

Phase 2 : G를 Transpose한 그래프(edge의 방향을 바꾼 그래프)로 DFS를 수행한다.

1) Search를 시작하려면, Vertices 는 Stack으로부터 pop되어야 한다.

2) 모든 분기 탐색을 끝낸 뒤에 더이상 연결이 없으면 해당 그래프는 strongly connected component이다.

3) stack을 확인하여 unexplored vertex를 찾을 때까지 pop한다. (새로운 시작점 찾기)

 

def bfs(graph,start_node):
    queue,visited=list(),list()
    queue.append(start_node)

    while queue:
        node=queue.pop(0)
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])

    return visited
    

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']
bfsResult=bfs(graph,'A')