[자료구조] 11~14 주차 노트 (유향 그래프, BFS, DFS, 위상 정렬, 최소신장트리, Prim, Kruskal, Bellman-Ford, Floyd-Warshall 알고리즘)

KOCW에서 제공하는 고려대학교 유용재 교수님의 자료구조 강의를 수강한 후, 정리한 글입니다. 

http://www.kocw.net/home/cview.do?cid=b216fbe96107c9ea

 

 

주제

• 11주차 Graph의 뜻과 여러가지 구현 방법
• 12주차 Graph에 기반한 최적 Tree 산출
• 14주차 자료구조에서 알고리즘으로

 

# 그래프 구현

G = [[0,1,1,1],
    [1,0,1,0],
    [1,1,0,1],
    [1,0,1,0]]
    
print(G[3][2])

G = {
    0 : [1,2,3],
    1 : [0,2],
    2 : [0,1,3],
    3 : [0,2]
    }

# BFS
G = {
    0 : [1, 2],
    1 : [0, 2, 3],
    2 : [0, 1, 4],
    3 : [1, 4],
    4 : [2, 3, 5],
    5 : [4, 6],
    6 : [5]
    }
    
def BFS(graph, start_node):
    visit = list()
    queue = list()
    visit.append(start_node)
    queue.append(start_node)
    while len(queue) > 0:
        for node in graph[queue[0]]:
            if (node in visit) == False:
                visit.append(node)
                queue.append(node)
        del queue[0]
    return visit

print(BFS(G,5))​

# DFS

dfs_visit = list()

def DFS(graph, start_node):
    dfs_visit.append(start_node)
    for node in graph[start_node]:
        if (node in dfs_visit) == False:
            DFS(graph, node)
            
            
DFS(G, 4)
print(dfs_visit)

# topological sort 위상 정렬

def topol_sort(graph):
    while len(graph) > 0:
        for i in graph.keys():
            topol_check = True
            for j in graph.keys():
                if (i in graph[j]) == True:
                    topol_check = False
            if topol_check == True:
                print(i)
                del graph[i]
                break

topol_sort(G)

# week 12

# Prim Algorithm

# heapq : list as priority queue
from heapq import heappush
from heapq import heappop

def Prim(graph, graph_v, start_node):
    h = list()
    # To check vertex[i] is connected or not
    connect = list()
    for i in range(0, len(graph)):
        connect.append(False)
    
    # push (0, start) to heap h
    heappush(h, (0, start_node))
    # total cost
    total_weight = 0
    # connected vertex count
    vertex_count = 0
    
    while (vertex_count < len(graph)):
        # heappop = pop min value(cost)
        pop_info = heappop(h)
        pop_weight = pop_info[0]
        pop_node = pop_info[1]
        
        # if pop_node is not connected node
        if connect[pop_node] == False:
            connect[pop_node] = True
            total_weight = total_weight + pop_weight
            vertex_count = vertex_count + 1
            print("새로 연결된 곳 : ", graph_v[pop_node])
            print('누적 가중치 합 : ', total_weight )
            
            # renew weight 
            for i in range(0, len(graph)):
                if (graph[pop_node][i] != 0) and (connect[i] == False):
                    heappush(h, (graph[pop_node][i], i))

    
G = [[0,30,28,17,0],
    [30,0,0,42,0],
    [28,0,0,22,15],
    [17,42,22,0,19],
    [0,0,15,19,0]]
    
V = ['A','B','C','D','E']


Prim(G, V, 0)

# result
새로 연결된 곳 :  A
누적 가중치 합 :  0
새로 연결된 곳 :  D
누적 가중치 합 :  17
새로 연결된 곳 :  E
누적 가중치 합 :  36
새로 연결된 곳 :  C
누적 가중치 합 :  51
새로 연결된 곳 :  B
누적 가중치 합 :  81

# week 12

# Kruskal Algorithm


def kruskal(edges, vertexes):
    # O(1)
    edge_count = 0
    total_weight = 0
    
    # O(V)
    union = dict()
    for vertex in vertexes:
        union[vertex] = vertex
    
    # O(ElogE) = O(ElogV)
    edges.sort()
    
    # edge : (wieght, start_node, end_node)
    for edge in edges:
        if union[edge[1]] != union[edge[2]]:
            total_weight = total_weight + edge[0]
            edge_count = edge_count + 1
            print(edge[1] ,'과', edge[2], '가 연결되었습니다.')
            print('가중치 합은 ', total_weight)
            for vertex in vertexes:
                if union[vertex] == union[edge[2]]:
                    union[vertex] = union[edge[1]]
        if edge_count >= (len(vertexes)-1):
            break
        
E = [(30, 'A', 'B'),
    (28, 'A', 'D'),
    (17, 'A', 'C'),
    (22, 'D', 'C'),
    (42, 'B', 'C'),
    (19, 'C', 'E'),
    (15, 'D', 'E')
    ]
    
V = ['A','B','C','D','E']


kruskal(E, V)

# Kruskal result

