[go] 경로 순회

18 Dec 2023

이번에는 그래프에서 경로 순회 알고리즘에 대해 알아보겠습니다. 경로 순회는 그래프에서 한 노드에서 다른 모든 노드를 한 번씩 방문하는 것을 목표로 합니다. 이번 포스트에서는 가장 기본적인 그래프 순회 알고리즘인 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)에 대해 다루겠습니다.

깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)은 그래프를 탐색할 때 한 경로를 끝까지 탐색한 후, 다시 돌아와서 다른 경로를 탐색하는 방식입니다. 스택 또는 재귀 함수를 통해 구현할 수 있습니다.

예제 코드

package main

import "fmt"

type Graph struct {
	nodes map[int][]int
}

func (g *Graph) DFS(node int, visited map[int]bool) {
	if visited[node] {
		return
	}

	visited[node] = true
	fmt.Println("Visited node:", node)

	for _, neighbor := range g.nodes[node] {
		g.DFS(neighbor, visited)
	}
}

func main() {
	g := Graph{
		nodes: map[int][]int{
			1: {2, 3},
			2: {4},
			3: {5},
			4: {},
			5: {},
		},
	}

	visited := make(map[int]bool)
	g.DFS(1, visited)
}

너비 우선 탐색(BFS)

너비 우선 탐색(BFS)은 그래프를 탐색할 때 한 노드에서 시작하여 인접한 모든 노드를 우선 탐색한 후, 다음 노드로 이동하여 탐색하는 방식입니다. 큐를 사용하여 구현할 수 있습니다.

예제 코드

package main

import "fmt"

type Graph struct {
	nodes map[int][]int
}

func (g *Graph) BFS(startNode int) {
	visited := make(map[int]bool)
	queue := []int{startNode}

	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		if !visited[node] {
			fmt.Println("Visited node:", node)
			visited[node] = true

			for _, neighbor := range g.nodes[node] {
				if !visited[neighbor] {
					queue = append(queue, neighbor)
				}
			}
		}
	}
}

func main() {
	g := Graph{
		nodes: map[int][]int{
			1: {2, 3},
			2: {4},
			3: {5},
			4: {},
			5: {},
		},
	}

	g.BFS(1)
}

마치며

이상으로 경로 순회 알고리즘에 대한 간단한 소개를 마칩니다. DFS와 BFS는 다양한 그래프 탐색 문제에 유용하게 활용될 수 있는데요. 다음 번에는 더 복잡한 그래프 알고리즘에 대해 알아보도록 하겠습니다. 감사합니다!

참고 문헌

Skiena, S. S. “The Algorithm Design Manual.” Springer, 1997.