Tweet
# include<stdio.h>
# define size 25
# define T 1
# define F 0
typedef struct Edge
{
int terminal;
struct Edge *next;
}ed;
typedef struct Vertex
{
int visit;
int vertex_no;
char info;
int path_length;
struct Edge *Edge_Ptr;
}ver;
void Table(int , int matrix [size][size], struct Vertex vert[size]);
ed *Insert_Vertex (int , ed *);
void DFS ( int , int *dist, ver vert [size]);
void Input(int, int a [size][size]);
void Output(int, int a [size][size]);
ed * Insert_Vertex (int vertex_no, ed *first)
{
ed *new1, *current;
new1 = (ed *) malloc(sizeof(ed));
new1->terminal = vertex_no;
new1->next = NULL;
if (!first)
return (new1);
for (current = first; current->next; current = current->next);
current->next = new1;
return (first);
}
void Table(int vertex_num, int matrix [size][size],
ver vert[size])
{
int i, j;
for (i = 0; i < vertex_num; i++)
{
vert [i].visit = F;
vert [i].vertex_no = i+1;
vert [i].info = 'A'+ i;
vert [i].path_length = 0;
vert [i].Edge_Ptr = NULL;
}
for (i =0; i < vertex_num ; i++)
for (j =0; j < vertex_num ; j++)
if (matrix [i][j] > 0)
vert [i].Edge_Ptr = Insert_Vertex (j, vert [i].Edge_Ptr);
}
void DFS ( int index, int *dist,
ver vert [size])
{
ed *Link;
vert [index].visit = T;
vert [index].path_length = *dist;
*dist += 1;
for ( Link = vert [index].Edge_Ptr; Link; Link = Link->next)
if (vert [Link->terminal].visit == F)
DFS (Link->terminal, dist, vert);
}
void Input(int number, int a [size][size])
{
int i, j;
printf("\n Input the adjacency matrix \n");
for (i =0; i < number; i++)
{
for (j=0; j < number; j ++)
{
scanf("%d", &a [i][j]);
}
printf("\n");
}
}
void Output(int number, int a [size][size])
{
int i, j;
printf("\n Adjacency matrix \n");
for (i = 0; i < number; i++)
{
for (j = 0; j < number; j ++)
{
printf(" %d", a [i][j]);
}
printf("\n");
}
}
main()
{
int i;
int number, index, dist;
int a [size][size];
ver vert [size];
ed *List;
printf("\n Input the number of vertices in the graph: ");
scanf("%d", &number);
Input(number, a);
Output(number, a);
Table(number, a, vert);
printf("\n Input the starting vertex 0- %d:", number-1);
scanf("%d", &index);
dist = 0;
DFS (index, &dist, vert);
printf("\n Path length of the vertex from %c", vert[index].info);
printf("\n Vertex Length Vertex Connectivity \n ");
for (i = 0; i < number; i++)
{
printf("\n %c %d ", vert[i].info, vert[i].path_length);
for (List= vert[i].Edge_Ptr; List; List = List->next)
{
printf(" ");
putchar(List->terminal+'A');
}
}
}
DFS Algorithm Programming in C
