发布时间 : 星期日 文章数据结构历年考研试题第7章图更新完毕开始阅读
14．[题目分析]有几种方法判断有向图是否存在环路，这里使用拓扑排序法。对有向图的顶点进行拓扑排序，若拓扑排序成功，则无环路；否则，存在环路。题目已假定有向图用十字链表存储，为方便运算，在顶点结点中，再增加一个入度域indegree，存放顶点的入度。入度为零的顶点先输出。为节省空间，入度域还起栈的作用。值得注意的是，在邻接表中，顶点的邻接点非常清楚，顶点的单链表中的邻接点域都是顶点的邻接点。由于十字链表边（弧）结点个数与边（弧）个数相同（不象无向图边结点个数是边的二倍），因此，对某顶点v, 要判断其邻接点是headvex还是tailvex。 int Topsor(OrthList g)
//判断以十字链表为存储结构的有向图g是否存在环路，如是，返回1，否则，返回0。
{int top=0; //用作栈顶指针 for (i=1;i<=n;i++) //求各顶点的入度。设有向图g有n个顶点，初始时入度域均为0
{p=g[i].firstin; //设顶点信息就是顶点编号，否则，要进行顶点定位 while(p)
{g[i].indegree++; //入度域增1
if (p->headvex==i) p=p->headlink; else p=p->taillink; //找顶点i的邻
接点
}//while(p) }//for
for (i=1;i<=n;i++) //建立入度为0的顶点的栈
if (g[i].indegree==0) {g[i].indegree=top; top=i; } m=0; //m为计数器，记输出顶点个数 while (top<>0)
{i=top; top=g[top].indegree; m++; //top指向下一入度为0的顶点 p=g[i].firstout;
while (p) //处理顶点i的各邻接点的入度
{if (p->tailvex==i) k=p->headvex; else k=p->tailvex;}//找顶点i的邻接
点
g[k].indegree--; //邻接点入度减1
if (g[k].indegree==0) {g[k].indegree=top; top=k; } //入度为0的顶点再入栈
if (p->headvex==i) p=p->headlink; else p=p->taillink;//找顶点i的下
一邻接点
}//while (p) }// while (top<>0)
if (m 15. int FirstAdj(AdjMuList g , vertype v) //在邻接多重表g中，求v的第一邻接点，若存在，返回第一邻接点，否则，返回0。 {i=GraphLocateVertex(g,v); //确定顶点v在邻接多重表向量中的下标，不考虑不存在v的情况。 p=g[i].firstedge; //取第一个边结点。 if (p==null ) return (0); 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[]) //图的顶点队列Ｑ初始化。