[자료구조] Graph

 

✅ 그래프의 정의 

그래프(G)는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조입니다.

 

V ( 정점들의 집합 )= { 정점1, 정점2, 정점3 ... }

E ( 간선들의 집합 )= { (1,2), (1,3), (2,3) ...  }

✅ 그래프의 활용

그래프는 이렇듯 연결 관계를 표현하기에 현실 세계의 사물이나 추상적인 개념들을 잘 표현 할 수 있다. 

그래프는 현실의 문제를 해결하기 위한 도구로서  유용하게 활용된다.

• 도시들을 연결하는 도로망: 도시(vertex), 도로망(edge) -> 네비게이션, 길찾기
• 지하철 연결 노선도: 정거장(vertex), 정거장을 연결한 선(edge)
• 컴퓨터 네트워크: 각 컴퓨터와 라우터(vertex), 라우터간의 연결 관계(edge)
• 소셜 네트워크 분석: 페이스북의 계정(vertex), follow 관계(edge)

✅ 그래프의 종류 

• 무향 그래프(undirected graph) : edge 양방향으로 이동 가능
• 방향 그래프(directed graph) : edge 이동 가능한 방향 정해져 있음. vertex 기준으로 자신에게 들어오는 edge는 indegree, 자신에게서 나가는 edge는 outdegree

 

✅ 그래프의 구현 방법 (인접 행렬 , 인접 리스트, 암시적 그래프 ) 

1. 인접 행렬 ( adjacency matrix )

각 vertex사이에 edge가 있으면 1, 없으면 0으로 표현함 

자기 자신과의 만남을 뜻하는 우하향 대각선은 항상 0이며,  대각선을 기준으로 양쪽으로 대칭이다.

-> 없는 간선(0)을 표현하기 위해 너무 많은 메모리를 소모하기에 거의 쓰이지 않는다. 

matrix = [
    [0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 1, 0],
    [0, 1, 0, 1, 0, 0],
    [0, 0, 1, 0, 1, 1],
    [0, 1, 0, 1, 0, 1],
    [0, 0, 0, 1, 1, 0],
]

 

 

 

2. 인접 리스트

딕셔너리(js의 Object) {} 형태로  정의된다. key 에는 vertex(정점)들이 들어가며 value에는 list 형태로 연결 관계를 표시한다. 

graph = {
    "A": ["B"],
    "B": ["A", "C", "E"],
    "C": ["B", "D"],
    "D": ["C", "E", "F"],
    "E": ["B", "D", "F"],
    "F": ["D", "E"],
}

 

 

3. 암시적 그래프 

길찾기 등과 같은 바둑판 무늬의 형태를 표현할 때에 각 칸을 Vertex로 생각하고 그래프와 비슷하게 표현한 암시적 그래프가 활용된다. 

아래와 같이 2차원 배열로 나타낸 후 벽이 있는 곳, 없는 곳을 각각 1, 0 으로 나타낸다면 각 칸이 정점이고 상,하,좌,우 의 칸 사이에 edge로 연결되어 있다고 상정한다면 그래프의 형태와 동일하게 생각할 수 있다. 

 

 

 

 

✅ 그래프 순회 : BFS , DFS

🔸 BFS breadth-First Search : 너비 우선 탐색 

트리의 BFS 순회와 거의 비슷하다. ( Level Order Traversal )

그래프 순회를 할 때 시작점이 주어지는데, 이를 루트노드라 생각하고 level별로 탐색하는 것이 BFS이다.  

from collections import deque

def bfs(graph, start_v):
    visited = [start_v]
    queue = deque(start_v)
    while queue:
        cur_v = queue.popleft()
        for v in graph[cur_v]:
            if v not in visited:
                visited.append(v)
                queue.append(v)
    return visited
    
graph = {
    "A": ["B"],
    "B": ["A", "C", "E"],
    "C": ["B", "D"],
    "D": ["C", "E", "F"],
    "E": ["B", "D",  "F"],
    "F": ["D", "E"],
}

bfs(graph, 'A') # return ['A','B','C','D','E','F']

 

 

 

🔸 DFS Depth-First Search : 깊이우선탐색

DFS는 stack과 재귀로 구현한다. 

graph = {
    "A": ["B", "D", "E"],
    "B": ["A", "C", "D"],
    "C": ["B"],
    "D": ["A", "B"],
    "E": ["A"]
}

visited = []
# graph와 visited를 전역변수로 놓았다고 가정하고 구현한다.

def dfs(cur_v):
    visited.append(cur_v)
    for v in graph[cur_v]:
        if v not in visited:
            dfs(v)	# visted안된 vertex라면 재귀로 dfs 진입
            
            
dfs( 'A' ) 

# dfs 이후 visited=['A','B','C','D','E']

 

 

✅ BFS와 DFS 시간 복잡도

각각의 순회는 모든 정점(V)들을 탐색해야 하고 그러기 위해서는 정점에 연결된 edge(E)들을 모두 확인해봐야 합니다. 따라서 BFS와 DFS 시간 복잡도는 O(V+E)이다.