graph(2) - 그래프 구현 및 탐험

들어가기에 앞서

graph(1) - 그래프와 트리

이번 글에서는, 컴퓨터를 통해 그래프를 구현하는 방법과, 탐험하는 방법에 대해 알아보도록 하겠습니다.

그래프 구현

그래프와 트리에 대해 이해를 했습니다. 이젠 어떻게 구현하는지에 대해 python을 사용해서 이야기를 해보려고 합니다. 대부분의 언어가, 표준 라이브러리로 그래프를 지원하지 않습니다. 왜냐하면 그래프는 상황에 따라서 여러가지 방식으로 구현될 수 있기 때문입니다. 따라서, 어지간한 언어에서 지원하는 배열(리스트, vector.. 등)을 사용해, 2차원 배열으로 그래프를 구현합니다. 대표적인 방식은 인접 리스트, 인접 행렬, 간선 리스트가 있습니다.

아래의 그래프를 예시로 살펴보겠습니다.

인접 리스트

인접 리스트는, 정점의 번호를 index 삼아, 이를 기준으로 몇 번 정점이 연결되어 있는지를 살펴보는 방식입니다. 1번과 2번, 2번과 3번은 연결되어 있습니다.

그래프 탐험

그래프를 구현하는 방법에 대해 알았습니다. 그래프를 탐험(graph traverse)하는 방법에 대해 알아보겠습니다. 그래프를 탐험하는 방식에는 대표적으로 DFS, BFS가 있습니다. 앞의 하나의 알파벳만 다르다는 사실을 인지하고 아래에서 살펴보도록 하겠습니다.

DFS

DFS는 depth first search입니다. 한국어로 번역하면 깊이 우선 탐색이라고 할 수 있습니다. 하나의 정점을 기준으로, 그 정점으로 갈 수 있는 모든 정점을 탐험한 다음, 탐험하지 않은 정점에 대해 탐험하는 방식입니다.

간단하게, 하나를 기준으로 계속 내려갑니다. 그러고 더 이상 탐험할 곳이 없다면, 올라오는 방식입니다.

아래 그래프를 예시로 설명해보겠습니다.

시작 정점이 1번이라고 가정해보겠습니다.

백준 1260 - DFS와 BFS

백준 1260번 : DFS와 BFS 자세한 해설은 여기를 참조해주시길 바랍니다.

소스 코드

import sys
from collections import deque

n,m,v=map(int,sys.stdin.readline().split())
graph=[[] for _ in range(n+1)]
for _ in range(m) :
    v1,v2=map(int,sys.stdin.readline().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

for i in range(1,n+1) :
    graph[i].sort()
    graph[i].reverse()
    
#dfs
stack=deque()
visited=[False for _ in range(n+1)]
stack.append(v)
answer=[]
while stack :
    now=stack.pop()
    if visited[now] :
        continue
    visited[now]=True
    answer.append(str(now))
    for node in graph[now] :
        if visited[node]==False : #node를 방문하지 않았다면
            stack.append(node)
print(*answer)
answer2=[]
queue=deque()
visited=[False for _ in range(n+1)]
queue.append(v)
while queue :
    now=queue.popleft()
    if visited[now] :
        continue
    visited[now]=True
    answer.append(str(now))
    for idx in range(len(graph[now])-1,-1,-1) :
        node=graph[now][idx]
        if visited[node]==False : #node를 방문하지 않았다면
            queue.append(node)
print(*answer2)