图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

关注
图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)www.shan-machinery.com//访问标志数组int visited[MAX] = {0};//用邻接表方式实现深度优先搜索(递归方式)//v 传入的是第一个需要访问的顶点void DFS(MGraph G, int v){//图的顶点的搜索指针ArcNode *p;//置已访问标记visited[v] = 1;//输出被访问顶点的编号printf("%d", v);//p指向顶点v的第一条弧的弧头结点p = G.vertices[v].firstarc;while (p != NULL){//若p->adjvex顶点未访问,递归访问它if (visited[p->adjvex] == 0){DFS(G, p->adjvex);}//p指向顶点v的下一条弧的弧头结点p = p->nextarc;}}

广度优先搜索(BFS)

方法:从图的某一结点出发,首先依次访问该结点的所有邻接顶点 Vi1, Vi2, …, Vin 再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点,重复此过程,直至所有顶点均被访问为止。

顶点的访问次序

实现过程:依靠队列和一维数组来实现

1 #include 2 #include 3 using namespace std; 4 5 const int MAX = 10; 6 //辅助队列的初始化,置空的辅助队列Q,类似二叉树的层序遍历过程 7 queue q; 8 //访问标记数组 9 bool visited[MAX];10 //图的广度优先搜索算法11 void BFSTraverse(Graph G, void (*visit)(int v))12 {13 int v = 0;14 //初始化访问标记的数组15 for (v = 0; v < G.vexnum; v++)16 {17 visited[v] = false;18 }19 //依次遍历整个图的结点20 for (v = 0; v < G.vexnum; v++)21 {22 //如果v尚未访问,则访问 v23 if(!visited[v])24 {25 //把 v 顶点对应的数组下标处的元素置为真,代表已经访问了26 visited[v] = true;27 //然后v入队列,利用了队列的先进先出的性质28 q.push(v);29 //访问 v,打印处理30 cout = 0; w = NextAdjVex(G,u,w))39 {40 //w为u的尚未访问的邻接顶点41 if (!visited[w])42 {43 visited[w] = true;44 //然后 w 入队列,利用了队列的先进先出的性质45 q.push(w);46 //访问 w,打印处理47 cout https://www.shan-machinery.com