数据结构历年考研试题第7章图 (5)

else {if (ivex==i) return (jvex); else return (ivex);}

//返回第一邻接点，ivex和jvex中必有一个等于i

}// FirstAdj 16. [题目分析]本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。

int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。 const n=用户定义的顶点数;

AdjList g ; //用邻接表作存储结构的有向图g。 void dfs(v)

{visited [v]=1; num++; //访问的顶点数＋1

if (num==n) {printf(“%d是有向图的根。\\n”,v); num=0;}//if p=g[v].firstarc; while (p)

{if (visied[p->adjvex]==0) dfs (p->adjvex);

p=p->next;} //while

visited[v]=0; num--; //恢复顶点v

}//dfs

void JudgeRoot()

//判断有向图是否有根，有根则输出之。 {static int i ;

for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。 {num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot

算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。

17. [题目分析] 使用图的遍历可以求出图的连通分量。进入dfs或bfs一次，就可以访问到图的一个连通分量的所有顶点。 void dfs ()

{visited[v]=1; printf ( “=”,v); //输出连通分量的顶点。 p=g[v].firstarc; while (p!=null)

{if（visited[p->adjvex==0]） dfs(p->adjvex); p=p->next; }//while }// dfs void Count()

//求图中连通分量的个数

{int k=0 ; static AdjList g ; //设无向图g有n个结点 for (i=1;i<=n;i++ )

if (visited[i]==0) { printf (\第%d个连通分量:\\n\if }//Count

算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g[i].vertex分量输出。 18. void bfs(AdjList GL，vertype v )

//从v发广度优先遍历以邻接表为存储结构的无向图GL。 {visited[v]=1;

printf( \输出第一个遍历的顶点。

QueueInit(Q); QueueIn(Q ,v); //先置空队列，然后第一个顶点v入队列，设队列容量足够大

while (!QueueEmpty(Q))

{v=QueueOut(Q); p=GL[v].firstarc; //GL是全局变量， v入队列。 while (p!=null)

{if(visited[p->adjvex]==0) {printf(\visited[p->adjvex]=1; QueueIn(Q,p->adjvex);}//if

p=p->next; }//while

}// while (!QueueEmpty(Q)) }//bfs

void BFSCOM()

//广度优先搜索，求无向图Ｇ的连通分量。 { int count=0; //记连通分量个数。 for (i=1;i<=n;i++) visited[i]=0; for (i=1;i<=n;i++)

if (visited[i]==0) {printf(\第%d个连通分量:\\n\bfs(i);}//if

}//BFSCOM

19.请参见上题18。HEAD，MARK，VER，LINK相当于上题GL，visited，adjvex，next。 20. void Traver(AdjList g,vertype v)

//图g以邻接表为存储结构，算法从顶点v开始实现非递归深度优先遍历。

{struct arc *stack[];

visited[v]=1；printf(v); //输出顶点v top=0; p=g[v].firstarc; stack[++top]=p; while(top>0 || p!=null) {while (p)

if (p && visited[p->adjvex]) p=p->next;

else {printf(p->adjvex); visited[p->adjvex]=1;

stack[++top]=p; p=g[p->adjvex].firstarc; }//else

if (top>0) {p=stack[top--]; p=p->next; } }//while }//算法结束。

[算法讨论] 以上算法适合连通图，若是非连通图，则再增加一个主调算法,其核心语句是

for (vi=1;vi<=n;vi++) if (!visited[vi]) Traver(g,vi); 21. （１）限于篇幅，邻接表略。

（２）在邻接点按升序排列的前提下，其dfs和bfs序列分别为BADCEF和BACEDF。 （３）void dfs(v)

{i=GraphLocateVertex(g ,v); //定位顶点 visited[i]=1; printf(v); //输出顶点信息 p=g[i].firstarc; while (p)

{ if (visited[p->adjvex]==0) dfs(g[p->adjvex].vertex); p=p->next;

}//while

}//dfs

void traver( )

//深度优先搜索的递归程序；以邻接表表示的图g是全局变量。

{ for (i=1;i<=n;i++) visited[i]=0; //访问数组是全局变量初始化。 for (vi=v1;vi<=vn;vi++)

if (visited[GraphLocateVertex(g，vi)]==0) dfs(vi); }//算法结束。 22. [题目分析]强连通图指从任一顶点出发，均可访问到其它所有顶点，故这里只给出dfs()过程。

PROC dfs(g:AdjList , v0:vtxptr)

//从v0出发，深度优先遍历以邻接表为存储结构的强连通图g。

TYPE stack=ARRAY[1..n] OF arcptr; //栈元素为弧结点指针，n为顶点个数。 s:stack; top:integer; top:=0 visited[v0]:=1;

write(v0:4); //设顶点信息就是顶点编号；否则要顶点定位。 p:=g[v0]^.firstarc;

WHILE (top>0 || p!=NIL) DO BEGIN WHILE (p!= NIL) DO

IF (visited[p^.adjvex]=1) THEN p:=p^.next; //查未访问的邻接点。 ELSE BEGIN w:=p^.adjvex; visited[w]:=1; top:=top+1; s[top]:=p; p:=g[w].firstarc ;

END； //深度优先遍历。

IF (top>0) THEN BEGIN p:=s[top]; top:=top-1; p:=p^.next END;

END； ENDP；

23. [题目分析] 本题是对无向图Ｇ的深度优先遍历，dfs算法上面已有几处（见20-22）。这里仅给出将连通分量的顶点用括号括起来的算法。为了得出题中的输出结果，各顶点的邻接点要按升序排列。 void Traver( )

{for (i=1;i<=nodes(g);i++) visited[i]=0; //visited是全局变量，初始化。 for (i=1;i<=nodes(g);i++)

if (visied[i]==0) {printf (\if

}//Traver

24.void visit(vertype v) //访问图的顶点v。

void initqueue (vertype Q[]) //图的顶点队列Ｑ初始化。

void enqueue (vertype Q[] ,v) //顶点v入队列Ｑ。 vertype delqueue (vertype Q[]) //出队操作。 int empty (Q) //判断队列是否为空的函数，若空返回１，否则返回０。

vertype firstadj(graph g ,vertype v)//图g中v的第一个邻接点。

vertype nextadj(graph g ,vertype v ,vertype w)//图g中顶点v的邻接点中在w后的邻接点

void bfs (graph g ,vertype v0)

//利用上面定义的图的抽象数据类型，从顶点v0出发广度优先遍历图g。 {visit(v0);

visited[v0]=1; //设顶点信息就是编号，visited是全局变量。 initqueue(Q); enqueue(Q,v0); //v0入队列。 while (!empty(Q))

{v=delqueue(Q); //队头元素出队列。

w=firstadj(g ,v); //求顶点v的第一邻接点 while (w!=0) //w!=0表示w存在。

{if (visited[w]==0) //若邻接点未访问。

{visit(w); visited[w]=1; enqueue(Q,w);}//if w=nextadj(g,v,w); //求下一个邻接点。 }//while }//while }//bfs

void Traver()

//对图g进行宽度优先遍历，图g是全局变量。 {for (i=1;i<=n;i++) visited[i]=0; for (i=1;i<=n;i++)

if (visited[i]==0) bfs(i); } //Traver

25.[题目分析] 本题应使用深度优先遍历。设图的顶点信息就是顶点编号，用num记录访问顶点个数，当num等于图的顶点个数（题中的NODES(G)），输出所访问的顶点序列，顶点序列存在path中，path和visited数组，顶点计数器num，均是全局变量，都已初始化。 void SPathdfs(v0)

//判断无向图Ｇ中是否存在以v0为起点，包含图中全部顶点的简单路径。 {visited[v0]=1; path[++num]=v0;

if (num==nodes(G) //有一条简单路径，输出之。

{for (i=1;i<=num;i++) printf( \//if

p=g[v0].firstarc; while (p)

{if (visited[p->adjvex]==0) SPathdfs(p->adjvex); //深度优先遍历。 p=p->next; //下一个邻接点。 }//while

visited[v0]=0; num--; //取消访问标记，使该顶点可重新使用。 }//SPathdfs

26. 与上题类似，这里给出非递归算法，顶点信息仍是编号。

void AllSPdfs(AdjList g,vertype u,vertype v)

//求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(g,u,v) { int top=0,s[];

s[++top]=u; visited[u]=1; while (top>0 || p)

{p=g[s[top]].firstarc; //第一个邻接点。

while (p!=null && visited[p->adjvex]==1) p=p->next; //下一个访问邻接点表。

if (p==null) top--; //退栈。

else { i=p->adjvex; //取邻接点（编号）。

if (i==v) //找到从u到v的一条简单路径，输出。 {for (k=1;k<=top;k++) printf( \printf( \if

else { visited[i]=1; s[++top]=i; } //else深度优先遍历。 }//else }//while }// AllSPdfs

类似本题的另外叙述的第（2）题 ：u到v有三条简单路径：uabfv，ucdv，ucdefv。 27. （1）[题目分析]D_搜索类似BFS，只是用栈代替队列，入出队列改为入出栈。查某顶点的邻接点时，若其邻接点尚未遍历，则遍历之，并将其压入栈中。当一个顶点的所有邻接点被搜索后，栈顶顶点是下一个搜索出发点。 void D_BFS(AdjList g ,vertype v0)

// 从v0顶点开始，对以邻接表为存储结构的图g进行D_搜索。

{ int s[], top=0; //栈，栈中元素为顶点，仍假定顶点用编号表示。 for (i=1,i<=n;i++) visited[i]=0; //图有n个顶点，visited数组为全局变量。 for (i=1,i<=n;i++) //对n个顶点的图g进行D_搜索。 if (visited[i]==0)

{s[++top]=i; visited[i]=1; printf( \ while (top>0)

{i=s[top--]; //退栈

p=g[i].firstarc; //取第一个邻接点

while (p!=null) //处理顶点的所有邻接点 {j=p->adjvex;

if (visited[j]==0) //未访问的邻接点访问并入栈。 {visited[j]=1; printf( \p=p->next;

1 } //下一个邻接点

}//while(top>0) 2 3 4 } //if 7 }//D_BFS

（2）D_搜索序列：1234675，生成树如图： 5

28，[题目分析] 本题的含义是对有向无环图(DAG)的顶点，以整数适当编号后，可使其邻接矩阵中对角线以下元素全部为零。根据这一要求，可以按各顶点出度大小排序，使出度最大的顶点编号为1，出度次大者编号为2，出度为零的顶点编号为n。这样编号后，可能出现

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新初中教育数据结构历年考研试题第7章图 (5)全文阅读和word下载服务。