그래프 순회 - Graph Traversal
목차
1. 그래프 순회에 대한 소개
2. 깊이 우선 그래프 (DFS) 순회
3. 재귀적 용법의 깊이 우선 그래프 (DFS) 소개
4. 재귀적 용법의 깊이 우선 그래프 (DFS) 솔루션
5. 반복적 용법의 깊이 우선 그래프 (DFS) 소개
6. 반복적 용법의 깊이 우선 그래프 (DFS) 솔루션
7. 넓이 우선 그래프 (BFS) 순회
8. 넓이 우선 그래프 (BFS) 소개
9. 넓이 우선 그래프 (BFS) 솔루션
1. 그래프 순회에 대한 소개
Graphs
A presentation created with Slides.
cs.slides.com
순회를 한다는건, 그래프에 있는 모든 정점(Vertex)를 방문한다는 말이다.
그래프 순회 사용 예시
1. Peer to peer networking
2. Web crawlers
3. Finding "closest" matches/recommendations
4. Shortest path problems
- GPS Navigation
- Solving mazes
- AI (shortest path to win the game)
2. 깊이 우선 그래프 (DFS) 순회
DFS ( Depth First Search ) : Explore as far as possible down one branch before "backtracking"
3. 재귀적 용법의 깊이 우선 그래프 (DFS) 소개
DFS 의사코드 ( Recursive )
DFS (vertex) :
if vertex is empty
return (this is base case)
add vertex to results list
mark vertex as visited (객체, 즉 키-값 쌍을 가지고 표시함, { "A" : true, "B" : true, "C" : true } )
for each neighbor in vertex's neighbors :
if neighbor is not visited :
recursively call DFS on neighbor
자세한 DFS 의사코드 ( Recursive )
1. 노드를 인수로 받는 함수를 작성한다.
2. 최종 결과를 저장할 빈 리스트, 배열을 만든다. (마지막에 리턴할 예정)
3. 정점을 저장할 수 있는 개체를 만듦. (처음엔 빈 상태로 시작해야 함)
4. 정점을 인수로 받는 헬퍼 함수를 만듦.
- 헬퍼 함수는 정점이 비어있으면 빠른 리턴(끝)을 한다.
- 인자로 넣은 정점을 방문 객체로 넣는다, 그리고 방문했다는 표시를 하고 결과 배열에 push 해준다.
- 해당 정점의 모든 인접점에 대해 루프를 돌린다.
- 만약 인접 정점이 방문한 곳이 아니라면, 해당 정점에 대해 헬퍼 함수를 재귀 방식으로 호출한다.
5. 시작 정점을 인자로 헬퍼함수(4번)를 호출한다.
6. 결과 배열(2번)을 리턴한다.
4. 재귀적 용법의 깊이 우선 그래프 (DFS) 솔루션
// graph_DFS_recursive.js
class Graph{
constructor(){
this.adjacencyList = {};
}
addVertex(vertex){
if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}
addEdge(v1,v2){
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
removeEdge(vertex1,vertex2){
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
v => v !== vertex2
);
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
v => v !== vertex1
);
}
removeVertex(vertex){
while(this.adjacencyList[vertex].length){
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex]
}
depthFirstRecursive(start){
const result = [];
const visited = {};
const adjacencyList = this.adjacencyList;
(function dfs(vertex){
if(!vertex) return null;
visited[vertex] = true;
result.push(vertex);
adjacencyList[vertex].forEach(neighbor => {
if(!visited[neighbor]){
return dfs(neighbor)
}
});
})(start);
return result;
}
}
let g = new Graph();
g.addVertex("A")
g.addVertex("B")
g.addVertex("C")
g.addVertex("D")
g.addVertex("E")
g.addVertex("F")
g.addEdge("A", "B")
g.addEdge("A", "C")
g.addEdge("B", "D")
g.addEdge("C", "E")
g.addEdge("D", "E")
g.addEdge("D", "F")
g.addEdge("E", "F")
g.depthFirstRecursive("A")
// A
// / ＼
// B C
// | |
// D --- E
// ＼ /
// F
// 결과 : (6) ['A', 'B', 'D', 'E', 'C', 'F']5. 반복적 용법의 깊이 우선 그래프 (DFS) 소개
DFS 의사코드 ( Iterative )
DFS-iterative (start) :
let S be a stack
S.push(start)
while S is not empty
vertex = S.pop()
if vertex is not labeled as discovered :
visit vertex ( add to result list )
label vertex as discovered
for each of vertex's neighbors, N do S.push(N)
자세한 DFS 의사코드 ( Iterative )
1. 이 함수(depthFirstIterative)는 시작점이 되는 노드(start)를 인자로 받는다.
2. 정점들을 추적하는데 도움을 줄 빈 스택을 만든다. (리스트나 배열 사용)
3. 최종 결과를 저장할 배열or리스트를 만든다. 마지막에 리턴할 예정
4. 방문한 정점들을 저장할 빈 객체를 생성한다.
5. 스택에 시작하는 지점의 정점을 넣는다, 그리고 방문했다고 표시한다.
6. 스택에 무언가 있는 한 루프를 돌린다.
6-1. 스택에서 다음 정점을 pop 한다.
6-2. 결과 리스트에 pop한 정점을 push 한다.
6-2. pop한 정점의 인접 정점들을 forEach 루프를 돌린다.
만약에, 해당 정점을 아직 방문하지 않았다면 :
- (해당 정점) 방문 표시를 한다.
- ("") 인접 정점들을 모두 스택에 push 한다.
7. 결과 배열or리스트(3번)를 리턴한다.
6. 반복적 용법의 깊이 우선 그래프 (DFS) 솔루션
// graph_DFS_iterative.js
class Graph{
constructor(){
this.adjacencyList = {};
}
addVertex(vertex){
if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}
addEdge(v1,v2){
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
removeEdge(vertex1,vertex2){
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
v => v !== vertex2
);
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
v => v !== vertex1
);
}
removeVertex(vertex){
while(this.adjacencyList[vertex].length){
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex]
}
depthFirstRecursive(start){
const result = [];
const visited = {};
const adjacencyList = this.adjacencyList;
(function dfs(vertex){
if(!vertex) return null;
visited[vertex] = true;
result.push(vertex);
adjacencyList[vertex].forEach(neighbor => {
if(!visited[neighbor]){
return dfs(neighbor)
}
});
})(start);
return result;
}
depthFirstIterative(start){
const stack = [start];
const result = [];
const visited = {};
let currentVertex;
visited[start] = true;
while(stack.length){
currentVertex = stack.pop();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor => {
if(!visited[neighbor]){
visited[neighbor] = true;
stack.push(neighbor)
}
});
}
return result;
}
}
let g = new Graph();
g.addVertex("A")
g.addVertex("B")
g.addVertex("C")
g.addVertex("D")
g.addVertex("E")
g.addVertex("F")
g.addEdge("A", "B")
g.addEdge("A", "C")
g.addEdge("B","D")
g.addEdge("C","E")
g.addEdge("D","E")
g.addEdge("D","F")
g.addEdge("E","F")
// A
// / ＼
// B C
// | |
// D --- E
// ＼ /
// F
// 결과 : (6) ['A', 'C', 'E', 'F', 'D', 'B']7. 넓이 우선 그래프 (BFS) 순회
Breadth First Search ?
같은 깊이의 인접 정점 먼저 방문한다. (Visit neighbors at current depth first !)
8. 넓이 우선 그래프 (BFS) 소개
깊이 우선 탐색에서 했던 것과 매우 비슷하다.
다른 점은 다른 종류의 데이터 구조를 사용한다는 점이다.
스택 대신에 큐를 사용한다.
스택을 배열로 사용할 때는 push와 pop을 사용했지만, (LIFO)
큐를 배열로 사용할 땐 push와 shift를 사용하게 된다. (FIFO)
BFS 의사코드
1. 이 함수는 시작하는 정점을 인자로 받는다.
2. 배열을 사용해서 queue를 생성한다. 그리고 시작 정점을 넣는다.
3. 방문한 노드들을 저장할 배열을 생성한다.
4. 방문한 노드들을 저장할 객체를 생성한다.
5. 시작 정점을 방문한 것으로 표시한다.
6. 큐에 무언가 있는 한 반복문을 돌려준다.
7. 큐에서 첫 정점을 제거(shift) 하고, 방문한 노드를 저장하는 배열에 push한다.
8. 방문한 정점의 각 인접 정점들을 반복 루프 한다.
9. 만약에 인접 정점을 아직 방문하지 않았다면, 객체(4번)에 방문했다고 표시하고 큐(2번)에 enqueue(push)한다.
10. 루프를 끝내면, 방문했던 노드 배열(3번)을 리턴한다.
9. 넓이 우선 그래프 (BFS) 솔루션
// graph_BFS.js
class Graph{
constructor(){
this.adjacencyList = {};
}
addVertex(vertex){
if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}
addEdge(v1,v2){
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
removeEdge(vertex1,vertex2){
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
v => v !== vertex2
);
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
v => v !== vertex1
);
}
removeVertex(vertex){
while(this.adjacencyList[vertex].length){
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex]
}
depthFirstRecursive(start){
const result = [];
const visited = {};
const adjacencyList = this.adjacencyList;
(function dfs(vertex){
if(!vertex) return null;
visited[vertex] = true;
result.push(vertex);
adjacencyList[vertex].forEach(neighbor => {
if(!visited[neighbor]){
return dfs(neighbor)
}
});
})(start);
return result;
}
depthFirstIterative(start){
const stack = [start];
const result = [];
const visited = {};
let currentVertex;
visited[start] = true;
while(stack.length){
currentVertex = stack.pop();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor => {
if(!visited[neighbor]){
visited[neighbor] = true;
stack.push(neighbor)
}
});
}
return result;
}
breadthFirst(start){
const queue = [start];
const result = [];
const visited = {};
let currentVertex;
visited[start] = true;
while(queue.length){
currentVertex = queue.shift();
result.push(currentVertex);
this.adjacencyList[currentVertex].forEach(neighbor => {
if(!visited[neighbor]){
visited[neighbor] = true;
queue.push(neighbor);
}
});
}
return result;
}
}
let g = new Graph();
g.addVertex("A")
g.addVertex("B")
g.addVertex("C")
g.addVertex("D")
g.addVertex("E")
g.addVertex("F")
g.addEdge("A", "B")
g.addEdge("A", "C")
g.addEdge("B","D")
g.addEdge("C","E")
g.addEdge("D","E")
g.addEdge("D","F")
g.addEdge("E","F")
// A
// / ＼
// B C
// | |
// D --- E
// ＼ /
// F
// QUEUE: []
// RESULT: [A, B, C, D, E, F]