国外做调查的网站,十堰响应式网站,网页在线代理浏览,免费咨询图片素材对于一个有向图无向图#xff0c;我们下面介绍第二种遍历方式。
广度优先搜索#xff0c;即优先对同一层的顶点进行遍历。
如下图所示#xff1a; 该例子#xff0c;我们有六个顶点#xff0c; 十条边。
对于广度优先搜索#xff0c;我们先搜索a#xff0c;再搜索abc…对于一个有向图无向图我们下面介绍第二种遍历方式。
广度优先搜索即优先对同一层的顶点进行遍历。
如下图所示 该例子我们有六个顶点 十条边。
对于广度优先搜索我们先搜索a再搜索abcd最后搜索ef。
而对于广度优先搜索我们需要一个队列来辅助我们进行广度优先搜索先进先出。
同时我们还需要一个visit数组来判断某个顶点是否已经被搜索过了。
#includestdio.h#define MAX_NUM 100
typedef struct ArcNode{ //边 int adjvex;struct ArcNode *next;int weight;
}ArcNode; typedef struct{ //头结点 char vertex;ArcNode *firstarc;
}VNode;typedef VNode Adjlist[MAX_NUM]; //邻接表 typedef struct{ //建立邻接表 Adjlist adjlist;int vexnum,arcnum;
}ALGraph;void DFSTraverse(ALGraph *G) //深度优先搜索
{int v;int visit[G-vexnum];for(v0;vG-vexnum;v){visit[v] 0;}for(v0;vG-vexnum;v){if(visit[v]0)DFS(G,v,visit);}
}void DFS(ALGraph *G,int v,int *visit) //深度优先搜索后继结点判断
{int w;ArcNode *p;printf(访问顶点:%c\n,G-adjlist[v].vertex);visit[v] 1;p G-adjlist[v].firstarc;while(p){w p-adjvex;if(visit[w]0)DFS(G,w,visit);p p-next;}
}void BFSTraverse(ALGraph *G) //广度优先搜索后继节点判断
{int v,w,u;int Q[G-vexnum1],r,f;int visit[G-vexnum];for(v0;vG-vexnum;v)visit[v] 0;f 0,r 0;for(v0;vG-vexnum;v){if(visit[v]0){visit[v] 1;printf(第%d个结点是-%c\n,v,G-adjlist[v].vertex);Q[r] v;r (r1)%(G-vexnum1);while(f!r){u Q[f];f (f1)%(G-vexnum1);ArcNode *p G-adjlist[u].firstarc;while(p){if(visit[p-adjvex]0){visit[p-adjvex] 1;printf(第%d个结点是-%c\n,p-adjvex,G-adjlist[p-adjvex].vertex);Q[r] p-adjvex;r (r1)%(G-vexnum1);}p p-next;}}}}
}int main()
{return 0;
}
运行结果如下
