Depth First search algorithm is used for traversing or searching the graph. Select a vertex as start vertex V and mark it as visited. Any non-visited vertex w adjacent to V is selected and apply depth first search to w. If a vertex x is reached and all its adjacent vertices are already visited, then we need to back track to the last visited vertex which has any non-visited vertex w adjacent to it and apply depth first search on w. This process continues until no more non-visited vertex can be selected from any of the visited vertices.
Algorithm For Depth First Search:
DFS (v) {
visited[v] = 1
for all w adjacent to v do
if visited[v] == 0
DFS(w)
}
We are going to do depth first search for the below graph.
+-------------------- V1 -----------------------+
| |
| |
V2 -------------------+ +-------------------- V3
| | | |
| | | |
V4 | | V5
| | | |
| | | |
+------------------- V6 ----------------------+
Steps to perform Depth First Search:
So, the given graph is visited in the order: V1, V2, V4, V6, V3 and V5.
+-------------------- V1 ----------------------+
| |
| |
V2 -------------------+ +-------------------- V3
| | | |
| | | |
V4 | | V5
| | | |
| | | |
+-------------------- V6 ----------------------+
Adjacency list representation of the input graph:
+----------+ +---------+ +----------+
| V1 |----->| 2 | |----->| 3 | N |
| | +---------+ +----------+
+----------+ +---------+ +----------+ +----------+
| |----->| 1 | |---->| 4 | |----->| 6 | N |
| V2 | +---------+ +----------+ +----------+
+----------+ +---------+ +----------+ +----------+
| |---->| 1 | |----->| 5 | |----->| 6 | N |
| V3 | +---------+ +----------+ +----------+
+----------+ +---------+ +----------+
| |---->| 2 | |----->| 6 | N |
| V4 | +---------+ +----------+
+----------+ +---------+ +----------+
| |---->| 3 | |----->| 6 | N |
| V5 | +---------+ +----------+
+----------+ +---------+ +----------+ +----------+ +----------+
| |---->| 2 | |----->| 3 | |------>| 4 | N |----->| 5 | N |
| V6 | +---------+ +----------+ +----------+ +----------+
+----------+
See Also:
C Program To Implement Dijkstra's Algorithm
C Program To Find Minimum Spanning Tree Using Prim's Algorithm
C Program To Find Minimum Spanning Tree Using Kruskal's Algorithm
C Program To Implement Breath First Search
C Program To Implement Depth First Search
Algorithm For Depth First Search:
DFS (v) {
visited[v] = 1
for all w adjacent to v do
if visited[v] == 0
DFS(w)
}
We are going to do depth first search for the below graph.
+-------------------- V1 -----------------------+
| |
| |
V2 -------------------+ +-------------------- V3
| | | |
| | | |
V4 | | V5
| | | |
| | | |
+------------------- V6 ----------------------+
Steps to perform Depth First Search:
- Select a start vertex and mark it as visited. Vertex v1 is selected and it is marked as visited.
- V1 has two adjacent vertices. We need to select one among V2 and V3. Let's consider that we will always select lowest vertex(v2 < v3 <=> 2 < 3). So, vertex V2 is selected.
- V1 and V4 are adjacent to V4. Select V4 since V1 is already visited.
- V6 is selected.
- V4, V5, V2 and V3 are adjacent to V6. V2 and V4 are already visited. So, we cannot select them. (V3 < V5) Mark V3 as visited.
- V5 is the only non-visited vertex. So, select it and mark it as visited.
So, the given graph is visited in the order: V1, V2, V4, V6, V3 and V5.
+-------------------- V1 ----------------------+
| |
| |
V2 -------------------+ +-------------------- V3
| | | |
| | | |
V4 | | V5
| | | |
| | | |
+-------------------- V6 ----------------------+
Adjacency list representation of the input graph:
- There's one list for each vertex in the graph. Each list has a head node(V1, V2, V3, V4, V5 & V6).
- Adjacent vertices are linked to the head node. And the head node provides random access to any particular vertex(by using data in the node as vertex).
+----------+ +---------+ +----------+
| V1 |----->| 2 | |----->| 3 | N |
| | +---------+ +----------+
+----------+ +---------+ +----------+ +----------+
| |----->| 1 | |---->| 4 | |----->| 6 | N |
| V2 | +---------+ +----------+ +----------+
+----------+ +---------+ +----------+ +----------+
| |---->| 1 | |----->| 5 | |----->| 6 | N |
| V3 | +---------+ +----------+ +----------+
+----------+ +---------+ +----------+
| |---->| 2 | |----->| 6 | N |
| V4 | +---------+ +----------+
+----------+ +---------+ +----------+
| |---->| 3 | |----->| 6 | N |
| V5 | +---------+ +----------+
+----------+ +---------+ +----------+ +----------+ +----------+
| |---->| 2 | |----->| 3 | |------>| 4 | N |----->| 5 | N |
| V6 | +---------+ +----------+ +----------+ +----------+
+----------+
See Also:
C Program To Implement Dijkstra's Algorithm
C Program To Find Minimum Spanning Tree Using Prim's Algorithm
C Program To Find Minimum Spanning Tree Using Kruskal's Algorithm
C Program To Implement Breath First Search
C Program To Implement Depth First Search
Example Program To Implement Depth First Search(in C):
#include <stdlib.h>
#define VERTEXCOUNT 6
#define VISITED 1
struct node {
int data;
struct node *next;
};
int visitVertex[VERTEXCOUNT];
struct node * createNode(int data) {
struct node *newnode;
newnode = (struct node *)malloc(sizeof(struct node));
newnode->data = data;
newnode->next = NULL;
return newnode;
}
void depthFirstSearch(int index, struct node *vertex[]) {
struct node *temp;
/* mark the unvisted node as visited and print it to console */
visitVertex[index - 1] = VISITED;
temp = vertex[index - 1];
printf("VV(Visited Vertex): %d\n", index);
while (temp != NULL) {
/*
* if current vertex is already visited,
* try next adjacent vertex. Otherwise, do
* depth first search for current vertex.
*/
if (visitVertex[temp->data - 1] == VISITED)
temp = temp->next;
else
depthFirstSearch(temp->data, vertex);
}
}
void deleteNodes(struct node *myNode) {
struct node *temp;
while (myNode != NULL) {
temp = myNode;
myNode = myNode->next;
free(temp);
}
}
int main() {
struct node *vertex[VERTEXCOUNT], *newnode;
int index = 0;
/* Create adjacency list for the graph */
newnode = createNode(2);
vertex[0] = newnode;
newnode->next = createNode(3);
newnode = createNode(1);
vertex[1] = newnode;
newnode->next = createNode(4);
newnode->next->next = createNode(6);
newnode = createNode(1);
vertex[2] = newnode;
newnode->next = createNode(5);
newnode->next->next = createNode(6);
newnode = createNode(2);
vertex[3] = newnode;
newnode->next = createNode(6);
newnode = createNode(3);
vertex[4] = newnode;
newnode->next = createNode(6);
newnode = createNode(2);
vertex[5] = newnode;
newnode->next = createNode(3);
newnode->next->next = createNode(4);
newnode->next->next->next = createNode(5);
/* depth first search operation */
depthFirstSearch(1, vertex);
while (index < VERTEXCOUNT) {
deleteNodes(vertex[index]);
index++;
}
return 0;
}
Output: (C Program To Implement Depth First Search)
jp@jp-VirtualBox:~/$ ./a.out
VV(Visited Vertex): 1
VV(Visited Vertex): 2
VV(Visited Vertex): 4
VV(Visited Vertex): 6
VV(Visited Vertex): 3
VV(Visited Vertex): 5
VV(Visited Vertex): 1
VV(Visited Vertex): 2
VV(Visited Vertex): 4
VV(Visited Vertex): 6
VV(Visited Vertex): 3
VV(Visited Vertex): 5
No comments:
Post a Comment