Breadth-first search (BFS)
BFS is a traversing algorithm that starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory is needed to keep track of the child nodes that were encountered but not yet explored.
The traversing process is as follows:
Pseudocode
BFS(G, root) is
let Q be a queue
label root as explored
Q.enqueue(root) // insert a tree root in queue until every neighbour vertices are marked
while Q is not empty do:
v := Q.dequeue() // remove a to-be-visited vertex from queue
if v is the goal then
return v
for all edges from v to w in G.adjacentEdges(v) do:
if w is not labelled as explored then
label w as explored
Q.enqueue(w) // store w in Q if it's not visited
end for
end while
end
Depth-first search (DFS)
DFS is a traversing algorithm that starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
The traversing process is as follows:
Pseudocode
DFS(G,v) // v is the vertex where the search starts
Stack S := {}; // start with an empty stack
for each vertex u, set visited[u] := false
push S, v;
while S is not empty do:
u := pop S;
if u is not visited then
visited[u] := true;
for each unvisited neighbout w of u
push S, w;
end for
end while
end for
end
Example
The number of vertices: 4
The number of edges: 5
Start node: 1
#include <iostream>
#include <queue>
#define MAX_VAL 1001
int N, M, V;
int mat[MAX_VAL][MAX_VAL];
bool visited[MAX_VAL];
using namespace std;
void dfs(int v)
{
printf("%d, ", v);
visited[v] = true;
for (int i = 1; i <= N; i++)
{
if (visited[i] || mat[v][i] == 0)
continue;
dfs(i);
}
}
void bfs(int v)
{
queue<int> q;
q.push(v);
visited[v] = true;
while (!q.empty())
{
v = q.front();
printf("%d, ", q.front());
q.pop();
for (int i = 1; i <= N; i++)
{
if (visited[i] || mat[v][i] == 0)
continue;
q.push(i);
visited[i] = true;
}
}
}
int main()
{
int x, y;
cin >> N >> M >> V;
for (int i = 0; i < M; i++)
{
cin >> x >> y;
mat[x][y] = mat[y][x] = 1;
}
memset(visited, false, sizeof(visited));
dfs(V);
prinft("\n");
memset(visited, false, sizeof(visited));
bfs(V);
}
Complexity
| BFS | DFS | |
| Time | O(|V| + |E|) | O(|V| + |E|) |
| Space | O(|V|) | O(|V|) |
- |V| is the number of vertices
- |E| is the number of edges
'Algorithms' 카테고리의 다른 글
| Window Sliding Technique (0) | 2021.09.11 |
|---|---|
| Hopcroft-Karp algorithm (호프크로프트-카프) (0) | 2021.09.05 |
| Recursion vs. Iteration for Fibonacci (0) | 2021.08.25 |
| Recursive Algorithm 재귀 알고리즘 (0) | 2021.08.25 |
| Halting Problem 정지 문제 (0) | 2021.08.24 |
