资源描述：
《图的遍历及生成树ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图的遍历与求图的连通分量图的遍历:从给定图中任意指定的顶点出发,按照某种方式系统地访问图中的顶点,使每个顶点仅被访问一次,所得到的一个序列访问标志位visit[]遍历前置visit的各元素为0若顶点vi被访问过,则置visit[i]为1深度优先搜索广度优先搜索深度优先搜索首先访问出发顶点v0选择一个与v0相邻接的且末访问过的顶点w访问再从w开始,按深度优先搜索…..每当到达一个其所相邻接的顶点都已被访问过的顶点,则从最后所访问的顶点开始,依次退回到尚有邻接顶点末曾访问过的顶点u,并从u开始进行深序优先
2、搜索…..直到所有顶点都访问过或从任何一个已访问过的顶点出发,再也无法到达末曾访问过的顶点123456789深度优先搜索14253135^124135^234^234^5^12345#include#defineMAXN50#defineMAXN100structl_node{intver;structl_node*link;};typedefstructl_nodeL_NODE;typedefstruct{intver1;intver2;}E_NODE;L_NODE*head[MA
3、XN];intvisit[MAXN];E_NODEe[MAXN];intn,m,u;voidcreat_adj_list(head,n,e,m)L_NODE*head[];E_NODEe[];intn,m;{inti,u,v;L_NODE*p;for(i=1;i<=n;i++)head[i]=NULL;for(i=0;iver=v;p->link=head[u];
4、head[u]=p;p=(L_NODE*)moalloc(sizeof(L_NODE));p->ver=u;p->link=head[v];head[v]=p;}}voidinit(n)intn;{inti;for(i=1;i<=n;i++)visit[i]=0;}voiddfs(u)intu;{L_NODE*t;visit[u]=1;printf(“%d”,u);t=head[u];while(t!=NULL){if(visit[t->ver]==0)dfs(t->ver);t=t->link;}}
5、广度优先搜索法首先访问出发点v然后访问与顶点v邻接的全部顶点w1,w2,….,wt再依次访问与w1,w2,….,wt邻接的全部结点(已访问过的顶点除外)再从这些已访问的顶点出发,依次访问与它们邻接的全部顶点(已访问的顶点除外)依次类推,直到图中所有顶点都访问到或出发顶点V所在的连通分量的所有顶点都有被访问到为止123456789广度优先搜索法14253135^124135^234^234^5^12345广度优先搜索法把队列置空输出出发顶点,置该顶点已被访问的标志让出发顶点进队若队列不空,则取出队首中的
6、顶点V在邻接表中,依次取得与顶点V邻接的各个顶点转(4)若队列空,则处理过程结束voidbfs(u)intu;{structqueuetype{intqa;intqe;intitem[MAXN];}typedefstructqueuetypeQTYPE;intv,w;L_NODE*t;QTYPEqueue;printf(“%4d”,u);visit[u]=1;queue.qa=0;queue.qe=0queue.item[0]=u;while(queue.qa<=queue.qe){v=queue.i
7、tem[queue.qa++];t=head[v];while(t!=NULL){w=t->ver;if(visit[w]==0){printf(“%4d”,w);visit[w]=1;queue.item[++queue.qe]=w;}t=t->link;}}}求图的连通分量对图的每一个顶点进行检验若被访问过,则该顶点落在已被求出的连通分量上若末被访问过,则从该顶点出发遍历图,便可求得图的另一个连通分量生成树和最小生成树生成树:设G是一个连通无向图,若G’是包含G中所有顶点的一个无回路的连通子图,则
8、称G’是G的一棵生成树142536879142536879142536879生成树从G中任一顶点出发,遍历图中的所有顶点,在遍历过程中,将E分成两个集合T(G)和B(G),其中T(G)是遍历时所通过的边集,B(G)是剩余的边集,则G’=(V,T(G))是G的一棵生成树dfs生成树bfs生成树14253687914253616918201914511622最小生成树一个带权连通无向图G的最小生成树是G的所有生成树中边上的权之和最小的一棵生成树MST性质:设
