11. Graph

1. Graph

- 정점과 간선의 집합

2. Graph 의 종류

- Undirected Graph

- 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프

-

- Directed Graph

- 간선에 방향성이 포함되어 있는 그래프

-

3. Degree

- Undirected Graph

- 각 정점에 연결된 에지의 개수를 Degree라 한다

- Directed Graph

- 각 정점으로 나가는 간선의 개수를 Qutdegree라 하고 들어오는 간선의 개수를  Indegree라 한다.

4. 가중치 그래프와 부분 그래프

- 가중치 그래프

- 간선에 가중치 정보를 두어서 구성한 그래프를 

- 비가중치 그래프

- 모든 간선의 가중치가 동일한 그래프 

- 부분 그래프

- 본래의 그래프의 일부 정정 및 간선으로 이루어진 그래프

5. 그래프 구현하는 두 방법

- 인접 행렬 : 정방 행렬을 사용하는 방법

- 해당하는 위치의 value 값을 통해서 vertex간의 연결 관계를 O(1) 으로 파알할 수 있다. Edge개수와는 무관하게 V^2의 공간 복잡도를 갖는다.

- 인접 리스트: 연결 리스트를 사용하는 방법

- vertex의 인접 리스트를 확인해봐야 하므로 vertex간 연결되어있는지 확인하는데 오래 걸린다. 공간 복잡도는 O(E + V)이다

6. 그래프 탐색

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

- 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로 나아가는 방법으로 우선 탐색한다. 연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더 이상 연결되지 않은 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 확인한다. Stack 을 사용하면 쉽게 구현할 수 있다. 시간복잡도 O(V+E) vertex + edge

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


def dfs(graph, root):
    visited = []
    stack = [root]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack.extend(list(set(graph[n]) - set(visited)))

    return visited

print(dfs(graph, 'A'))


---------------------------------------

['A', 'C', 'F', 'E', 'B', 'D']

- 너비 우선 탐색(Breadth first search:BFS)

- 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. BFS에서는 Queue를 사용한다. 탐색을 시작하는 정점을 Queue에 넣는다 그리고 dequeue를 하면서 dequeue하는 정점과 간선으로 연결되어 있는 정점들을 enqueue한다. vertex들을 방문한 순서대로 queue에 저장하는 방법이다. 시간복잡도는 O(V+E) vertex + edge 

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


def bfs(graph, root):
    visited = []
    queue = [root]

    while queue:
        n = queue.pop(0)
        if n not in visited:
            visited.append(n)
            queue.extend(list(set(graph[n]) - set(visited)))

    return visited

print(bfs(graph, 'A'))

-------------------------------------

['A', 'B', 'C', 'E', 'D', 'F']

7. Minimum Spanning Tree(최소 신장 트리)

- 그래프 G의 spanning tree 중 edge weight의 합이 최소인 spanning tree를 말한다. 여기서 말하는 spanning tree란 그래프 G의 모든 vertex가 cycle이 없이 연결된 형태를 말한다.

8. Kruskal Algorithm

- 초기화 작업으로 edge 없이 vertex들만으로 그래프를 구성한다. 그리고 weight가 제일 작은 edge부터 검토한다. 그러기 위해선 edge set을 비내림차순으로 정렬 해야 한다. 그리고 가장 작은 weight에 해당하는 edge를 추가하는데 추가할 때 그래프에 cycle이 생기지 않는 경우에만 추가한다. 시간 복잡도 O(E log E)

graph = {
    "vertices": ['A', 'B', 'C', 'D'],
    "edges": [
        (10, 'A', 'B'),
        (15, 'C', 'D'),
        (20, 'D', 'A'),
        (12, 'A', 'C'),
        (18, 'C', 'B'),
    ]
}

table = graph["vertices"]


def make_set(vertices):
    e_dict = {}
    for i in vertices:
        e_dict.update({i: {"parent": i, "length": 0}})

    return e_dict


graph_table = make_set(table)


def find(edge):
    if graph_table[edge]["parent"] != edge:
        graph_table[edge]["parent"] = find(graph_table[edge]["parent"])

    return graph_table[edge]["parent"]


def union(u, v):
    root1 = find(u)
    root2 = find(v)

    if graph_table[root1]["length"] > graph_table[root2]["length"]:
        graph_table[root2]["parent"] = graph_table[root1]["parent"]
        graph_table[root2]["length"] += 1
    else:
        graph_table[root1]["parent"] = graph_table[root2]["parent"]
        graph_table[root1]["length"] += 1


def kruskal(graph):
    mst = []
    edges = sorted(graph["edges"])

    for edge in edges:
        weight, u, v = edge
        if find(u) != find(v):
            union(u, v)
            mst.append(edge)

    return mst


print(kruskal(graph))

--------------------------------

[(10, 'A', 'B'), (12, 'A', 'C'), (15, 'C', 'D')]

9. Prim Algorithm

- 초기화 과정에서 한 개의 verte로 이루어진 초기 그래프 A를 구성한다. 그리고 그래프 A 내부에 있는 verte로부터 외부에 있는 vertex를 사이의 edge를 연결하는데 그 중 가장 작은 weight의 edge를 통해 연결되는 verte를 추가한다. 이렇게 연결된 vertex는 그래프 A에 포한된다. 시간 복잡도 O(E log V)

from collections import defaultdict
import heapq

example_graph = {
    'A': {'C': 3, 'B': 2},
    'B': {'A': 2, 'C': 1, 'D': 1, 'E': 4},
    'C': {'A': 3, 'B': 1, 'F': 5},
    'D': {'B': 1, 'E': 1},
    'E': {'B': 4, 'D': 1, 'F': 1},
    'F': {'C': 5, 'E': 1, 'G': 1},
    'G': {'F': 1},
}

def prim(graph, start_point):
    mst = defaultdict(set)
    visited = [start_point]
    edges = [(cost, start_point, to) for to, cost in graph[start_point].items()]
    heapq.heapify(edges)

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.append(to)
            mst[frm].add(to)
            for to_next, cost in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))

    return mst


print(prim(example_graph, 'A'))

-------------------------------------

defaultdict(<class 'set'>, {'A': {'B'}, 'B': {'C', 'D'}, 'D': {'E'}, 'E': {'F'}, 'F': {'G'}})