{if(pre==null)g[i].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。 else {pre=p; p=p->next;} //沿链表继续查找 p=g[j].firstarc; pre=null; //删顶点j 的边结点(j,i) while (p)
if (p->adjvex==i)
{if(pre==null)g[j].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。 else {pre=p; p=p->next;} //沿链表继续查找 }// DeletEdge
算法中假定给的i，j均存在，否则应检查其合法性。若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。
8．假设有向图以邻接表存储，试编写算法删除弧
void DeleteArc（AdjList g,vertype vi, vertype vj）
//删除以邻接表存储的有向图g的一条弧
if (p->adjvex==j)
{if(pre==null) g[i].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。 else { pre=p; p=p->next;} }
9．设有向图用邻接表表示，图有n个顶点，表示为1至n，试写一个算法求顶点k的入度(1 在有向图的邻接表中，求顶点的出度容易，只要简单在该顶点的邻接点链表中查结点个数即可。而求顶点的入度，则要遍历整个邻接表。 参考答案： 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 (p->adjvex==k) count++; p=p->next; }//while }//if return(count); //顶点k的入度. } 10．试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值。(设图G已用邻接表存储) 参考答案： 使用图的遍历可以求出图的连通分量。进入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\}//Count 算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g[i].vertex分量输出。 11．设无向图G已用邻接表结构存储，顶点表为GL[n] (n为图中顶点数)，试用“广度优先搜索”方法，写出求图G中各连通分量的C语言描述算法：BFSCOM(GL)。（注：算法中可调用队列操作的基本算法。） 参考答案： 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(\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\}//BFSCOM 12．写出图的深度优先搜索DFS算法的非递归算法。 参考答案： 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); 13．设计算法以实现对无向图G的深度遍历，要求：将每一个连通分量中的顶点以一个表的形式输出。例如，下图的输出结果为：（1，3）（2，6，7，4，5，8）（9，10） （注：本算法中可以调用以下几个函数： firstadj（g,v）——返回图g中顶点v的第一个邻接点的号码，若不存在，则返回0； nextadj（g,v,w）——返回图g中顶点v的邻接点中处于w之后的邻接点的号码，若不存在，则返回0。 nodes（g）——返回图g中的顶点数） 参考答案： 本题是对无向图Ｇ的深度优先遍历，dfs算法见前述。这里仅给出将连通分量的顶点用括号括起来的算法。为了得出题中的输出结果，各顶点的邻接点要按升序排列。 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 (\}//Traver 14．设计算法以判断给定的无向图G中是否存在一条以V0为起点的包含所有顶点的简单路径，若存在，返回TRUE，否则，返回FALSE（注：本算法中可以调用以下几个函数：FIRSTADJ（G，V）——返回图G中顶点V的第一个邻接点的号码，若不存在，则返回0；NEXTADJ（G，V，W）——返回图G中顶点V的邻接点中处于W之后的邻接点的号码，若不存在，则返回0；NODES（G）——返回图G中的顶点数） 参考答案： 本题应使用深度优先遍历。设图的顶点信息就是顶点编号，用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( \p=g[v0].firstarc; while (p) {if (visited[p->adjvex]==0) SPathdfs(p->adjvex); //深度优先遍历。 p=p->next; //下一个邻接点。 }//while visited[v0]=0; num--; //取消访问标记，使该顶点可重新使用。 }//SPathdfs 15．已有邻接表表示的有向图， 请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。要求：先描述图的存储结构，并简述算法思路；查找邻接点等图的运算要自己实现。（尽量采用非递归算法） 参考答案： 非递归算法，顶点信息仍是编号。 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( \else { visited[i]=1; s[++top]=i; } //else深度优先遍历。 }//else }//while }// AllSPdfs 16．图的D_搜索类似与BFS，不同之处在于使用栈代替BFS中的队列，入出队列的操作改为入出栈的操作，即当一个顶点的所有邻接点被搜索之后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。 （1）用邻接表做存储结构，写一个D_搜索算法； （2）用D_搜索方法的访问次序和相应的生成树，当从某顶点出发搜索它的邻接点，请按邻接点序号递增序搜索，以使答案唯一。 参考答案： （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; } //下一个邻接点 }//while(top>0) } //if }//D_BFS （2）D_搜索序列：1234675，生成树如图： 17．我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。 参考答案： 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。