[파이썬] DFS와 BFS 1 - 그래프를 이중리스트로 나타내기

예제로 사용할 그래프

 우선, DFS와 BFS는 그래프를 순회하는 알고리즘이기 때문에 이 게시글에선 위 그래프를 예제로 사용하겠습니다.

 간단하게 알아보자면 DFS는 Depth First Search, 깊이 우선 탐색이며 BFS는 Breadth First Search, 너비 우선 탐색이라고 알아두시면 되겠습니다.

 

 탐색을 하려면 일단 그래프를 각 정점(vertex, v)들의 연결 상태를 나타내는 이중리스트(matrix)로 정의해야합니다.

준비된 매트릭스

 매트릭스는 위와 같이 생겼습니다. 정점들의 연결상태를 우선 파란 칸(연결됨), 빨간 칸(연결되지 않음)으로 나누어 색칠하겠습니다.

 먼저 자신이 자신과 연결되어있진 않으니 자신과 만나는 쌍을 전부 빨간색으로 색칠합니다.

만나는 쌍(1,1),(2,2),(3,3)...

 다음은 이어진 점들의 쌍을 파란색으로 색칠합니다. 단, 간선의 방향이 없는 그래프이므로 (1,2)가 이어져있다면 (2,1)도 파란색으로 칠해주어야 합니다.

 이렇게요. 빨간 대각선을 기준으로 대칭임을 알 수 있습니다.

 마지막으로 빈칸은 이어져있지 않음을 나타내므로 빨간색으로 색칠합니다.

 완성되었습니다. 정점 3을 예로 들자면 2, 4, 5, 6과 만나는 쌍이 파란색으로 칠해져있으니 이들과 연결되어있음을 알 수 있겠네요.

 이제 이걸 파이썬의 리스트를 이중으로 사용하여 옮겨줍니다. 단, 파이썬 리스트의 인덱스는 0번부터 시작하므로 칸을 7*7로 만들어 0번에 해당하는 쌍은 전부 0으로 채웁니다.

 이렇게 그래프를 이중리스트로 옮겨보았습니다.