Tree & Graph, 비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (10)

트리와 그래프

Review: 트리란?

트리는 서로 연결된 노드들로 구성되어 있다
두 노드 간에는 유일한 길(path)만 존재한다

이렇게 정의만 보면 와닿지 않죠. 트리 예시를 그려보았습니다. 

<트리? -> O>

<트리? -> X>

쉽게 말해 모든 노드들끼리 연결은 되어 있어야 하며, 대신 그 연결 방법이 유일해야 한다는 것입니다. 

그래프(graph)란?

그래프는 노드와 엣지(edge)로 구성되어 있다
엣지는 두 노드를 연결하는 선이며, 없어도 가능하다

위에 있는 모든 그림 및 아래 그림은 그래프라고 할 수 있습니다.(모든 트리는 그래프입니다)

<그래프? -> O>

단순 그래프(Simple Graphs)

단순 그래프는 다음의 2가지 특성을 가지지 않습니다. 여기선 단순 그래프만 우선 고려하겠습니다.

1. Loop: 노드는 자기 자신과 연결될 수 있다(엣지를 가진다) -> (v, v)
2. Parallel edge: 노드 간 2개의 엣지가 존재한다 -> e1=(v, w), e2=(v, w)

참고로 그래프에서 사용되는 용어들을 설명하겠습니다.

Vertex = v: 노드

Edge = (v, w): 엣지
- undirected(=line): 노드들 간 서로 방문 가능 -> undirected graph
- directed(=arrow): 한 노드에서 다른 노드로만 방문 가능 -> directed graph

Adjacent: 두 노드 간 "유일한" 엣지를 가지면 인접하다고 표현

Path = (v, w, y, z): 엣지들로 연결된 vertices의 시퀀스
- simple path = (v, w, y, z) <- non-repeated / not simple path = (v, w, y, v, z) <- repeated
- cycle = (v, w, y, v) <- the first and last vertices are the same
- cyclic graph: 싸이클이 있는 그래프 / acyclic graph: 싸이클이 없는 그래프

Connected: path가 존재하면 노드가 연결되었다고 표현

아래는 undirected graph를 생성하는 코드입니다. vertices와 edge가 모두 리스트 형태로 들어오고, neighbor라는 딕셔너리 안에 각 vertex의 이웃 노드를 리스트로 저장합니다.

class undi_graph():
    def __init__(self, V: list, E: list) -> None:
        # 모든 vertices 복사
        self.V = V[:]
        self.neighbor = {} # neighbor list 초기화
        for v in V:
            self.neighbor[v] = []
        for (v, w) in E:
            self.neighbor[v].append(w)
            self.neighbor[w].append(v)
            
V = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
E = [(0, 1), (1, 4), (1, 5), (4, 6), (5, 6), (5, 7), (6, 9), (7, 8), (2, 3)]

아래는 Preorder 방식으로 그래프를 순회하는 코드입니다. 다만, 트리에서 말한 Preorder와 100% 일치하진 않습니다. 과정은 아래 코드와 그림을 통해 설명하겠습니다. 또한, 이웃 노드가 2개일 때, 위에서 선언한 엣지 순서를 참고하여 우선 탐색합니다. 

일단 아래와 같은 그래프를 탐색한다고 합시다. 노드2와 3이 나머지 노드 그룹과 연결되지 않음에 주의해주세요.

class undi_graph():
    
    def __DFTHelp(self, visited: list, v: int) -> None:
        if not visited[v]: # 방문 기록이 False인 경우만
            visited[v] = True # 방문했음을 표시
            print(v)
            for w in self.neighbor[v]:
                self.__DFTHelp(visited, w)
        
    def DFT(self) -> None:
        if self.V:
            visited = {}
            for v in self.V: # 모든 방문 기록을 False로 초기화
                visited[v] = False 
            for v in self.V:
                self.__DFTHelp(visited, v) # disconnected 된 노드들도 방문해야 하기 때문에 for loop 사용

위 코드 실행 과정의 첫 단계는 바로 아래 그림과 같습니다. 모든 노드에 방문 기록은 False로 정해져있고, 이제부터 방문된 노드는 방문 기록을 남길 것입니다. 

그 다음 실행되는 코드를 적었고, 결과는 그림으로 나타냈습니다. 동작 단계라 node0이라 표시했지만, 사실 for 문이 돌아가고 있는 것임을 기억해주세요. 

