Aim:

Write a program to implement the graph traversal methods (Depth First Search)

Solution :

C program to implement the Depth First search a graph traversal methods

#include <stdio.h>
int a[20][20], visited[20], n;
void dfs(int v) 
{
	int i;
    visited[v] = 1;
    for (i = 1; i <= n; i++)
	{
		if (a[v][i] && !visited[i]) 
		{
			printf("\n %d->%d", v, i);
            dfs(i);
        }
    }
}

int main( ) 
{
	int i, j,v, count = 0;
    printf("\n Enter number of vertices:");
    scanf("%d", &n);
    for (i = 1; i <= n; i++) 
	{
		visited[i] = 0;
        for (j = 1; j <= n; j++)
			a[i][j] = 0;
	}
    printf("\n Enter the adjacency matrix:\n");
    for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			scanf("%d", &a[i][j]);
	printf("Enter the starting vertex: ");
    scanf("%d", &v);
	dfs(v);
    return 0;
}

Enter number of vertices:6
Enter the adjacency matrix:
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 1 1 0
0 0 1 0 0 0
0 0 1 0 0 1
0 0 0 0 1 0
Enter the starting vertex: 2
2->1
1->3
3->4
3->5
5->6

Related Content :

Data Structures Lab Programs

1) Write a program that uses functions to perform the following operations on singly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

2) Write a program that uses functions to perform the following operations on doubly linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

3) Write a program that uses functions to perform the following operations on circular linkedlist.:
i) Creation ii) Insertion iii) Deletion iv) Traversal View Solution

4) Write a program that implement Stack (its operations) using Array View Solution

5) Write a program that implement Stack (its operations) using Linked List (Pointer) View Solution

6) Write a program that implement Queue(its operations) using Array View Solution

7) Write a program that implement Queue (its operations) using Linked List (Pointer) View Solution

8) Write a program that implements Quick sort sorting methods to sort a given list of integers in ascending order View Solution

9) Write a program that implements Merge sort sorting methods to sort a given list of integers in ascending order View Solution

10) Write a program that implements Heap sort sorting methods to sort a given list of integers in ascending order View Solution

11) Write a program to implement the tree traversal methods using Recursive View Solution

12) Write a program to implement the tree traversal methods using Non Recursive View Solution

13) Write a program to implement Binary Search Tree (its operations) View Solution

14) Write a program to implement AVL Tree (its operations) View Solution

15) Write a program to implement Red - Black Tree (its operations) View Solution

16) Write a program to implement B Trees (its operations) View Solution

17) Write a program to implement B+ Trees (its operations) View Solution

18) Write a program to implement the graph traversal methods (Breadth First Search) View Solution

19) Write a program to implement the graph traversal methods (Depth First Search) View Solution

20) Write a program to Implement a Pattern matching algorithms using Boyer- Moore View Solution

21) Write a program to Implement a Pattern matching algorithms using Knuth-Morris-Pratt View Solution