graph traversal

What is Graph Traversal?

Graph traversal refers to the process of visiting each vertex in a graph.

Types of Graph Traversal

  • Breadth First Search(BFS)
  • Depth First Search(DFS)

Breadth First Search(BFS)

BFS is an algorithm for traversing Graph data structures. It starts at some arbitrary node of a graph and explores the neighbor nodes(which are at current level) first, before moving to the next level neighbors.

Handling one Special Scenario of BFS

  • Disconnected Graph
    • Cannot traverse the graph with BFS. Because the vertecis are disconneted with each other.

Time Complexity - BFS

  • Time Complexity - O(V+E)
  • Space Complexity - O(V+E)

Depth First Search(DFS)

DFS is an algorithm for traversing Graph data structures. It starts selecting some arbitrary node and explores as far as possible along each edge before backtracking.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
class Graph {
    constructor(){
        this.adjacencyList = {};
    }
    addVertex(vertex){
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }

    addEdge(vertex1, vertex2){
        if(this.adjacencyList[vertex1]){
            this.adjacencyList[vertex1].push(vertex2);
        }
        if(this.adjacencyList[vertex2]){
            this.adjacencyList[vertex2].push(vertex1);
        }
    }

    removeEdge(v1, v2){
        if(this.adjacencyList[v1].includes(v2)){
            this.adjacencyList[v1] = this.adjacencyList[v1].filter( v => v !== v2);
        }
        if(this.adjacencyList[v2].includes(v1)){
            this.adjacencyList[v2] = this.adjacencyList[v2].filter( v => v !== v1);
        }
    }

    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;
    }

    breadthFirstIterative(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")
g.depthFirstRecursive("A")


//          A
//        /   \
//       B     C
//       |     |
//       D --- E
//        \   /
//          F

출처 : “Data Structures & Algorithms” by DS GUY