그래프 알고리즘

 - 그래프란 정점(Vertex, 또는 Node)과 간선(Edge)으로 이루어진 자료구조이다. 네트워크 망이나 전철 노선도를 떠올리면 된다.

 - 유향 그래프와 무향 그래프가 있다. 유향 그래프는 간선에 방향이 있어서 간선의 방향으로만  갈수 있는 그래프이고, 무향 그래프는 간선에 방향이 없어서 양방향으로 갈수 있는 그래프이다.

 - 그래프 관련 알고리즘으로는 DFS(Depth First Search, 깊이 우선 탐색), BFS(Breadth First Search, 너비 우선 탐색), 다익스트라(Dijkstra) 알고리즘 등이 있다.

- DFS는 깊이 우선 탐색으로, 일단 간선을 따라서 방문하지 않은 정점을 방문한다. 방문할 이웃이 없으면, 다시 뒤로 돌아가서 다른 이웃 정점을 같은 방식으로 방문한다. 일단 깊게 들어간 뒤에 다시 나와서 탐색하기 때문에 깊이 우선 탐색이라고 한다.

 - BFS는 너비 우선 탐색으로, 일단 자기 주변에 방문할수 있는 정점을 모두 방문한다. 그 다음 방문한 정점을 하나 선택해서 다시 그 정점에서 방문할수 있는 정점을 방문한다. 깊게 들어가지 않고 한 단계씩 탐색하기 때문에 너비 우선 탐색이라고 한다.

 - 다익스트라(Dijkstra) 알고리즘은 한 정점에서 다른 정점으로 가기 위한 최소 비용(또는 거리)을 구하는 알고리즘이다. 알고리즘의 동작을 간략히 설명하자면

1. 시작 정점의 거리를 0으로 초기화 하고, 시작 정점부터 나머지 정점까지의 거리를 무한(적당히 큰 값)으로 설정한다.

2. 방문하지 않은 정점 중 최소 거리인 정점을 선택한다. (A 정점이라고 하자)

3. A 정점을 방문한 정보를 기록한다.

4. 선택된 정점에서 방문할수 있는 정점 (B 정점이라고 하자) 의 거리를 계산해서, A 정점을 거쳐서 가는게 더 가까울 경우에, B 정점의 거리를 갱신한다.

( 즉, '시작 정점 -> B의 거리' > '시작 정점 -> A의 거리 + A -> B의 거리'일 경우, B 정점의 거리를 '시작 정점 -> A의 거리 + A -> B의 거리'로 갱신한다.)

5. 모든 정점을 방문할 때까지 2, 3 과정을 반복한다.

말로 하니 좀 복잡해 보일수 있는데, 코드는 무척 단순하다.

 - 이제 위에서 설명한 알고리즘을 파이썬으로 구현한 코드를 공개하겠다.

 - 데이터 표현 방식

(그래프 이미지 참고 주소)

# 그래프에 저장되어 있는 정점의 리스트
nodeList = ["A", "B", "C", "D", "E", "F"]
 
# 딕셔너리를 이용해서 그래프를 표현
graph = {}
graph["A"] = {"B": 10, "C": 30, "D": 15}
graph["B"] = {"E": 20}
graph["C"] = {"F": 5}
graph["D"] = {"C": 5, "F": 20}
graph["E"] = {"F": 20}
graph["F"] = {"D": 20}

- DFS

# DFS
def dfs(graph, source):
    stack = [source]
    visited = dict((v, False) for v in graph)
    
    while stack:
        v = stack.pop()
        
        if visited[v]: continue
        
        visited[v] = True
        print v
        
        for neighbor in reversed(sorted(graph[v])):
            stack.append(neighbor)

- BFS

# BFS
def bfs(graph, source):
    queue = [source]
    visited = dict((v, False) for v in graph)
    
    while queue:
        v = queue.pop(0)
        
        if visited[v]: continue
    
        visited[v] = True
        print v
    
        for neighbor in sorted(graph[v]):
            queue.append(neighbor)

- Dijkstra

# Dijkstra
def dijkstra(nodeList, graph, source):
    visited = dict((node, False) for node in nodeList)
    prev = dict((node, None) for node in nodeList)
    distance = dict((node, sys.maxint) for node in nodeList)
    distance[source] = 0
    
    while any(visited[node] == False for node in nodeList):
        _, nowNode = min((distance[node], node) for node in nodeList if visited[node] == False)
        
        for neighbor in graph[nowNode]:
            if distance[nowNode] + graph[nowNode][neighbor] < distance[neighbor]:
                distance[neighbor] = distance[nowNode] + graph[nowNode][neighbor]
                prev[neighbor] = nowNode
                
        visited[nowNode] = True
    
    for node in nodeList:
        path = [node]
        
        while prev[node] != None:
            path.append(prev[node])
            node = prev[node]
            
        print " -> ".join(reversed(path)), distance[path[0]]

- 전체 코드

# -*- coding: utf-8 -*-
 
import sys
import time
 
 
nodeList = ["A", "B", "C", "D", "E", "F"]
 
graph = {}
graph["A"] = {"B": 10, "C": 30, "D": 15}
graph["B"] = {"E": 20}
graph["C"] = {"F": 5}
graph["D"] = {"C": 5, "F": 20}
graph["E"] = {"F": 20}
graph["F"] = {"D": 20}
 
def dijkstra(nodeList, graph, source):
    visited = dict((node, False) for node in nodeList)
    prev = dict((node, None) for node in nodeList)
    distance = dict((node, sys.maxint) for node in nodeList)
    distance[source] = 0
    
    while any(visited[node] == False for node in nodeList):
        _, nowNode = min((distance[node], node) for node in nodeList if visited[node] == False)
        
        for neighbor in graph[nowNode]:
            if distance[nowNode] + graph[nowNode][neighbor] < distance[neighbor]:
                distance[neighbor] = distance[nowNode] + graph[nowNode][neighbor]
                prev[neighbor] = nowNode
                
        visited[nowNode] = True
    
    for node in nodeList:
        path = [node]
        
        while prev[node] != None:
            path.append(prev[node])
            node = prev[node]
            
        print " -> ".join(reversed(path)), distance[path[0]]
 
def dfs(graph, source):
    stack = [source]
    visited = dict((v, False) for v in graph)
    
    while stack:
        v = stack.pop()
        
        if visited[v]: continue
        
        visited[v] = True
        print v
        
        for neighbor in reversed(sorted(graph[v])):
            stack.append(neighbor)
 
def bfs(graph, source):
    queue = [source]
    visited = dict((v, False) for v in graph)
    
    while queue:
        v = queue.pop(0)
        
        if visited[v]: continue
    
        visited[v] = True
        print v
    
        for neighbor in sorted(graph[v]):
            queue.append(neighbor)
 
 
def main():
    start = time.time()
    
    for node in nodeList:
        dijkstra(nodeList, graph, node)
        print
    
    print time.time() - start
    
    print
    print "dfs"
    dfs(graph, nodeList[0])
    print
    print "bfs"
    bfs(graph, nodeList[0])
 
 
if __name__ == "__main__":
    main()