7.16 试在无向图的邻接矩阵和邻接链表上实现如下算法：
(1)往图中插入一个顶点
(2)往图中插入一条边
(3)删去图中某顶点
(4)删去图中某条边
解：
(一)用邻接矩阵表示
#define MaxVertexNum l00 //最大顶点数，应由用户定义
typedef char VertexType； //顶点类型应由用户定义
typedef int EdgeType； //边上的权值类型应由用户定义
typedef struct{
VextexType vexs[MaxVertexNum] //顶点表
EdeType edges[MaxVertexNum][MaxVertexNum];
//邻接矩阵，可看作边表
int n，e； //图中当前的顶点数和边数
}MGragh；
(1)往图中插入一个顶点
void AddVertexMGraph(MGraph *G,VertexType x)
{//往无向图的邻接矩阵中插入顶点
if (G->n>=MaxVertexNum)
Error("顶点数太多")；
G->vexs[G->n]=x;//将新顶点输入顶点表
G->n++；//顶点数加1
}
(2)往图中插入一条边
void AddedgeMGraph(MGraph *G,VertexType x,VertexType y)
{//往无向图的邻接矩阵中插入边(x,y)
int i,j,k;
i=-1;j=-1;
for(k=0;k<G->n;k++)//查找X，Y的编号
{ if (g->vexs[k]===x) i=k;
if (g->vexs[k]==y) j=k;
}
if (i==-1||j==-1) Error("结点不存在");
else {//插入边(x,y)
g->vex[i][j]=1;
g->vex[j][i]=1;
G->e++;//边数加1
}
}
(3)删去图中某顶点
void DeleteVertexMGraph(MGraph *G,VertexType x)
{//无向图的邻接矩阵中删除顶点x
int i,k,j;
i=-1;
for(k=0;k<G->n;k++)//查找X的编号
if (g->vexs[k]=x) i=k;
if (i==-1) Error("结点不存在");
else {//删除顶点以及边
k=0;//求出与x结点相关联的边数k
for (j=0;j<G->n;j++)
if (g->vexs[i][j]==0) k++;
G->e=G->e-k;//设置新的边数
for (k=i+1;k<G->n;k++)//在邻接矩阵中删除第i行
for(j=0;j<G->n;j++)
g->vexs[k-1][j]=g->vexs[k][j];
for (k=i+1;k<G->n;k++)//在邻接矩阵中删除第i列
for(j=0;j<G->n;j++)
g->vexs[j][k-1]=g->vexs[j][k];
G->n--;//总结点数-1
}
}
(4)删去图中某条边
void DeleteedgeMGraph(MGraph *G,VertexType x,VertexType y)
{//无向图的邻接矩阵中删除边(x,y)
int i,j,k;
i=-1;j=-1;
for(k=0;k<G->n;k++)//查找X，Y的编号
{ if (g->vexs[k]=x) i=k;
if (g->vexs[k]=y) j=k;
}
if (i==-1||j==-1) Error("结点不存在");
else if (g->vexs[i][j]!=1)
{//删除边(x,y)
g->vex[i][j]=0;
g->vex[j][i]=0;
G->e--;//边数加1
}
}
(二)用邻接表表示
typedef struct node{//边表结点
int adjvex； //邻接点域
struct node *next； //链域
//若要表示边上的权，则应增加一个数据域
}EdgeNode;
typedef struct vnode{ //顶点表结点
VertexType vertex； //顶点域
EdgeNode *firstedge；//边表头指针
}VertexNode；
typedef VertexNode AdjList[MaxVertexNum]；//AdjList是邻接表类型
typedef struct{
AdjList adjlist；//邻接表
int n，e； 图中当前顶点数和边数
}ALGraph； //对于简单的应用，无须定义此类型，可直接使用AdjList类型。
(1)往图中插入一个顶点
void AddVertexALGraPh(ALGrahp *G,VertexType x)
{//往无向图的邻接表表示中插入一个顶点
if (G->n>=MaxVertexNum)
Error("顶点数太多")；
G->adjlist[G->n].vertex=x;//将新顶点输入顶点表
G->adjlist[G->n].firstedge=NULL;//边表置为空表
G->n++；//顶点数加1
}
(2)往图中插入一条边
void AddedgeALGraPh(ALGrahp *G,VertexType x,VertexType y)
{//往无向图的邻接表中插入边(x,y)
int i,j,k;
EdgeNode *s；
i=-1;j=-1;
for(k=0;k<G->n;k++)//查找X，Y的编号
{ if (G->adjlist[k].vertex==x) i=k;
if (G->adjlist[k].vertex==y) j=k;
}
if (i==-1||j==-1) Error("结点不存在");
else {
s=G->adjlist[i].firstedge;
while ((s)&&(s->adjvex!=j)//查看邻接表中有无(x,y)
s=s->next;
if (!s)//当邻接表中无边(x,y),插入边(x,y)
{
s=(EdgeNode *)malloc(sizeof(EdgeNode))； //生成边表结点
s->adjvex=j; //邻接点序号为j
s->next=G->adjlist[i].firstedge；
G->adjlist[i].firstedge=s；//将新结点*s插入顶点x的边表头部
s=(EdgeNode *)malloc(sizeof(EdgeNode))；
s->adjvex=i; //邻接点序号为i
s->next=G->adjlist[j].firstedge；
G->adjlist[j].firstedge=s； //将新结点*s插入顶点x的边表头部
G->e++;//边数加1
}
}
}
(3)删去图中某顶点
void DeleteVertexALGraPh(ALGrahp *G,VertexType x)
{//无向图的邻接表中删除顶点x
int i,k,j;
EdgeNode *s,*p,*q；
i=-1;
for(k=0;k<G->n;k++)//查找X的编号
if (G->adjlist[k].vertex==x) i=k;
if (i==-1) Error("结点不存在");
else {//删除与x相关联的边
s=G->adjlist[i].firstedge;
while (s)
{p=G->adjlist[s->adjvex].firstedge;//删除与i相关联的其他结点边表中表结点
if (p)&&(p->adjvex==i)//是第一个边表结点，修改头指针
{G->adjlist[s->adjvex].firstedge=p->next;
free(p);
}
else//不是第一个 边表结点，查找并删除
{while (p)&&(p->next)&&(p->next->adjvex==i)
p=p->next;
q=p->next;
p->next=q->next;free(q);
}
q=s;s=s->next;free(q);//在i结点的边表中删除表结点
G->e--;
}
//调整顶点表
for (j=i;j<G->n-1;j++)
{G->adjlist[j].firstedge=G->adjlist[j+1].firstedge;
G->adjlist[j].vertex=G->adjlist[j+1].vertex;
}
G->n--;
}
}
(4)删去图中某条边
void DeleteedgeALGraPh(ALGraph *G,VertexType x,VertexType y)
{//往无向图的邻接表中删除边(x,y)
int i,j,k;
EdgeNode *s,*p；
i=-1;j=-1;
for(k=0;k<G->n;k++)//查找X，Y的编号
{ if (G->adjlist[k].vertex==x) i=k;
if (G->adjlist[k].vertex==y) j=k;
}
if (i==-1||j==-1) Error("结点不存在");
else {
s=G->adjlist[i].firstedge;//在i的边表中删除值为j的边表结点
if (s)&&(s->adjvex==j)
{G->adjlist[i].firstedge=s->next;
free(s);
}
else{
while (s)&&(s->next)&&(s->next->adjvex!=j)
s=s->next;
if (!s->next) Error("无此边");
else
{p=s->next;s=p->next;free(p);
}
}
s=G->adjlist[j].firstedge;//在j的边表中删除值为i的边表结点
if (s)&&(s->adjvex==i)
{G->adjlist[j].firstedge=s->next;
free(s);
}
else{
while (s)&&(s->next)&&(s->next->adjvex!=j)
s=s->next;
p=s->next;s=p->next;free(p);
}
G->e--;
}
}
7.17 下面的伪代码是一个广度优先搜索算法，试以图7.29（下图）中的v0为源点执行该算法，请回答下述问题：
(1)对图中顶点vn+1，它需入队多少次？它被重复访问多少次?
(2)若要避免重复访问同一个顶点的错误，应如何修改此算法?
void BFS(ALGraph *G,int k)
{//以下省略局部变量的说明，visited各分量初值为假
InitQueue(&Q);//置空队列
EnQueue(&Q,k);//k入队
while(!QueueEmpty(&Q)){
i=DeQueue(&Q);//vi出队
visited[i]=TRUE;//置访问标记
printf("%c",G->adjlist[i].vertex;//访问vi
for(p=G->adjlist[i].firstedge;p;p=p->next)
//依次搜索vi的邻接点vj(不妨设p->adjvex=j)
if(!visited[p->adjvex])//若vj没有访问过
EnQueue(&Q,p->adjvex);//vj入队
}//endofwhile
}//BFS
答：
(1)对图中顶点vn+1，它需入队n次,它被重复访问n次。
(2)若要避免重复访问同一个顶点的错误，应作如下修改：
void BFS(ALGraph *G,int k)
{//以下省略局部变量的说明，visited各分量初值为假
InitQueue(&Q);//置空队列
EnQueue(&Q,k);//k入队
visited[i]=TRUE;//置访问标记
printf("%c",G->adjlist[i].vertex;//访问vi
while(!QueueEmpty(&Q)){
i=DeQueue(&Q);//vi出队
for(p=G->adjlist[i].firstedge;p;p=p->next)
//依次搜索并访问vi的未访问邻接点vj(不妨设p->adjvex=j)
if(!visited[p->adjvex])//若vj没有访问过
{printf("%c",G->adjlist[i].vertex;//访问vj
EnQueue(&Q,p->adjvex);//vj入队
}
}//endofwhile
}//BFS
7.18 试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(i<>j)之间是否有路径。
答：
(1)基于采用邻接矩阵的DFS
int pathDFSM(MGraph *G，int i,int j)
{ //以邻接矩阵为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0
int k;
visited[i]=TRUE；
for(k=0；k<G->n；k++) //依次搜索vi的邻接点
if(G->edges[i][k]==1&&!visited[k])
if (k==j) return 1;//有路径相通
else return(pathDFSM(G,k,j);
return 0;//无路径相通
}//DFSM
(2)基于采用邻接表的DFS
int PATHDFS(ALGraph *G，int i,int j){
//以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0
EdgeNode *p；
visited[i]=TRUE； //标记vi已访问
p=G->adjlist[i].firstedge； //取vi边表的头指针
while(p){//依次搜索vi的邻接点vk，这里k=p->adjvex
if （!visited[p->adjvex])//若vk尚未被访问
if (p->adjvex==j)
return 1;
else ruturn PATHDFS(g，p->adjvex,j);//则以Vk为出发点向纵深搜索
p=p->next； //找vi的下一邻接点
}
return 0;
}//PATHDFS
(3)基于邻接矩阵的BFS算法
int pathBFSM(MGraph *G，int i,int j)
{//以邻接矩阵为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0
int k；
CirQueue Q；
initQueue(&Q)；
visited[i]=TRUE；
EnQueue(&Q，i)；
while(!QueueEmpty(&Q)){
i=DeQueue(&Q)； //vi出队
for(k=0;k<G->n;k++)//依次搜索vi的邻接点vk
if(G->edges[i][k]==1&&!visited[k]){//vk未访问
if (k==j) return 1;
visited[k]=TRUE；
EnQueue(&Q，k)；//访问过的vk人队
}
}//endwhile
return 0;
}//pathBFSM
(4)基于邻接表为存储结构的BFS算法
int BFS(ALGraph *G，int i,int j)
{//以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0
int i；
CirQueue Q； //须将队列定义中DataType改为int
EdgeNode *p；
InitQueue(&Q)；//队列初始化
visited[i]=TRUE；
EnQueue(&Q，i)；//vi已访问，将其人队。（实际上是将其序号人队）
while(!QueueEmpty(&Q)){//队非空则执行
i=DeQueue(&Q)； //相当于vi出队
p=G->adjlist[i].firstedge； //取vi的边表头指针
while(p){//依次搜索vi的邻接点vk(令p->adjvex=k)
if(!visited[p->adjvex]) //若vk未访问过
if (p->adjvex==j)
return 1;
else{
visited[P->adjvex]=TRUE；
EnQueue(&Q，p->adjvex)；
}//访问过的vk人队
p=p->next；//找vi的下一邻接点
}//endwhile
}//endwhile
return 0;
}//end of pathBFS
7.19 试分别写出求DFS和BFS生成树(或生成森林)的算法，要求打印出所有的树边。
答：
(1)求DFS生成树
typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
Boolean visited[MaxVertexNum]； //访问标志向量是全局量
void DFSTraverseTREE(ALGraph *G)
{ //求深度优先生成树(以邻接表表示的图G)，而以邻接矩阵表示G时，
//算法完全与此相同,只要将DFSTree(G，i)改为DFSMTree(G，i)即可
int i；
for(i=0;i<G->n;i++)
visited[i]=FALSE； //标志向量初始化
for(i=0;i<G->n；i++)
if(!visited[i]) //vi未访问过
DFSTree(G，i)； //以vi为源点开始DFS搜索,求DFS生成树的边
}//DFSTraverse
void DFSTree(ALGraph *G，int i){
//以vi为出发点对邻接表表示的图G进行深度优先搜索,打印生成树(生成森林)的边
EdgeNode *p；
visited[i]=TRUE； //标记vi已访问
p=G->adjlist[i].firstedge； //取vi边表的头指针
while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex
if (!visited[p->adjvex])//若vj尚未被访问
{printf("(%c,%c)\n",G->adjlist[i].vertex,G->adjlist[p->adjvex].vertex) ；
// 打印边
DFSTree(g，p->adjvex);//则以Vj为出发点向纵深搜索
}
p=p->next； //找vi的下一邻接点
}
}//DFS
void DFSMTree(MGraph *G，int i)
{ //以vi为出发点对邻接矩阵表示的图G进行深度优先搜索,打印生成树(生成森林)的边
int j；
visited[i]=TRUE；
for(j=0；j<G->n；j++) //依次搜索vi的邻接点
if(G->edges[i][j]==1&&!visited[j])
{
printf("(%c,%c)\n",G->vexs[i],G->vexs[j]);// 打印边
DFSMTree(G，j);//(vi，vj)∈E，且vj未访问过，故vj为新出发点
}
}//DFSMTree
(2)求BFS生成树
typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
Boolean visited[MaxVertexNum]； //访问标志向量是全局量
void BFSTraverseTREE(ALGraph *G)
{ //求广度优先生成树(以邻接表表示的图G)，而以邻接矩阵表示G时，
//算法完全与此相同,只要将BFSTree(G，i)改为BFSMTree(G，i)即可
int i；
for(i=0;i<G->n;i++)
visited[i]=FALSE； //标志向量初始化
for(i=0;i<G->n；i++)
if(!visited[i]) //vi未访问过
BFSTree(G，i)； //以vi为源点开始BFS搜索,求BFS生成树的边
}//BFSTraverse
void BFSTree(ALGraph*G，int k)
{// 以vk为源点对用邻接表表示的图G进行广度优先搜索,并求出BFS生成树边
int i；
CirQueue Q； //须将队列定义中DataType改为int
EdgeNode *p；
InitQueue(&Q)；//队列初始化
visited[k]=TRUE；
EnQueue(&Q，k)；//vk已访问，将其人队。（实际上是将其序号人队）
while(!QueueEmpty(&Q)){//队非空则执行
i=DeQueue(&Q)； //相当于vi出队
p=G->adjlist[i].firstedge； //取vi的边表头指针
while(p){//依次搜索vi的邻接点vj(令p->adjvex=j)
if(!visited[p->adivex]){ //若vj未访问过
printf("(%c,%c)\n"，G->adjlist[i].vertex,G->adjlist[p->adjvex].vertex)；
//打印边
visited[P->adjvex]=TRUE；
EnQueue(&Q，p->adjvex)；／／访问过的vj人队
}//endif
p=p->next；//找vi的下一邻接点
}//endwhile
}//endwhile
}//end of BFSTree
void BFSMTree(MGraph *G，int k)
{// 以vk为源点对用邻接矩阵表示的图G进行广度优先搜索,并求出BFS生成树边
int i，j；
CirQueue Q；
InitQueue(&Q)；
visited[k]=TRUE；
EnQueue(&Q，k)；
while(!QueueEmpty(&Q)){
i=DeQueue(&Q)； //vi出队
for(j=0;j<G->n;j++)//依次搜索vi的邻接点vj
if(G->edges[i][j]==1&&!visited[j]){//vi未访问
printf("(%c,%c)\n"，G->vexs[i],G->vexs[j])；//打印边
visited[j]=TRUE；
EnQueue(&Q，j)；//访问过的vj人队
}
}//endwhile
}//BFSMTree
7.20 写一算法求连通分量的个数并输出各连通分量的顶点集。
答：
typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
Boolean visited[MaxVertexNum]； //访问标志向量是全局量
void DFSTraverse(ALGraph *G)
{ //深度优先遍历以邻接表表示的图G，求连通分量的个数和各连通分量的顶点集
int i；
for(i=0;i<G->n;i++)
visited[i]=FALSE； //标志向量初始化
j=0;//连通分量个数计数器
for(i=0;i<G->n；i++)
if(!visited[i]) //vi未访问过
{j++;
printf("connected component %d:{",j);
DFS(G，i)； //以vi为源点开始DFS搜索
printf("}\n");
}
}//DFSTraverse
void DFS(ALGraph *G，int i){
//以vi为出发点对邻接表表示的图G进行深度优先搜索
EdgeNode *p；
printf("％c,"，G->adjlist[i].vertex)；//访问顶点vi
visited[i]=TRUE； //标记vi已访问
p=G->adjlist[i].firstedge； //取vi边表的头指针
while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex
if （!visited[p->adjvex])//若vi尚未被访问
DFS(g，p->adjvex);//则以Vj为出发点向纵深搜索
p=p->next； //找vi的下一邻接点
}
}//DFS
7.21 设图中各边的权值都相等，试以邻接矩阵和邻接表为存储结构，分别写出算法：
(1)求顶点vi到顶点vj(i<>j)的最短路径
(2)求源点vi到其余各顶点的最短路径
要求输出路径上的所有顶点(提示：利用BFS遍历的思想)
答：
(1)求顶点vi到顶点vj(i<>j)的最短路径
int shortestpath(ALGraph*G，int i,int j)
{// 对邻接表表示的图G，求顶点vi到顶点vj(i<>j)的最短路径
int dist[MaxVertexNum];
CirQueue Q； //须将队列定义中DataType改为int
EdgeNode *p；
int k；
for(k=0;k<G->n;k++)
dist[k]=0； //距离向量初始化
InitQueue(&Q)；//队列初始化
visited[i]=TRUE；
EnQueue(&Q，i)；
while(!QueueEmpty(&Q)){//队非空则执行
i=DeQueue(&Q)； //相当于vi出队
p=G->adjlist[i].firstedge； //取vi的边表头指针
while(p){//依次搜索vi的邻接点vk(令p->adjvex=k)
if(!visited[p->adjvex]){ //若vj未访问过
dist[p->adjvex]++;
if (p->adjvex==j) return dist[p->adjvex];
visited[P->adjvex]=TRUE；
EnQueue(&Q，p->adjvex)；／／访问过的vk人队
}//endif
p=p->next；//找vi的下一邻接点
}//endwhile
}//endwhile
}//end of shortestpath
int BFSM(MGraph *G，int i,int j)
{// 对邻接链表表示的图G，求顶点vi到顶点vj(i<>j)的最短路径
int dist[MaxVertexNum],k；
CirQueue Q；
initQueue(&Q)；
for(k=0;k<G->n;k++)
dist[i]=0； //距离向量初始化
visited[k]=TRUE；
EnQueue(&Q，i)；
while(!QueueEmpty(&Q)){
i=DeQueue(&Q)； //vi出队
for(k=0;k<G->n;k++)//依次搜索vi的邻接点vk
if(G->edges[i][k]==1&&!visited[k]){//vk未访问
dist[k]++;
if (k==j) return dist[j];
visited[k]=TRUE；
EnQueue(&Q，k)；//访问过的vk人队
}
}//endwhile
}//BFSM
(2)求源点vi到其余各顶点的最短路径
void shortestpath(ALGraph*G，int i)
{// 对邻接表表示的图G，求顶点vi到顶点vj(i<>j)的最短路径
int dist[MaxVertexNum];
int pre[MaxVertexNum];//pre[k]中存放vi到vk路径中，vk的前趋的序号
CirQueue Q； //须将队列定义中DataType改为int
EdgeNode *p；
int k,j；
for(k=0;k<G->n;k++)
{dist[k]=0； //距离向量初始化
pre[k]=k;
}
InitQueue(&Q)；//队列初始化
visited[i]=TRUE；
EnQueue(&Q，i)；
while(!QueueEmpty(&Q)){//队非空则执行
i=DeQueue(&Q)； //相当于vi出队
p=G->adjlist[i].firstedge； //取vi的边表头指针
while(p){//依次搜索vi的邻接点vk(令p->adjvex=k)
if(!visited[p->adjvex]){ //若vj未访问过
dist[p->adjvex]++;
pre[p->adjvex]=i;
visited[P->adjvex]=TRUE；
EnQueue(&Q，p->adjvex)；／／访问过的vk人队
}//endif
p=p->next；//找vi的下一邻接点
}//endwhile
}//endwhile
for(k=0;k<G->n;k++)// 打印各顶点的最短路径和长度
{printf("path of %c is %d:",G->adjlist[k].vertex,dist[k]);
j=k;
printf("%c",G->adjlist[k].vertex);
do
{
j=pre[j];
print("<-%c",G->adjlist[j].vertex);
}
while (j!=i);
printf("\n");
}
}//end of shortestpath
void shortestpathBFSM(MGraph *G，int i)
{// 对邻接矩阵表示的图G，求顶点vi到其他顶点的最短路径
int dist[MaxVertexNum],k,j;
int pre[MaxVertexNum];//pre[k]中存放vi到vk路径中，vk的前趋的序号
CirQueue Q；
initQueue(&Q)；
for(k=0;k<G->n;k++)
{dist[k]=0； //距离向量初始化
pre[k]=k;
}
visited[k]=TRUE；
EnQueue(&Q，i)；
while(!QueueEmpty(&Q)){
i=DeQueue(&Q)； //vi出队
for(k=0;k<G->n;k++)//依次搜索vi的邻接点vk
if(G->edges[i][k]==1&&!visited[k]){//vk未访问
dist[k]++;
pre[k]=i;
visited[k]=TRUE；
EnQueue(&Q，k)；//访问过的vk人队
}
}//endwhile
for(k=0;k<G->n;k++)// 打印各顶点的最短路径和长度
{printf("path of %c is %d:",G->vertex[k],dist[k]);
j=k;
printf("%c",G->vertex[k]);
do
{
j=pre[j];
printf("<-%c",G->vertex[j]);
}
while (j!=i);
printf("\n");
}
}//shortestpathBFSM
7.22 以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路(若存在)。
答：
int circleDFS(ALGraph *G，int k){
//以vk为出发点对邻接表表示的图G,求简单回路,若存在返回1，否则返回0
EdgeNode *p；
printf("％c"，G->adjlist[k].vertex)；//访问顶点vk
visited[k]=TRUE； //标记vk已访问
p=G->adjlist[k].firstedge； //取vk边表的头指针
while(p){//依次搜索vk的邻接点vj，这里j=p->adjvex
if (!visited[p->adjvex])//若vj尚未被访问
DFS(G，p->adjvex);//则以Vj为出发点向纵深搜索
else if (p->adjvex==k)
{printf("%c",G->adjlist[k].vertex)；return 1;}
p=p->next； //找vk的下一邻接点
}
return 0;
}//DFS
7.23 写一算法求有向图的所有根(若存在)，分析算法的时间复杂度。
答：
typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
Boolean visited[MaxVertexNum]； //访问标志向量是全局量
void DFSTraverse(ALGraph *G)
{ //对以邻接表表示的有向图G，求所有根(以邻接矩阵表示G时，算法完全与此相同)
int i,j；
for (j=0;j<G->n;j++)
{
for(i=0;i<G->n;i++)
visited[i]=FALSE； //标志向量初始化
DFS(G，j)； //以vj为源点开始DFS搜索，也可用BFS(G,j)
i=0;
while(i<G->n)&&(visited[i]==TRUE)
i++;
if (i==G->n) printf("root:%c",G->adjlist[j].vertex);
}
}//DFSTraverse
该算法的为二重循环，若调用的DFS算法的复杂度为O(n+e),所以该算法的时间复杂度为O(n(n+e))
若调用的DFSM算法的复杂度为O(n*n),所以该算法的时间复杂度为O(n^3)
7.24 改写7.5节的算法Print，使输出的从源点到各终点的最短路径是正向的。(提示：使用栈暂存路径)
答：
void print(path p,distance d)
{//输出最短路径及其长度，从源点到各终点的最短路径是正向的
int i,pre;
SeqStack S; //定义一个栈
InitStack (&s);
for(i=0;i<n;i++){//依次打印各顶点i的最短路径及其长度
printf("\n distance:%d,path:",d[i]);//输出终点i的最短距离
Push(&S, i);//终点i入栈
pre=p[i];//找终点i的前趋
while (pre!=-1)
{push(&s,pre);
pre=p[pre];//继续找前趋
}//endwhile
printf("%d",pop(&s));
while (!StackEmpty(S))
printf(",%d",pop(&s));
}//endfor
}//endprint
7.25 对7.6节的NonSuccFirstTopSort算法求精，分别以邻接矩阵和邻接表作为存储结构，写出其具体算法，并分析算法的时间。
答：
(1)以邻接矩阵作为存储结构
void NonSuccFirstTopSort(MGraph G){//优先输出无后继的顶点
int outdegree[MaxVertexNum];//出度向量，此处MaxVertexNum>=G.n
SeqStack S,T;//将栈中data向量的基类型改为int
int i,j,count=0;//count对输出的顶点数目计数，初值为0
for(i=0;i<G.n;i++)
outdegree[i]=0;
for(i=0;i<G.n;i++)
for(j=0;j<G.n;j++)
outdegree[i]=outdegree[i]+g.edge[i][j];
InitStack(&s);
for(i=0;i<G.n;i++)
if (outdegree[i]==0)
Push(&S, i);//出度为0的顶点i入栈
InitStack(&T);
while(!StackEmpty(S))//栈非空，有出度为0的顶点
{i=pop(&s);
Push(&T, i);
count++;//顶点计数加1
for (j=0;j<G.n;j++)//修改以i为弧头的弧的弧尾顶点的出度
if (G.edge[j][i]==1)
{G.edge[j][i]=0;
outdegree[j]--;
if (outdegree[j]==0)//将新生成的出度为0的顶点入栈
Push(&S, j);//出度为0的顶点j入栈
}//end of if
}//end of while
if (count<G.n)
printf("G中存在有向环，排序失败!");
else{//输出拓扑序列
while (!StackEmpty(T))
printf("%c",G.vertex[pop(&T)]);
}
}
(2)以邻接表作为存储结构
void NonSuccFirstTopSort(ALGraph G){
//优先输出无后继的顶点,此处用逆邻接表存储
int outdegree[MaxVertexNum];//出度向量，此处MaxVertexNum>=G.n
SeqStack S,T;//将栈中data向量的基类型改为int
int i,j,count=0;//count对输出的顶点数目计数，初值为0
EdgeNode *p;
for(i=0;i<G.n;i++)
outdegree[i]=0;
for(i=0;i<G.n;i++)
for(p=G.adjlist[i].firstedge;p;p=p->next)//扫描i的入边表
outdegree[p->adjvex]++;//设p->adjvex=j，则将<j,i>的起点j出度加1
InitStack(&s);
for(i=0;i<G.n;i++)
if (outdegree[i]==0)
Push(&S, i);//出度为0的顶点i入栈
InitStack(&T);
while(!StackEmpty(S))//栈非空，有出度为0的顶点
{i=pop(&s);
Push(&T, i);
count++;//顶点计数加1
for(p=G.adjlist[i].firstedge;p;p=p->next)
//修改以i为弧头的弧的弧尾顶点的出度
{
j=p->adjvex;
outdegree[j]--;
if (outdegree[j]==0)//将新生成的出度为0的顶点入栈
Push(&S, j);//出度为0的顶点j入栈
}//end of for
}//end of while
if (count<G.n)//输出顶点数小于n
printf("G中存在有向环，排序失败!");
else{//输出拓扑序列
while (!StackEmpty(T))
printf("%c",G.adjlist[pop(&T)].vertex);
}
}
7.26 设一个有向图DAG，试以邻接矩阵和邻接表作为存储结构，写出对7.6节的DFSTopSort求精算法。为什么有向图不是DAG时，该算法不能正常工作?
答：
(1)以邻接矩阵作为存储结构
void DFSTopSort(MGraph G,int i,SeqStack T){
EdgeNode *p;
visited[i]=TRUE;
for(j=0;j<G.n;j++)
if (G.edge[i][j]==1)&&(!visited[j])
FFSTopSort(G,j,T);
push(&T,i);
}
(2)以邻接表作为存储结构
void DFSTopSort(ALGraph G,int i,SeqStack T){
int j;
visited[i]=TRUE;
for(p=G.adjlist[i].firstedge;p;p=p->next)
if (!visited[p->adjvex])//若vj尚未被访问
DFSTopSort(G，p->adjvex,T);
push(&T,i);
}
当有向图不是DAG图时，该算法不能检测出回路，仍然能给出包含所有顶点的序列，所以该算法不能正常工作。
7.27 利用拓扑排序算法的思想写一算法判别有向图中是否存在有向环，当有向环存在时，输出构成环的顶点。
答：
typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
Boolean visited[MaxVertexNum]； //访问标志向量是全局量
int i；
for(i=0;i<G->n;i++)
visited[i]=FALSE； //标志向量初始化
以邻接表作为存储结构
void NonSuccFirstTopSort(ALGraph G){
//优先输出无后继的顶点,此处用逆邻接表存储
int outdegree[MaxVertexNum];//出度向量，此处MaxVertexNum>=G.n
SeqStack S;//将栈中data向量的基类型改为int
int i,j,count=0;//count对输出的顶点数目计数，初值为0
EdgeNode *p;
for(i=0;i<G.n;i++)
{ outdegree[i]=0;
visited[i]=FALSE； //标志向量初始化
}
for(i=0;i<G.n;i++)
for(p=G.adjlist[i].firstedge;p;p=p->next)//扫描i的入边表
outdegree[p->adjvex]++;//设p->adjvex=j，则将<j,i>的起点j出度加1
InitStack(&s);
for(i=0;i<G.n;i++)
if (outdegree[i]==0)
Push(&S, i);//出度为0的顶点i入栈
while(!StackEmpty(S))//栈非空，有出度为0的顶点
{i=pop(&s);visited[i]=TRUE;
count++;//顶点计数加1
for(p=G.adjlist[i].firstedge;p;p=p->next)
//修改以i为弧头的弧的弧尾顶点的出度
{
j=p->adjvex;
outdegree[j]--;
if (outdegree[j]==0)//将新生成的出度为0的顶点入栈
Push(&S, j);//出度为0的顶点j入栈
}//end of for
}//end of while
if (count<G.n)//输出顶点数小于n
{printf("G中存在有向环，排序失败!");
for(i=0;i<G.n;i++)
if (visited[i]==FALSE)
printf("%c",G.adjlist[i].vertex);
}
else printf("G中无有向环!");
}