关于—图的编历—你了解多少RodmaChen的博客-

前言

这是我听老师讲课做的笔记,考试要看的。
作者：RodmaChen
关注我的csdn博客，更多数据结构与算法知识还在更新

一.深度优先遍历（DFS ）

一条道走到黑，撞到南墙再返回

（1）基本思想：给定一个连通子图，从图中某个结点v1出发，首先访问出发点v1，然后选择一个v1的未被访问过的邻接点v2，以v2为新的出发点继续进行深度优先遍历， 当遇到一个所有邻接于它的顶点都被访问过时，则回到已访问顶点中最后一个拥有未被访问的相邻顶点，再进行深度优先，直至所有的顶点都被访问。直到子图中所有结点都被访问过（递归定义）。若此时图中仍有未访问的结点，则另找一个连通子图，重复上述操作，直到图中所有的结点都被访问过。
特点：尽可能先对纵深方向进行搜索。

列：深度优先遍历过程

方法一：v3—v7—v6—v1—v2—v4—v8—v5

方法二：v1—v3—v6—v7—v2—v5—v8—v4

（2）算法实现

主函数：

void DFSTraverseAL(ALGraph *G) { /*深度优先遍历以邻接表存储的图G*/ int i; for (i=0;i<G->n;i++) visited[i]=FALSE;//标志数组 for (i=0;i<G->n;i++) if (!visited[i]) DFS(G,i);//是否被访问过 } void DFS(ALGraph *G,int i)//i:始发点 { /*以Vi为出发点对邻接表存储的图G进行DFS搜索*/ EdgeNode *p;//指向边结的指针 printf("visit vertex:V%cn",G->adjlist[i].vertex); /*访问顶点Vi*/ visited[i]=1;//表示访问过了 p=G->adjlist[i].firstedge;//p指向指针域 while(p) { if (visited[p->adjvex]==0)//p指向的值域是否被访问过，0未访问过，1访问过 {DFS(G,p->adjvex);}//循环深度调用 p=p->next; } } 

ALG邻接表表示法，MG邻接矩阵

二.广度优先遍历 （BFS）

（1）基本思想：

假设从图中某连通子图某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

始发点不一定唯一：先访问谁写谁的孩子

方法一：v1—v3—v2—v6—v7—v5—v4—v8

方法二：v3—v1—v6—v7—v2—v4—v5—v8

（2）算法实现

按照队的先进先出的特性

（1）：初始化队列Q

（2）：等于1表示访问过，输出

void BFS(ALGraph G, int i) { /*按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited*/ for (i=0;i<G.n;i++) visited[i]=0; InitQueue(Q); visited[i]=1;//表示访问过 printf(G.adjlist[i].vertex); EnQueue(Q,i); while (!QueueEmpty(&Q))//如果不为空 { m=DeQueue(&Q); w=G.adjlist[m].firstedge; while(w!=NULL) { if(visited[w->adjvex]==0) { visited[w->adjvex]=1; printf(G.adj[w->adjvex].vertex); EnQueue(Q, w->adjvex);} w=w->next; }}} 

三.边学边练（不考算法）

1.写出广度遍历：

答案：12345678

2.写出深度遍历：

本人博客：https://blog.csdn.net/weixin_46654114
本人b站求关注：https://space.bilibili.com/391105864
转载说明：跟我说明，务必注明来源，附带本人博客连接。

请给我点个赞鼓励我吧