# for v in self.V:
self.__DFTHelp(visited, node0)
                
if not visited[node0]:
    visited[node0] = True 
    print(node0)

#for w in self.neighbor[node0]:
self.__DFTHelp(visited, node1)

if not visited[node1]:
    visited[node1] = True 
    print(node1)

노드1은 이웃 노드를 2개 가지고 있는데요, 이때는 처음에 선언했던 엣지 순서를 참고합니다. (1, 4)가 (1, 5)보다 먼저 위치하기 때문에 노드1에서 노드4를 먼저 순회합니다. 단, (1, 4)를 먼저 순회하고 바로 (1, 5)를 순회하는 것이 아닙니다!! for 문이 계속 돌아가고 있습니다! 

#for w in self.neighbor[node1]:
self.__DFTHelp(visited, node4)
self.__DFTHelp(visited, node5)

if not visited[node4]:
    visited[node4] = True 
    print(node1)

self.__DFTHelp(visited, node6)

if not visited[node6]:
    visited[node6] = True 
    print(node6)

위의 과정을 반복하면 최종 출력값은 output: 0 1 4 6 5 7 8 9 2 3 입니다. 노드8이나 노드9처럼 막다른 노드에 다다렀을 때는 가장 안쪽의 for문이 종료되고, 그 다음 for문이 종료되다가 방문하지 않은 노드가 남아있다면 방문하는 것이고, 이웃 노드를 모두 방문했다면 그대로 for문을 종료시킵니다. 

(주의!!) 0 1 4 6 5 7 8 9 노드를 모두 방문한 것이 끝이 아닙니다. 왜냐하면 DFT 함수에 있던 마지막 for 문이 실행되고 있거든요. 

for v in self.V:
    self.__DFTHelp(visited, v)

# self.__DFTHelp(visited, node0) <- 끝
# self.__DFTHelp(visited, node1) <- 시작 
# self.__DFTHelp(visited, node2) <- 대기중...

각 노드를 시작점으로 두고 진행하면 이미 방문 기록이 있으면 그대로 종료되고, node2의 경우 방문 기록이 없기 때문에 다시 __DFTHelp() 함수를 돌리는 것입니다. 

아래는 Preorder가 아닌 Postorder로 그래프를 순회하는 코드입니다. print(v) 위치가 달라진 것에 주의해주세요. 

class undi_graph():
    
    def __DFTHelp(self, visited: list, v: int) -> None:
        if not visited[v]: # 방문 기록이 False인 경우만
            visited[v] = True # 방문했음을 표시
            for w in self.neighbor[v]:
                self.__DFTHelp(visited, w)
            print(v) # postorder은 자식 노드, 즉 최하위 노드부터 순회
        
    def DFT(self) -> None:
        if self.V:
            visited = {}
            for v in self.V: # 모든 방문 기록을 False로 초기화
                visited[v] = False 
            for v in self.V:
                self.__DFTHelp(visited, v) # disconnected 된 노드들도 방문해야 하기 때문에 for loop 사용

코드 실행 결과 output: 8 7 5 9 6 4 1 0 3 2 가 나옵니다. 

아래는 Breadth First Traversal 방법을 사용한 코드입니다. 같은 층의 모든 노드들을 먼저 방문하고 다음 층의 노드를 방문하게 되죠. 

class undi_graph():
    def BFT(self) -> None:
        if self.V:
            visited = {}
            for v in self.V:
                visited[v] = False
            q = deque([])
            
            for v in self.V:
                q.append(v)
                while q:
                    v = q.popleft() # FIFO 형식
                    if not visited[v]: # 방문하지 않은 경우만
                        visited[v] = True
                        print(v)
                        for w in self.neighbor[v]:
                            q.append(w)
                        print(q)

코드를 실행하면 output: 0 1 4 5 6 7 8 9 2 3 이 나옵니다. 이해를 돕기 위해 q도 마지막에 출력을 해보았는데요. 먼저 노드0을 방문하고, 이웃 노드인 1을 방문합니다. 이때 deque구조 q에는 노드1의 이웃 노드인 노드0, 4, 5가 들어가게 됩니다. 하지만 노드0은 방문 기록이 True기 때문에 무시하고 노드4와 노드5만 방문하는 것이죠.