图的遍历(Traversing Graph)是指从图中某一顶点出发访问图中其余顶点,且使每个顶点仅被访问一次。
深度优先搜索(Depth First Search)
深度优先搜索假设初始状态下图中所有顶点都未被访问,尝试优先搜索从图中某个顶点v出去,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,直到图中所有和v相连连的顶点都被访问到。如果此时图中还有没有访问到的顶点,则另选图中未被访问的某顶点作为起始点,重复上述过程,直到图中所有顶点都被访问到。
采用邻接表存储图的具体实现如下:
#include <cstdio> #include <cstdlib> #define VERTEXNUM 100 //顶点个数 typedef char VertexType; typedef int EdgeType; typedef enum{FALSE, TRUE} Boolean; Boolean visited[VERTEXNUM]; /*************************************** * * 邻接表存储结构 * * *************************************/ typedef struct node { int adjvex; //顶点位置 struct node *next; //指向下一条边的指针 }EdgeNode; typedef struct vnode { VertexType vertex; //顶点信息 EdgeNode *firstedge; //指向第一条依附该顶点的边的指针 }AdjList[VERTEXNUM]; typedef struct { AdjList vertexs; //邻接表 int vernum, edgenum; //图中当前的顶点和边数 }Graph; /*************************************** * * 建立图的邻接表 * * *************************************/ void MakeGraph(Graph *graph) { int v1, v2; int i, j, k; printf("请输入图的顶点数n和边数e:\n"); scanf("%d%d", &graph->vernum, &graph->edgenum); printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n"); for(i = 0; i < graph->vernum; i++) { getchar(); scanf("%c", &graph->vertexs[i].vertex); graph->vertexs[i].firstedge = NULL; //初始第一条边为空 } printf("请输入每条边对应的两个顶点的序号(格式为i,j):\n"); EdgeNode *p; for(k = 0; k < graph->edgenum; k++) { scanf("%d,%d", &i, &j); //读入边<vi,vj>的序号 p = (node *)malloc(sizeof(node)); //生成新的结点 p->adjvex = j - 1; p->next = graph->vertexs[i - 1].firstedge; graph->vertexs[i - 1].firstedge = p; } } /*************************************** * * 深度优先遍历 * * *************************************/ void DFSTraverse(Graph *graph, int v) { visited[v] = TRUE; printf("深度遍历:结点%c\n", graph->vertexs[v].vertex); EdgeNode *p = graph->vertexs[v].firstedge; while(p != NULL) { if(!visited[p->adjvex]) DFSTraverse(graph, p->adjvex); p = p->next; } } void DFS(Graph *graph) { int i; for(i = 0; i < graph->vernum; i++) visited[i] = FALSE; for(i = 0; i < graph->vernum; i++) if(!visited[i]) DFSTraverse(graph, i); } int main() { Graph *graph = (Graph *)malloc(sizeof(Graph)); MakeGraph(graph); //建立图的邻接表 DFS(graph); //深度优先遍历 return 0; }
对于图一中的图,上述程序运行结果如图二。
图一
图二