Compiled and confirmed:
/* Depth-first traversal of graph*/
#include
#include
#include
struct node /* graph vertex structure definition*/
{
int vertex; /* Vertex data information*/
struct node *nextnode; /* Pointer to the next vertex*/
};
typedef struct node *graph; /* The new structure of the graph*/
struct node head[9]; /* The graph vertex array is changed to the actual size*/
int visited[ 9]; /* Traverse the tag array and change it to the actual array size*/
/********************Establish adjacency based on existing information Table**********************/
void creategraph(int node[20][2],int num)/*num refers to Number of edges in the graph*/
{
graph newnode; /*Pointer definition pointing to new node*/
graph ptr;
int from; /* The starting point of the edge*/
int to; /* The end point of the edge*/
int i;
for ( i = 0 ; i < num; i++ ) /* Read edge information and insert into adjacency list*/
{
from = node[i][0]; /* Starting point of edge*/ /
to = node[i][1]; /* End point of edge*/
/* Create new vertex*/
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* Create vertex content*/
newnode->nextnode = NULL; /* Set indicator Initial value*/
ptr = &(head[from]); /* Vertex position*/
while ( ptr->nextnode != NULL ) /* Traverse to the end of the linked list */
ptr = ptr->nextnode; /* Next vertex*/
ptr->nextnode = newnode; /* Insert node*/
}
}
/********************** Depth-first search method for graphs***** ***************/
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* record has been traversed*/
printf("vertex[%d]\n",current); /* output the traversed vertex value*/ < /p>
ptr = head[current].nextnode; /* Vertex position*/
while ( ptr != NULL ) /* Traverse to the end of the linked list*/
{
if ( visited[ptr->vertex] == 0 ) /* If it has not been traversed before*/
dfs(ptr->vertex); /* Recursive traversal Call*/
ptr = ptr->nextnode; /* Next vertex*/
}
}
/** ****************************** Main program************************ **********/
int main()
{
graph ptr; /* Edge array*/
int node[20][2] = { {1, 2}, {2, 1}, /*Replace with your own vertex value, and the value range of i in the for loop below will change accordingly*/
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5 , 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{ 4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6}, < /p>
{7, 8}, {8, 7} };
int i;
system("cls");
for ( i = 1; i <= 8; i++ ) /* Vertex array initialization*/
{
head[i].vertex = i; /* Set vertex value */
head[i].nextnode = NULL; /* The pointer is null*/
visited[i] = 0; /* Set the traversal initial flag*/
}
creategraph(node,20); /* Create adjacency list*/
printf("Content of the gragh's ADlist is:\n"); < /p>
for ( i = 1; i <= 8; i++ )
{
printf("vertex%d ->",head[i].vertex ); /* Vertex value*/
ptr = head[i].nextnode; /* Vertex position*/
while ( ptr != NULL ) /* Traverse to the end of the linked list */
{
printf(" %d ",ptr->vertex); /* Print the vertex content*/
ptr = ptr-> nextnode; /* next vertex*/
}
printf("\n"); /* newline*/
}
< p>printf("\nThe end of the dfs are:\n");dfs(1); /* Print output traversal process*/
printf("\n "); /* Line break*/
puts(" Press any key to quit...");
getch();
return 0;
}