第7章图答案(编辑修改稿)

第7章图答案(编辑修改稿)内容摘要：

adjvex=i。 snext=gin[j].firstarc。 gin[j].firstarc=s。 p=pnext。 //下一个邻接点。 }//while }//for } 6. void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm) //将图的邻接表表示转换为邻接矩阵表示。 {for (i=1。 i=n。 i++) //设图有 n个顶点，邻接矩阵初始化。 for (j=1。 j=n。 j++) gm[i][j]=0。 for (i=1。 i=n。 i++) {p=gl[i].firstarc。 //取第一个邻接点。 while (p!=null) {gm[i][padjvex]=1。 p=pnext。 }//下一个邻接点 }//for }//算法结束 7. void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl ) //将图的邻接矩阵表示法转换为邻接表表示法。 {for (i=1。 i=n。 i++) //邻接表表头向量初始化。 {scanf(amp。 gl[i].vertex)。 gl[i].firstarc=null。 } for (i=1。 i=n。 i++) for (j=1。 j=n。 j++) if (gm[i][j]==1) {p=(ArcNode *)malloc(sizeof(ArcNode))。 //申请结点空间。 padjvex=j。 //顶点 I的邻接点是 j pnext=gl[i].firstarc。 gl[i].firstarc=p。 //链入顶点 i的邻接点链表中 } }//end [算法讨论 ] 算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。 8.[题目分析 ] 在有向图中，判断顶点 Vi 和顶点 Vj间是否有路径，可采用遍 历的方法，从顶点 Vi出发，不论是深度优先遍历（ dfs）还是宽度优先遍历（ bfs），在未退出 dfs或 bfs前 ,若访问到 Vj，则说明有通路，否则无通路。 设一全程变量 flag。 初始化为 0，若有通路，则 flag=1。 算法 1： int visited[]=0。 //全局变量，访问数组初始化 int dfs(AdjList g , vi) //以邻接表为存储结构的有向图 g，判断顶点 Vi 到 Vj 是否有通路 ,返回 1 或 0 表示有或无 { visited[vi]=1。 //visited是访问数组，设顶点的信息就 是顶点编号。 p=g[vi].firstarc。 //第一个邻接点。 while ( p!=null) { j=padjvex。 if (vj==j) { flag=1。 return（ 1）。 } //vi 和 vj 有通路。 if (visited[j]==0) dfs(g,j)。 p=pnext； }//while if (!flag) return(0)。 }//结束 [算法讨论 ] 若顶点 vi 和 vj 不是编号，必须先用顶点定位函数 ,查出其在邻接表顶点向量中的下标 i 和 j。 下面算法 2输出 vi 到 vj 的路径，其思想是用一个栈存放遍历的顶点，遇到顶点 vj时输出路径。 算法 2： void dfs(AdjList g , int i) //有向图 g的顶点 vi（编号 i）和顶点 vj（编号 j）间是否有路径，如有，则输出。 {int top=0,stack[]。 //stack是存放顶点编号的栈 visited[i]=1。 //visited 数组在进入 dfs前已初始化。 stack[++top]=i。 p=g[i].firstarc。 /求第一个邻接点 . while (p) {if (padjvex==j) {stack[++top]=j。 printf( 顶点 vi 和 vj 的路径为： \n)。 for (i=1。 i=top。 i++) printf( %4d,stack[i])。 exit(0)。 }//if else if (visited[padjvex]==0) {dfs(g,gadjvex)。 top。 p=pnext。 }//else if }//while }//结束算法 2 算法 3：本题用非递归算法求解。 int Connectij (AdjList g , vertype vi , vj ) //判断 n个顶点以邻接表表示的有向图 g中，顶点 Vi 各 Vj 是否有路径，有则返回 1，否则返回 0。 { for (i=1。 i=n。 i++) visited[i]=0。 //访问标记数组初始化。 i=GraphLocateVertex(g,vi)。 //顶点定位，不考虑 vi或 vj不在图中的情况。 j=GraphLocateVertex(g,vj)。 int stack[],top=0。 stack[++top]=i。 while(top0) {k=stack[top]。 p=g[k].firstarc。 while(p!=null amp。 amp。 visited[padjvex]==1) p=pnext。 //查第 k个链表中第一个未访问的弧结点。 if(p==null) top。 else {i=padjvex。 if(i==j) return(1)。 //顶点 vi和 vj 间有路径。 else {visited[i]=1。 stack[++top]=i。 }//else }//else }while return(0)。 } //顶点 vi和 vj 间无通路。 9. void DeletEdge(AdjList g,int i,j) //在用邻接表方式存储的无向图 g中，删除边 (i,j) {p=g[i].firstarc。 pre=null。 //删顶点 i 的边 结点 (i,j),pre是前驱指针 while (p) if (padjvex==j) {if(pre==null)g[i].firstarc=pnext。 else prenext=pnext。 free(p)。 }//释放结点空间。 else {pre=p。 p=pnext。 } //沿链表继续查找 p=g[j].firstarc。 pre=null。 //删顶点 j 的边结点 (j,i) while (p) if (padjvex==i) {if(pre==null)g[j].firstarc=pnext。 else prenext=pnext。 free(p)。 }//释放结点空间。 else {pre=p。 p=pnext。 } //沿链表继续查找 }// DeletEdge [算法讨论 ] 算法中假定给的 i， j 均存在，否则应检查其合法性。 若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标 i和 j。 10. void DeleteArc（ AdjList g,vertype vi,vj） //删除以邻接表存储的有向图 g的一条弧 vi,vj，假定顶点 vi和 vj存在 {i=GraphLocateVertex(g,vi)。 j=GraphLocateVertex(g,vj)。 //顶点定位 p=g[i].firstarc。 pre=null。 while (p) if (padjvex==j) {if(pre==null) g[i].firstarc=pnext。 else prenext=pnext。 free(p)。 }//释放结 点空间。 else { pre=p。 p=pnext。 } }//结束 11. void InsertArc ( OrthList g ,vertype vi,vj) //在以十字链表示的有向图 g中插入弧 vi,vj { i=GraphLocateVertex(g,vi)。 //顶点定位 . j=GraphLocateVertex(g,vj)。 p=(OrArcNode *)malloc(sizeof(OrArcNode))。 p=headvex=j。 p=tailvex=i。 //填写弧 结点信息并插入十字链表。 pheadlink=g[j].firstin。 g[j].firstin=p。 ptaillink=g[i].firstout。 g[i].firstout=p。 }//算法结束 12. [题目分析 ]在有向图的邻接表中，求顶点的出度容易，只要简单在该顶点的邻接点链表中查结点个数即可。 而求顶点的入度，则要遍历整个邻接表。 int count (AdjList g , int k ) //在 n个顶点以邻接表表示的有向图 g中，求指定顶点 k(1=k=n)的入度。 { int count =0。 for (i=1。 i=n。 i++) //求顶点 k的入度要遍历整个邻接表。 if(i!=k) //顶点 k的邻接链表不必计算 {p=g[i].firstarc。 //取顶点 i 的邻接表。 while (p) {if (padjvex==k) count++。 p=pnext。 }//while }//if return(count)。 //顶点 k的入度 . } 13. [题目分析 ]有向图判断回路要比无向图复杂。 利用深度优先遍历，将顶 点分成三类：未访问；已访问但其邻接点未访问完。 已访问且其邻接点已访问完。 下面用 0， 1， 2表示这三种状态。 前面已提到，若 dfs（ v）结束前出现顶点 u 到 v 的回边，则图中必有包含顶点 v和 u的回路。 对应程序中 v的状态为 1，而 u是正访问的顶点，若我们找出 u的下一邻接点的状态为 1，就可以输出回路了。 void Print(int v,int start ) //输出从顶点 start开始的回路。 {for(i=1。 i=n。 i++) if(g[v][i]!=0 amp。 amp。 visited[i]==1 ) //若存 在边（ v,i），且顶点 i的状态为 1。 {printf(“%d”,v)。 if(i==start) printf(“ \n”)。 else Print(i,start)。 break。 }//if }//Print void dfs(int v) {visited[v]=1。 for(j=1。 j=n。 j++ ) if (g[v][j]!=0) //存在边 (v,j) if (visited[j]!=1) {if (!visited[j]) dfs(j)。 }//if else {cycle=1。 Print(j,j)。 } visited[v]=2。 }//dfs void find_cycle() //判断是否有回路，有则输出邻接矩阵。 visited数组为全局变量。 {for (i=1。 i=n。 i++) visited[i]=0。 for (i=1。 i=n。 i++ ) if (!visited[i]) dfs(i)。 }//find_cycle 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。