[알고리즘] 그래프 관련 알고리즘 정리

DongJunKim99·2023년 7월 27일

포스트를 작성하게 된 계기
그래프 관련 알고리즘에는 다양한 알고리즘이 있다.

bfs

dfs

prim

kruskal

dijkstra

bellman-ford
위 알고리즘들이 그래도 코테 문제에서 흔히 등장하는 알고리즘들인 것 같은데, 지금까지는 dfs, bfs 문제들만 주로 풀어왔었기에, mst를 구하는 prim, kruskal과 최단 거리를 구하는 dijkstra, bellman-ford 알고리즘 문제들을 검색 없이는 해결하기 힘들었었고, 코테를 준비하는데 다양한 그래프 알고리즘들을 다룰 줄 알아야겠다는 필요성을 느꼈다.

BFS

너비 우선 탐색 알고리즘이다. 한 정점에서 퍼져나가는 방식으로 탐색을 진행한다. queue 자료구조를 사용해서 구현할 수도 있지만, 개인적으로는 두개의 리스트 구조를 이용하는 방식을 선호한다

void bfs() {
	List<Integer> currentNodes = new ArrayList<>();
    ~~~~ 
    while (!currentNodes.isEmpty()) {
    	List<Integer> temp = new ArrayList<>();
        for (int currentNode : currentNodes) {
        	for (int nextNode : canGo(currentNode) {
            	if (visited[nextNode] == 0) {
                	visited[nextNode] = 1;
                    temp.add(nextNode);
                }
            }
        
        }
    
    	currentNodes = temp;
    
    }

}

위와 같은 방식으로 bfs 탐색을 진행하는게 queue 자료구조를 사용하는 것보다 기억하기 쉬웠던 것 같다. 그리고 특정 노드가 시작 노드로부터 얼마나 떨어져있는지 같은 정보를 index 같은 변수 하나만 추가하면 바로 알 수 있다는 점도 문제 풀이에 도움됐었던 경험이 많아서 주로 bfs는 위와 같은 방식으로 코드를 작성하고 있다.

DFS

깊이 우선 탐색 방식이다. 미로 찾기 처럼 갈 수 있는 한 방향으로 계속 탐색하다가 더이상 탐색할 수 없는 지점을 맞이하면 되돌아오는 방식으로 탐색을 진행한다. dfs는 주로 재귀함수를 이용해서 구현하였다.


void dfs(int index) {
	if (visited[index] == 1) {
    	return;
    }
    visited[index] = 1;
    for (int nextNode : canGo(index)) {
    	dfs(nextNode);
    }

}

문제에 따라 조금씩 변형되긴하지만, 위와 같은 코드가 dfs 문제에 적용하는 가장 근본적인 코드인 것 같다.

kruskal

크루스칼 알고리즘은 MST를 만드는 알고리즘 중 하나이다.

MST란? minimum spanning tree로 n개의 정점을 가진 그래프가 있으면 n-1 개의 간선으로 이루어지면서 n개의 정점이 모두 연결된 tree 중에서 간선의 가중치 합이 가장 작은 tree를 의미한다.

MST를 만드는 알고리즘에는 kruskal, prim알고리즘이 존재하는데, kruskal은 greedy하게 간선을 선택하는 방식으로 진행된다.

크루스칼 알고리즘의 진행 방식은 다음과 같다.

간선을 가중치를 기준으로 정렬한다.
간선을 탐색하면서, 간선을 이루는 두 정점이 같은 그룹에 있는지를 판단한다.
- 같은 그룹에 있으면 사이클이 형성되면서 mst를 이룰 수 없다.
- 같은 그룹에 속하는지에 대한 판단은 union-find 알고리즘을 이용하면 쉽게 할 수 있다.
같은 그룹에 속하면 넘어가고, 같은 그룹에 속하지 않으면 간선을 mst에 추가하고, 두 정점을 union한다.