dfs Recursive Algorithm
The Depth First Search (DFS) algorithm is a powerful and widely-used graph traversal technique in computer science and programming. The DFS Recursive Algorithm, as the name suggests, employs recursion to explore all the vertices and edges of a graph or a tree in a depthward motion, moving as far as possible along a branch before backtracking. This algorithm can be used for various applications, such as finding connected components in an undirected graph, topological sorting in directed acyclic graphs, and solving puzzles like mazes and game boards.
In the DFS Recursive Algorithm, the traversal starts from a source node or vertex and continues to visit adjacent, unvisited vertices recursively. During the process, each visited vertex is marked as visited to avoid revisiting it in the future. Once the algorithm reaches a vertex with no unvisited neighbors, it backtracks and moves on to the next unvisited adjacent vertex in the previous node. This process continues until all reachable vertices from the source node have been visited. The DFS Recursive Algorithm can be implemented using stack data structure, where the vertices are pushed onto the stack as they are visited, and popped from the stack when backtracking. The algorithm is efficient in terms of memory usage, as it only needs to store the current path and visited vertices, making it suitable for large graphs and complex problems.
#include <stdio.h>
#include <stdbool.h>
#include "Graph.h"
#define MAX_NODES 1000
int visited[MAX_NODES]; // array to store visiting order
// indexed by vertex 0..nV-1
bool dfsPathCheck(Graph g, int nV, Vertex v, Vertex dest) {
Vertex w;
for (w = 0; w < nV; w++)
if (adjacent(g, v, w) && visited[w] == -1) {
visited[w] = v;
if (w == dest)
return true;
else if (dfsPathCheck(g, nV, w, dest))
return true;
}
return false;
}
bool findPathDFS(Graph g, int nV, Vertex src, Vertex dest) {
Vertex v;
for (v = 0; v < nV; v++)
visited[v] = -1;
visited[src] = src;
return dfsPathCheck(g, nV, src, dest);
}
int main(void) {
int V = 6;
Graph g = newGraph(V);
Edge e;
e.v = 0; e.w = 1; insertEdge(g, e);
e.v = 0; e.w = 4; insertEdge(g, e);
e.v = 0; e.w = 5; insertEdge(g, e);
e.v = 5; e.w = 4; insertEdge(g, e);
e.v = 4; e.w = 2; insertEdge(g, e);
e.v = 4; e.w = 3; insertEdge(g, e);
e.v = 5; e.w = 3; insertEdge(g, e);
e.v = 1; e.w = 2; insertEdge(g, e);
e.v = 3; e.w = 2; insertEdge(g, e);
int src = 0, dest = 5;
if (findPathDFS(g, V, src, dest)) {
Vertex v = dest;
while (v != src) {
printf("%d - ", v);
v = visited[v];
}
printf("%d\n", src);
}
return 0;
}
// By
// .----------------. .----------------. .----------------. .-----------------. .----------------. .----------------.
// | .--------------. || .--------------. || .--------------. || .--------------. | | .--------------. || .--------------. |
// | | _________ | || | _____ _____ | || | __ | || | ____ _____ | | | | ____ ____ | || | ____ | |
// | | | _ _ | | || ||_ _||_ _|| || | / \ | || ||_ \|_ _| | | | | |_ || _| | || | .' `. | |
// | | |_/ | | \_| | || | | | | | | || | / /\ \ | || | | \ | | | | | | | |__| | | || | / .--. \ | |
// | | | | | || | | ' ' | | || | / ____ \ | || | | |\ \| | | | | | | __ | | || | | | | | | |
// | | _| |_ | || | \ `--' / | || | _/ / \ \_ | || | _| |_\ |_ | | | | _| | | |_ | || | \ `--' / | |
// | | |_____| | || | `.__.' | || ||____| |____|| || ||_____|\____| | | | | |____||____| | || | `.____.' | |
// | | | || | | || | | || | | | | | | || | | |
// | '--------------' || '--------------' || '--------------' || '--------------' | | '--------------' || '--------------' |
// '----------------' '----------------' '----------------' '----------------' '----------------' '----------------'
// Email : z5261243@unsw.edu.au
// hhoanhtuann@gmail.com
