君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
数据结构第7章_图_答案
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口4534人阅读
众所周知常用的图遍历方式有深度优先遍历和广度优先遍历两种,那么我首先来看看这两种算法的具体实现，我们用G[Max][Max]表示图的邻接矩阵。
//三个全局变量
bool Visited[Max];//访问标志
void(*VisFunction)(int Vertex);//访问顶点
bool(*IsEdgeFuncion)(int G[][Max],intv,int u);//判断连边
深度优先递归版本：
void Depth_First(intG[][Max],void(*VisFunc)(int),bool(*IsEdgeFun)(int G[][Max],int, int),intBeginVer)
&&&& for(i=0;i&Mi++)Visited[i]=
&&&& VisFunction=VisF
&&&& IsEdgeFuncion=IsEdgeF
&&&& if(BeginVer&0||BeginVer&=Max)BeginVer=0;
&&&& DFS(G,BeginVer);
void DFS(int G[][Max],int BeginVer)
&&&& Visited[BeginVer]=
&&&& VisFunction(BeginVer);
&&&& for(inti=0;i&Mi++)
&&&&&&&&&& if(IsEdgeFuncion(G,BeginVer,i)&&!Visited[i]){
&&&&&&&&&&&&&&&& DFS(G,i);
&&&&&&&&&& }
深度优先非递归版本：
void Depth_FirstVer(intG[][Max],void(*VisFunc)(int),bool(*IsEdgeFun)(int G[][Max],int, int),intBeginVer)
&&&& usingstd::
&&&& stack&int&MyS
&&&& for(i=0;i&Mi++)Visited[i]=
&&&& VisFunction=VisF
&&&& IsEdgeFuncion=IsEdgeF
&&&& if(BeginVer&0||BeginVer&=Max)BeginVer=0;
&&&& MyStack.push(BeginVer);//Initialization
&&&& Visited[BeginVer]=
&&& //++Number；//改进
&&&& VisFunction(BeginVer);
&&&& while(!MyStack.empty()){
&&&&&&&Vertex=MyStack.top();
&&&& && int j=0;
&&&&&&&for(;j&Mj++){
&&&&&&&&&&&if(IsEdgeFuncion(G,Vertex,j)&&!Visited[j]){
&&&&&&&&&&&&&&&&&&&&& MyStack.push(j);
&&&&&&&&&&&&&&&&&&&&& Visited[j]=
&&&&&&&&&&&&&&&&&&&&& VisFunction(j);
&&&&&&&&&&&&&&&&&&&&& //if(++Number==Max)//改进
&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&& }
&&&&&&&&&& }
&&&&&&&&&& if(j&=Max)MyStack.pop();
深度优先的时间复杂度分析
我们用非递归版本来分析（比较清楚），我们知道在遍历过程中，每个顶点都要进一次栈且仅仅一次，n个顶点就会有n次进栈，现在我们在分析一下，每一次进栈后做什么呢？
当顶点u进栈后，就要以u为当前点继续遍历，也就说要寻找它的下一个邻接点v，时间为o(n),当沿着v这个分支遍历结束后又会回到u这点，找下一个没访问的邻接点v’（如果有的的话）。然后沿着v’分支继续遍历，因此对每次进栈可能需要o（cn）次寻找下一个元素。因此总的时间复杂度为0（n2）=c1n+c2n+…cnn；
从这个分析我们可以改进上面的算法，用一个变量（Number）来记录已经访问过的元素个数，一点Number等于顶点个数时就可以直接退出了，而不必返回去访问一些没用的分支了。
当图用邻接表储存时，那么当当顶点u进栈后，要寻找它的下一个邻接点v，时间为o(e1),其中e1为u的邻接边个数, 此总的时间复杂度为0(n+e)=n+e1+e2+…+en；其中e= e1+e2+…+en为无向图中边数，有向图弧数。O(n)是初始化访问标志等所耗时间。
void BFS(intG[][Max],void(*VisFunc)(int),bool(*IsEdgeFun)(int G[][Max],int, int),intBeginVer)
&&&&& usingstd::
&&&&& queue&int&M
&&&&& for(i=0;i&Mi++)Visited[i]=
&&&&& VisFunction=VisF
&&&&& IsEdgeFuncion=IsEdgeF
&&&&& if(BeginVer&0||BeginVer&=Max)BeginVer=0;
&&&&& Myqueue.push(BeginVer);
&&&&& Visited[BeginVer]=
&&&&& VisFunction(BeginVer);
&&&&& intV
&&&&& while(!Myqueue.empty()){
&&&& &&&&&&Vertex=Myqueue.front();
&&&&&&&&&Myqueue.pop();
&&&&&&&&&& for(intj=0;j&Mj++){
&&&&&&&&&&&&&&&& if(IsEdgeFuncion(G,Vertex,j)&&!Visited[j]){
&&&&&&&&&&&&&&&&&&&&& Myqueue.push(j);
&&&&&&&&&&&&&&&&&&&&& Visited[j]=
&&&&&&&&&&&&&&&&&&&&& VisFunction(j);
&&&&&&&&&&&&&&&& }
&&&&&&&&&& }
广度优先时间复杂度分析：
在广度优先的遍历中每个顶点都要进（出）一次列队且仅仅一下（类似于深度优先遍历的进栈），对于每一个顶点u出列队后,要访问的所有邻接点，时间为o(n),因此我们可知广度优先遍历和深度优先遍历总的时间复杂度是一样的为o(n2)或o(n+e)
对比深度优先和广度优先
他们都能实现对图的遍历，且时间复杂度也是一样的。但对于同一个图他们的访问顺序是不一样的。这样的不一样可能会影响他们的具体应用。
从上面的算法（都看非递归本版）可以看出，深度优先遍历时使用的stack，stack的原则是先进后出，且每一次进栈后，马上跳出当前的for循环。以当前进栈元素为起点继续往下遍历，如果没能找到一个合适的元素（j&=Max）那么就将当前元素出栈，这样保证了能沿着分支回到父节点。
而在广度优先使用的是queue，queue的原则是先进先出，且每一出列队后，以出队元素为起点，遍历它所有的邻接点。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：12156次
排名：千里之外君，已阅读到文档的结尾了呢~~
解方程练习题及答案 水浒传练习..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
第7章图练习题答案
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口数据结构(Java)图_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
数据结构(Java)图
上传于||文档简介
&&这​是​j​a​v​a​数​据​结​构​图​的​相​关​课​件​,​里​面​包​含​图​相​关​介​绍​及​基​础​知​识
大小：4.63MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢&&/&&&&/&&&&/&&
图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。
由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：
① 在图结构中，没有一个&自然&的首结点，图中任意一个顶点都可作为第一个被访问的结点。
② 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
③ 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
④ 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
图的遍历通常有深度优先搜索和广度优先搜索两种方式，下面分别介绍。
8.3.1 深度优先搜索
深度优先搜索（Depth_Fisrst Search）遍历类似于树的先根遍历，是树的先根遍历的推广。
假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点发v 出发，访问此顶点，然后依次从v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和v 有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
以图8.17 的无向图G5 为例，进行图的深度优先搜索。假设从顶点v1 出发进行搜索，在访问了顶点v1 之后，选择邻接点v2。因为v2 未曾访问，则从v2 出发进行搜索。依次类推，接着从v4 、v8 、v5 出发进行搜索。在访问了v5 之后，由于v5 的邻接点都已被访问，则搜索回到v8。由于同样的理由，搜索继续回到v4，v2 直至v1，此时由于v1 的另一个邻接点未被访问，则搜索又从v1 到v3，再继续进行下去由此，得到的顶点访问序列为：
显然，这是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited[0:n-1], ，其初值为FALSE ，一旦某个顶点被访问，则其相应的分量置为TRUE。
从图的某一点v 出发，递归地进行深度优先遍历的过程如算法8.4 所示。
void DFS(Graph G,int v )
{ /*从第v 个顶点出发递归地深度优先遍历图G*/
visited[v]=TRUE;VisitFunc(v); /*访问第v 个顶点*/
for(w=FisrAdjVex(G,v);w; w=NextAdjVex(G,v,w))
if (!visited[w]) DFS(G,w); /*对v 的尚未访问的邻接顶点w 递归调用DFS*/
算法8.5 和算法8.6 给出了对以邻接表为存储结构的整个图G 进行深度优先遍历实现的C 语言描述。
void DFSTraverseAL(ALGraph *G)
{/*深度优先遍历以邻接表存储的图G*/
for (i=0;i&G-&n;i++)
visited[i]=FALSE; /*标志向量初始化*/
for (i=0;i&G-&n;i++)
if (!visited[i]) DFSAL(G,i); /*vi 未访问过，从vi 开始DFS 搜索*/
}/*DFSTraveseAL*/
void DFSAL(ALGraph *G,int i)
{/*以Vi 为出发点对邻接表存储的图G 进行DFS 搜索*/
EdgeNode *p;
printf(&visit vertex:V%c\n&,G-&adjlist[i].vertex);/*访问顶点Vi*/
visited[i]=TRUE; /*标记Vi 已访问*/
p=G-&adjlist[i]. /*取Vi 边表的头指针*/
while(p) /*依次搜索Vi 的邻接点Vj，j=p-&adjva*/
{if (!visited[p-&adjvex]) /*若Vj 尚未访问，则以Vj 为出发点向纵深搜索*/
DFSAL(G,p-&adjvex);
p=p-& /*找Vi 的下一个邻接点*/
}/*DFSAL*/
分析上述算法，在遍历时，对图中每个顶点至多调用一次DFS 函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O(n2) ，其中n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e) 。
8.3.2 广度优先搜索
广度优先搜索（Breadth_First Search） 遍历类似于树的按层次遍历的过程。假设从图中某顶点v 出发，在访问了v 之后依次访问v 的各个未曾访问过和邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使&先被访问的顶点的邻接点&先于&后被访问的顶点的邻接点&被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程中以v 为起始点，由近至远，依次访问和v 有路径相通且路径长度为1,2,&的顶点。
例如，对图8.17 所示无向图G5 进行广度优先搜索遍历，首先访问v1 和v1 的邻接点v2 和v3，然后依次访问v2 的邻接点v4 和v5 及v3 的邻接点v6 和v7，最后访问v4 的邻接点v8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由些完成了图的遍历。得到的顶点访问序列为：
v1&v2 &v3 &v4& v5& v6& v7 &v8
和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、&的顶点，需附设队列以存储已被访问的路径长度为1、2、& 的顶点。
从图的某一点v 出发，递归地进行广度优先遍历的过程如算法8.7 所示。
void BFSTraverse(Graph G, Status(*Visit)(int v))
{/*按广度优先非递归遍历图G。使用辅助队列Q 和访问标志数组visited*/
for (v=0;v&G,++v)
visited[v]=FALSE
InitQueue(Q); /*置空的国债队列Q*/
if (!visited[v]) /*v 尚未访问*/
{EnQucue(Q,v); /*v 入队列*/
while (!QueueEmpty(Q))
{ DeQueue(Q,u); /*队头元素出队并置为u*/
visited[u]=TRUE; visit(u); /*访问u*/
for(w=FistAdjVex(G,u); w=NextAdjVex(G,u,w))
if (!visited[w]) EnQueue(Q,w); /*u 的尚未访问的邻接顶点w 入队列Q*/
}/*BFSTraverse*/
算法8.8 和算法8.9 给出了对以邻接矩阵为存储结构的整个图G 进行深度优先遍历实现的C 语言描述。
void BFSTraverseAL(MGraph *G)
{/*广度优先遍历以邻接矩阵存储的图G*/
for (i=0;i&G-&n;i++)
visited[i]=FALSE; /*标志向量初始化*/
for (i=0;i&G-&n;i++)
if (!visited[i]) BFSM(G,i); /* vi 未访问过，从vi 开始BFS 搜索*/
}/*BFSTraverseAL*/
void BFSM(MGraph *G,int k)
{/*以Vi 为出发点，对邻接矩阵存储的图G 进行BFS 搜索*/
CirQueue Q;
InitQueue(&Q);
printf(&visit vertex:V%c\n&,G-&vexs[k]); /*访问原点Vk*/
visited[k]=TRUE;
EnQueue(&Q,k); /*原点Vk 入队列*/
while (!QueueEmpty(&Q))
{i=DeQueue(&Q); /*Vi 出队列*/
for (j=0;j&G-&n;j++) /*依次搜索Vi 的邻接点Vj*/
if (G-&edges[i][j]==1 && !visited[j]) /*若Vj 未访问*/
{printf(&visit vertex:V%c\n&,G-&vexs[j]); /*访问Vj */
visited[j]=TRUE;
EnQueue(&Q,j); /*访问过的Vj 入队列*/
分析上述算法，每个顶点至多进一次队列。遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。
推荐文章 TOP10}