정용이의 놀이동산

개요 시작 노드에서부터 다른 모든 노드로 가는 최단 경로를 계산하는 알고리즘이다. 길이가 '음수인 사이클'을 포함하지 않는 모든 그래프에서 최단 경로를 구할 수 있다. 음수인 사이클이 그래프에 존재하는지 파악할 수 있다. 구현 각 노드의 초깃값을 설정한다. 시작 노드는 0, 다른 모든 노드는 INF(무한대)이다. n-1번의 라운드를 돌며 매 라운드마다 모든 노드에 걸쳐 경로를 최소화한다. 라운드를 n회 돌아서 n회째에서도 경로 단축이 이뤄지면 음수 사이클이 존재한다고 판단한다. 해당 경로가 음수 사이클을 형성하고, 시작 노드가 INF이면 불가능한 경로의 계산이 진행되므로 주의해서 처리한다. n-1회의 라운드 동안 매회 m개의 간선을 처리하기 때문에 시간복잡도는 O(nm)이다. Java int INF = ..

개요 시작 노드에서부터 거리가 증가하는 순서대로 다른 노드를 방문하는 알고리즘이다. 노드 방문이 그래프의 여러 부분에 걸쳐서 진행되기 때문에 DFS보다 구현하기가 어렵다. 구현 방문 예정인 노드들을 관리할 큐를 사용해서 구현한다. 인접리스트를 사용하면 구현하기 쉽다. 노드가 n개, 간선이 m개 존재하는 BFS의 시간복잡도는 O(n+m)이다. Java Queue q; boolean[] visited; int[] dist; ... void bfs(int x) { dist[x] = 0; q.offer(x); visited[x] = true; while(!q.isEmpty()) { int current = q.poll(); // 현재 위치에서 처리할 작업을 구현한다. foreach(Integer i : adjL..

개요 그래프의 간선을 따라가며 도달 가능한 모든 노드를 처리하는 알고리즘이다. 새로운 노드가 발견되는 동안 단일한 경로를 따른다. 알고리즘을 진행하며 방문한 노드를 기록하기 때문에 각 노드는 한 번씩만 방문된다. 구현 재귀(Recursive)를 이용하여 쉽게 구현할 수 있다. 그래프를 인접리스트로 표현하면 편하다. 노드가 n개, 간선이 m개 존재하는 DFS의 시간복잡도는 O(n+m)이다. Java List[] adjList; boolean[] visited; ... void dfs(int n) { if(visited[n]) { return; } visited[n] = true; // 이 부분에서 현재 방문한 노드에서 할 작업을 수행 foreach(Integer i : adjList[n]) { dfs(i)..