tu-table-DFS.rar_dfs_tu_图的遍历_连通_非 连通图 遍历

#include <stdlib.h> #include <stdio.h> struct node /* 图形顶点结构定义 */ { int vertex; /* 顶点 */ struct node *nextnode; /* 指下一顶点的指针 */ }; typedef struct node *graph; /* 图形的结构重定义 */ struct node head[6]; /* 图形顶点结构数组 */ bool visited[6]; // 访问标志数组 /*----------建立图形--------*/ void creategraph(int *node,int num) { graph newnode; /* 新顶点指针 */ graph ptr; int from; /* 边线的起点 */ int to; /* 边线的终点 */ int i; for ( i = 0; i < num; i++ ) /* 读取边线的回路 */ { from = node[i*2]; /* 边线的起点 */ to = node[i*2+1]; /* 边线的终点 */ /* 申请存储新顶点的内存空间 */ newnode = ( graph ) malloc(sizeof(struct node)); newnode->vertex = to; /* 建立顶点内容 */ newnode->nextnode = NULL; /* 设定指针初值 */ ptr = &(head[from]); /* 顶点位置 */ while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */ ptr = ptr->nextnode; /* 下一个顶点 */ ptr->nextnode = newnode; /* 插入结尾 */ } } /*------------深度遍历------------*/ void DFS(node *head, int v) { // 算法7.5 // 从第v个顶点出发递归地深度优先遍历图G。 int w; graph p; visited[v] = true; printf(" %d ",head[v].vertex); // 访问第v个顶点 for (p=head[v].nextnode; p!=NULL; p=p->nextnode){ w=p->vertex; if (!visited[w]) DFS(head, w); // 对v的尚未访问的邻接顶点w递归调用DFS } } void DFSTraverse(node *head) { // 算法7.4 // 对图G作深度优先遍历。 int v; for (v=0; v<6; ++v) visited[v] = false; // 访问标志数组初始化 for (v=0; v<6; ++v) if (!visited[v]) DFS(head, v); // 对尚未访问的顶点调用DFS } /*------主程序: 建立图形后,将邻接链表输出------*/ void main() { graph ptr; int node[12][2] = { {0, 2}, {2, 0}, /* 边线数组 */ {1, 4}, {4, 1}, {1, 5}, {5, 1}, {3, 4}, {4, 3}, {3, 5}, {5, 3}, {4, 5}, {5, 4} }; int i; for ( i = 0; i <= 5; i++ ) { head[i].vertex = i; /* 设定顶点值 */ head[i].nextnode = NULL; /* 清除图形指针 */ } creategraph(*node,12); /* 建立图形 */ printf("图形的邻接链表内容:\n"); for ( i = 0; i <= 5; i++ ) { printf("顶点%d =>",head[i].vertex);/* 顶点值 */ ptr = head[i].nextnode; /* 顶点位置 */ while ( ptr != NULL ) /* 遍历至链表尾 */ { printf(" %d ",ptr->vertex); /* 输出顶点内容 */ ptr = ptr->nextnode; /* 下一个顶点 */ } printf("\n"); /* 换行 */ } DFSTraverse(head); }