D 과 E 가 연결되었습니다.
가중치 합은  15
A 과 C 가 연결되었습니다.
가중치 합은  32
C 과 E 가 연결되었습니다.
가중� 합은  51
A 과 B 가 연결되었습니다.
가중치 합은  81

# week 13

# Dijkstra Algorithm

from heapq import heappush
from heapq import heappop

def dijkstra(graph, graph_v, start_node):
    h = list()
    # To check vertex[i] is connected or not
    connect = list()
    for i in range(0, len(graph)):
        connect.append(False)
    
    # push (0, start) to heap h
    heappush(h, (0, start_node))
    
    
    while (len(h)>0):
        # heappop = pop min value(cost)
        pop_info = heappop(h)
        pop_weight = pop_info[0]
        pop_node = pop_info[1]
        
        # if pop_node is not connected node
        if connect[pop_node] == False:
            connect[pop_node] = True
            print(graph_v[start_node], '->', graph_v[pop_node], '최단 시간 : ', pop_weight)
            # renew weight 
            for i in range(0, len(graph)):
                if (graph[pop_node][i] != 0) and (connect[i] == False):
                    heappush(h, (pop_weight + graph[pop_node][i], i))

    
G = [[0,5,0,1,0],
    [0,0,5,4,0],
    [0,4,0,0,2],
    [0,3,0,0,0],
    [0,1,0,0,0]]
    
V = ['A','C','E','B','D']


dijkstra(G, V, 0)

# Dijkstra result

A -> A 최단 시간 :  0
A -> B 최단 시간 :  1
A -> C 최단 시간 :  4
A -> E 최단 시간 :  9
A -> D 최단 시간 :  11​

 

# week 13

# Bellman-Ford Algorithm

def bellman_ford(graph, graph_v, start_node):
    min_wight = list()
    for i in range(0, len(graph)):
        min_wight.append(float('inf'))
        
        min_wight[start_node] = 0
        on_node = [start_node]
        new_on_node = list()
    
    for round in range(1, len(graph)):
        for node in on_node:
            for i in range(0, len(graph)):
                if (graph[node][i] != 0):
                    new_weight = min_wight[node] + graph[node][i]
                    min_wight[i] = min(min_wight[i], new_weight)
                    new_on_node.append(i)
        on_node = new_on_node
        new_on_node = list()
    
    for i in range(0, len(graph)):
        print(graph_v[start_node], '->', graph_v[i], '최단 시간 : ', min_wight[i])


    
G = [[0,3,0,2,0],
    [4,0,0,-3,0],
    [0,5,0,0,3],
    [0,0,0,0,6],
    [0,-2,0,0,0]]
    
V = ['A','C','E','B','D']


bellman_ford(G, V, 0)

# Bellman-Ford result

A -> A 최단 시간 :  0
A -> C 최단 시간 :  3
A -> E 최단 시간 :  inf
A -> B 최단 시간 :  0
A -> D 최단 시간 :  6

# Week 13

# Floyd-Warshall Algorithm

def flydwarshall(graph, graph_v, start):
	# 불가능한 이동 inf 처리
    for i in range(0, len(graph)):
    	for j in range(0, len(graph)):
        	if (i != j) and (graph[i][j] == 0):
            	graph[i][j] = float('inf')
	
    # 모든 시작-끝에 경유 계산, 비교
	for mid in range(0, len(graph)):
		for start in range(0, len(graph)):
			for end in range(0, len(graph)):
				new_weight = graph[start][mid] + graph[mid][end]
                graph[start][end] = min(graph[start][end], new_weight)
 	
    # print
	for i in range(0, len(graph)):
    	for j in range(0, len(graph)):
      		print(graph_v[i], '->', graph_v[j], '최단 거리 : ', graph[i][j])

G = [[0, 30, 0, 20, 0],
        [40, 0, 0, -30, 0],
        [0, 50, 0, 0, 30],
        [0, 0, 0, 0, 60],
        [0, -20, 0, 0, 0]]

V = ['A', 'C', 'E', 'B', 'D']

flydwarshall(G, V, 0)

# result
'''
A -> A 최단 거리 :  0
A -> C 최단 거리 :  30
A -> E 최단 거리 :  inf
A -> B 최단 거리 :  0
A -> D 최단 거리 :  60
C -> A 최단 거리 :  40
C -> C 최단 거리 :  0
C -> E 최단 거리 :  inf
C -> B 최단 거리 :  -30
C -> D 최단 거리 :  30
E -> A 최단 거리 :  50
E -> C 최단 거리 :  10
E -> E 최단 거리 :  0
E -> B 최단 거리 :  -20
E -> D 최단 거리 :  30
B -> A 최단 거리 :  80
B -> C 최단 거리 :  40
B -> E 최단 거리 :  inf
B -> B 최단 거리 :  0
B -> D 최단 거리 :  60
D -> A 최단 거리 :  20
D -> C 최단 거리 :  -20
D -> E 최단 거리 :  inf
D -> B 최단 거리 :  -50
D -> D 최단 거리 :  0
'''