[Coding Test][Python] Graph 개념 및 Graph 순회 예제

 

 

※ Grapn 란?

그래프 $G(V, E)$는 객체와 객체 간의 관계를 표현하기위한 자료구조이다. Graph는 객체를 표현하는 Vextex의 집합 V와 이들을 연결하는 Edge의 집합으로 구성된다.

 

 

그래프의 기본 구성요소

• Vertex(Node)
  • 그래프를 구성하는 기본 요소
  • 데이터의 단위를 표현한다
  • Vertex의 집합은 일반적으로 V로 표시한다
• Edge
  • 두 Vertex를 연결하는 선 또는 관계를 의미한다
  • 방향성, 가중치 등에 따라 다양한 특성을 가질 수 있다
  • Edge의 집합은 일반적으로 E로 표시한다

그래프의 종류

• Undirected Graph(무방향 그래프)
  • Edge에 방향이 없다. 즉, Vertex $u$와 $v$가 연결되어있다면, 서로 연결된 상태이다.
• Directed Graph(방향 그래프)
  • Edge에 방향이 있다. 즉, Edge ($u, v$)는 $u$에서 $v$로 연결되어 있음을 의미한다.
• Weighted Graph(가중치 그래프)
  • Edge에 가중치가 부여된 Graph이다
  • 가중치는 거리, 비용, 시간 등의 값을 나타낸다.
• Sub Graph(부분 그래프)
  • Graph $G = (V, E)$의 Vertex 및 Edge의 부분집합으로 구성된 Graph이다.
• Connected Graph(연결 그래프)
  • Undirected Graph에서 모든 Vertex가 하나의 경로로 연결된 Graph이다.
• Disconnected Graph(비연결 그래프)
  • 연결되지 않은 Vertex가 있는 Graph이다.
• Complete Graph(완전 그래프)
  • 모든 Vertex가 서로 연결된 Graph이다.
  • Edge의 수는 $\frac{n(n-1)}{2}$(Undirected Graph) 또는 $n(n-1)$(Directed Graph)이다.
• Cycle(사이클)
  • Graph 내에서 Vertex를 시작점으로 돌아오는 경로가 존재하는 Graph
• Acylic Graph(비순환 그래프) 
  • Cycle이 존재하지 않는 그래프
  • DAG(Directed Acyclic Graph)

그래프의 표현 방법

• Adjacency Matrix(인접 행렬)
  • $n x n$ 크기의 2차원 Matrix로 Graph를 표현한다.
  • Matrix의 값은 Edge의 존재여부를 나타낸다.
  • graph = [       
        [0, 0, 1, 0 ,1],        
        [0, 0, 0, 1 ,1],        
        [1, 0, 0, 0 ,1],        
        [0, 1, 0, 0 ,1],        
        [1, 1, 1, 1 ,1]     
    ]
• Adjacency List(인접 리스트)
  • 각 Vertex 마다 연결된 Edge의 Vertex의 List를 저장한다.
  • graph = {       
        1 : [3, 5],     
        2 : [4, 5],     
        3 : [1, 5],     
        4 : [2, 5],     
        5 : [1, 2, 3, 4]      
    }       
• Edge List(간선 리스트)
  • 모든 Edge를 List로 저장한다.
  • [(1, 3), (1, 5), (2, 4), (2, 5), (3, 1), (3, 5), (4, 2), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4)]
• Implicit Graph(암시적 그래프)
  • 명시적으로 모든 Vertex와 Edge를 저장하지 않고 State Space(상태 공간)을 기반으로 Graph를 정의하는 방식이다.
  • 예로 미로 찾기를 들 수 있다. 미로의 가능한 경로를 모두 저장하지 않고 현재 위치와 이동 가능한 방향만 고려한다. 즉, 위, 아래, 좌, 우로 Edge가 있다고 생각하면 된다.
  • matrix = [       
        [1, 1, 1, 1 ,1],        
        [0, 0, 0, 1 ,1],        
        [1, 1, 0, 1 ,1],        
        [1, 0, 0, 0 ,1],        
        [1, 1, 1, 1 ,1]     
    ]   

2. Grapn Traversal

1) Graph 표현

위의 그래프를 Adjacency List로 표현하는 방법입니다.

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

2) BFS(Breadth First Search)

Graph를 BFS로 탐색하는 코드 및 결과입니다.

Start Node를 "A"로 하여 현재 Vertex에서 연결된 Next Node들을 순차적으로 방문하는 것을 알 수 있습니다.

from collections import deque

def BFS(graph, start="A"):
    queue = deque()
    visited = dict.fromkeys(graph.keys(), False)

    queue.append(start)
    visited[start] = True
    print(start, end=' ')
    while queue:
        curr_node = queue.popleft()
        
        for next_node in graph[curr_node]:
            if visited[next_node] == False:
                queue.append(next_node)
                visited[next_node] = True
                print(next_node, end=' ')
                
BFS(graph, "A")

A B D E C

3) DFS(Depth First Search)

DFS는 Stack 또는 Recursion을 이용하여 구현할 수 있습니다.

# 스택을 사용한 DFS (Undirected Graph)
def dfs_stack(graph, start, visited=[]):
    stack = [start]  # 스택에 시작 노드를 넣음
    
    while stack:
        curr_node = stack.pop()  # 스택에서 노드 꺼냄

        if curr_node not in visited:
            visited.append(curr_node)     # 노드 방문 처리
            print(curr_node, end=' ')
            
            # 이웃 노드들을 스택에 추가 (방문하지 않은 것만)
            for next_node in graph[curr_node]:
                if next_node not in visited:
                    stack.append(next_node)

dfs_stack(graph, start="A", visited=[])

A E D B C

# Recursion을 이용한 DFS
def dfs_recursive(graph, start_node, visited):
    if start_node not in visited:
        print(start_node, end=" ")  # 방문한 노드 출력
        visited.append(start_node)     # 노드 방문 처리
        
        for next_node in graph[start_node]:
            if next_node not in visited:
                dfs_recursive(graph, next_node, visited)
                
dfs_recursive(graph, start="A", visited=[])

 

A B C D E

 

Stack을 이용한 DFS와 Recursion을 이용한 DFS의 결과가 다른데 이는 Stack은 LIFO 방식으로 명시적으로 Stack을 사용하여 현재 Vertex의 이웃을 역순으로 처리한다. 반대로 Recursion은 함수 호출 스택을 암묵적으로 사용하여 이웃 Node를 처음부터 탐색하색하기 때문이다. 따라서 Stack 기반의 DFS에서 next_node를 추가하는 순서를 역순으로 하면 해결가능하다.

def dfs_stack(graph, start, visited=[]):
    stack = [start]  # 스택에 시작 노드를 넣음

    while stack:
        curr_node = stack.pop()  # 스택에서 노드 꺼냄

        if curr_node not in visited:
            visited.append(curr_node)  # 노드 방문 처리
            print(curr_node, end=" ")

            # 이웃 노드들을 역순으로 스택에 추가
            for next_node in reversed(graph[curr_node]):
                if next_node not in visited:
                    stack.append(next_node)
                    
dfs_stack(graph, start="A", visited=[])

 

A B C D E