22. 그래프(Graph)

그래프는 정점(노드)과 간선(링크, 에지)으로 구성됩니다. 

지도도 일종의 그래프라 할 수 있죠. 

각 마을은 정점, 도로가 간선. 

정점은 v1, v2 등으로 정의하며, 간선은 (v1, v2)와 같은 쌍으로 정의합니다. 

정점들은 무게나 비용 등의 가중치를 포함할 수 있습니다. 

 

방향성(유향) 그래프(directed graph, digraph)

간선에서 정점의 순서를 따집니다. 

화살표로 표시할 수 있습니다. 

무방향성(무향) 그래프

경로의 길이는 첫 번째 정점에서 마지막 정점까지의 간선의 수를 의미합니다. 

정점 자신으로 향하는 경로, 즉 루프도 경로에 포함되지만, 이때 루프의 길이는 0입니다. 

 

첫 번째 정점에서 마지막 정점까지의 (하나 이상의 간선으로 이루어진) 경로가 같은 경우를 사이클(cycle)이라고 합니다. 

정점이 반복되지 않는 경우는 단순(simple) 사이클, 반복되는 경우는 일반(general) 사이클이라 합니다. 

 

무향 그래프의 코딩

 

간선과 정점을 기록하는 것이 가장 큰 고민이 될 텐데요.

dictionary(딕셔너리)와 set(집합) 자료형을 조합합니다. 

딕셔너리는 키의 중복을 허용하지 않고, 집합도 요소의 중복을 허용하지 않기 때문에 

간선(또는 정점)을 중복 입력하더라도 자료형에서 정리해 줍니다. 

 

연결 리스트나 이진트리처럼 객체를 이용해 그래프를 만들고 싶으실 수도 있으시겠지만 효율적이지 못한 방법입니다. 

class Graph:
    def __init__(self):
        self.graph = {}  # 딕셔너리

    def add(self, v, w):
        if v not in self.graph:  # 키가 딕셔너리에 없는 지 체크
            self.graph[v] = {w}  # 딕셔너리에 'v: {w}'를 추가
        else:
            self.graph[v].add(w)
        if w not in self.graph:
            self.graph[w] = {v}
        else:
            self.graph[w].add(v)

    def show(self):
        for i in self.graph:
            print(i, '->', self.graph[i])

딕셔너리에 데이터를 넣으면서 키를 체크해야 할 때가 있습니다. 
defaultdict 또는 setdefault, get 등을 이용하면 간편히 처리할 수 있습니다. 

# setdefault 1

    def add(self, v, w):
        self.graph.setdefault(v, {w})
        self.graph[v].add(w)
        self.graph.setdefault(w, {v})
        self.graph[w].add(v)

# setdefault 2

    def add(self, v, w):
        self.graph.setdefault(v, set()).add(w)
        self.graph.setdefault(w, set()).add(v)

# get 1

    def add(self, v, w):
        self.graph[v] = self.graph.get(v, {w}).union({w})
        self.graph[w] = self.graph.get(w, {v}).union({v})

# get 2

    def add(self, v, w):
        self.graph[v] = self.graph.get(v, set()) | {w}
        self.graph[w] = self.graph.get(w, set()) | {v}

# defaultdict

class Graph:

    def __init__(self):
        from collections import defaultdict
        self.graph = defaultdict(set)

    def add(self, v, w):
        self.graph[v].add(w)
        self.graph[w].add(v)

추가 모듈을 쓰는 것은 좀 번거로운 것 같고.. 
get을 쓰면 더 짧게 쓸 수 있지만 가독성이 좋지 않은 것 같고..
저는 setdefault가 적당한 것 같습니다.

g = Graph()
g.add(0, 1)
g.add(0, 3)
g.add(1, 2)
g.add(2, 4)
g.show()

0 -> {1, 3}
1 -> {0, 2}
3 -> {0}
2 -> {1, 4}
4 -> {2}