그래프 (Graph)

그래프란?

그래프는 정점(Vertex)와 간선(Edge)의 모음이다.

G = (V, E)

그래프의 표현

인접 행렬과 인접 리스트가 있다.

예시 그래프

 

- 인접 행렬 (Adjacency Matrix)

	1	2	3	4	5
1	0	1	1	1	1
2	1	0	1	0	1
3	1	1	0	0	0
4	1	0	0	0	1
5	1	1	0	1	0

장점: 정점 간의 인접 관계를 빠르게 알 수 있다.

단점: 메모리를 인접 이스트에 비해 많이 차지한다.

 

- 인접 리스트 (Adjacency List)

정점	인접 정점
1	2,3,4,5
2	1,3,5
3	1,2
4	1,5
5	1,2,4

장점: 인접 행렬에 비해 메모리를 적게 차지한다.

단점: 정점 간의 인접 관계를 순차 탐색으로 알아내야 한다. 

깊이 우선 탐색 (Depth first search)

깊이 우선 탐색은 그래프에서 정점을 탐색할 때, 형제와 자식이 있으면 자식부터 탐색하는 방법이다.

예시 그래프에서 깊이 우선 탐색을 하면 1 2 3 5 4순서로 방문하게 된다.

 

프로그램으로 구현하려면 스택을 사용해서 구현하거나 재귀적으로 구현할 수 있다.

스택으로 구현은 인접리스트 또는 인접행렬, 스택, 방문된정점리스트 세가지가 필요하다.

재귀적으로 구현은 인접리스트 또는 인접행렬, 방문된정점리스트 두가지가 필요하다.

# dfs.py
# 인접리스트
adjacencyList = {
    1:[2,3,4,5],
    2:[1,3,5],
    3:[1,2],
    4:[1,5],
    5:[1,2,4]
}

def dfs_stack(adjacencyList, start):
    visitedVertex = set()
    stack = []
    stack.append(start)
    while True:
        if len(visitedVertex)==5:
            break
        #pop하고 방문정점리스트에 추가
        vertex = stack.pop()
        visitedVertex.add(vertex)
        print(vertex, end=' ')
        #스택에 방문 안한것들 추가
        for x in adjacencyList[vertex]:
            if not (x in visitedVertex):
                stack.append(x)
    print()

visitedVertex = set()
def dfs_recursive(adjacencyList, vertex):
    # 방문한 정점이면 종료
    if vertex in visitedVertex:
        return
    # 자기자신 출력, 방문리스트에 추가
    print(vertex, end=' ')
    visitedVertex.add(vertex)
    # 인접한 정점마다 재귀적으로 함수 실행
    for x in adjacencyList[vertex]:
        dfs_recursive(adjacencyList,x)

dfs_stack(adjacencyList, 1)
dfs_recursive(adjacencyList, 1)
print()

너비 우선 탐색 (Breadth first search)

너비 우선 탐색은 그래프에서 정점을 탐색할 때, 형제와 자식이 있으면 형제부터 탐색하는 방법이다.

 

프로그램으로 구현하려면 인접리스트 또는 인접행렬, 큐, 방문된정점리스트 세가지가 필요하다.

# bfs.py
# 인접리스트, 큐, 방문한정점리스트
from collections import deque
adjacencyList = {
    1:[2,3,4,5],
    2:[1,3,5],
    3:[1,2],
    4:[1,5],
    5:[1,2,4]
}
deq = deque()
visitedVertex = set()
deq.append(1)

while len(visitedVertex)!=5:
    # dequeue하고 방문정점리스트에 추가.
    vertex = deq.popleft()
    visitedVertex.add(vertex)
    print(vertex)
    # queue에 정점에 연결된 방문 안한것들 추가.
    for x in adjacencyList[vertex]:
        if not (x in visitedVertex):
            deq.append(x)

다익스트라 (Dijkstra) 알고리즘

다익스트라는 가중 그래프에서 노드 사이의 가장 짧은 길을 찾는 알고리즘이다. DP(동적 프로그래밍)을 사용한다.

프로그램으로 구현하려면 인접행렬, 방문된정점리스트, 최단거리리스트가 필요하다.

 

동작방식:

1. 출발 정점을 정한다

2. 출발 정점을 기준으로 최단거리 리스트와 방문한 정점 리스트를 만든다.

3. 방문하지 않은 정점중에서 기준점과 최단거리에 있는 정점을 선택한다.

4. 해당 정점을 거쳐가는 방법이 기존 방법보다 가깝다면 갱신한다.

5. 3~4번 반복

다익스트라 알고리즘 구현에 사용될 예시 그래프 - 출처: 안경잡이개발자

O(N^2)시간복잡도 코드

NUM = 6
INF = 1234567890
# 인접 행렬
g = [
    [0, 2, 5, 1, INF, INF],
    [2, 0, 3, 2, INF, INF],
    [5, 3, 0, 3, 1, 5],
    [1, 2, 3, 0, 1, INF],
    [INF, INF, 1, 1, 0, 2],
    [INF, INF, 5, INF, 2, 0]
]

def getSmallIndex(d, v):
    m = INF
    index = 0
    for i in range(NUM):
        if d[i] < m and v[i] == False:
            m = d[i]
            index = i
    return index

def dijkstra(start):
    # 최단 거리
    d = g[start]
    # 방문한 정점
    v = [False for x in range(NUM)]
    v[start] = True
    for x in range(NUM-2):
        index = getSmallIndex(d, v)
        for y in range(NUM):
            if d[y] > d[index] + g[index][y]:
                d[y] = d[index] + g[index][y]
        v[index] = True
    return d

print(dijkstra(0))