Current location - Plastic Surgery and Aesthetics Network - Plastic surgery and beauty - Data structure course design, directed graph, for C language experts
Data structure course design, directed graph, for C language experts

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;

}