数据结构 第七章 图.docx
《数据结构 第七章 图.docx》由会员分享，可在线阅读，更多相关《数据结构 第七章 图.docx（26页珍藏版）》请在冰点文库上搜索。
数据结构第七章图
7.14
StatusBuild_AdjList（ALGraph&G）//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表
{
InitALGraph（G）;
scanf（"%d",&v）;
if（v<0）returnERROR;//顶点数不能为负
G.vexnum=v;
scanf（"%d",&a）;
if（a<0）returnERROR;//边数不能为负
G.arcnum=a;
for（m=0;m G.vertices[m].data=getchar（）;//输入各顶点的符号
for（m=1;m<=a;m++）
{
t=getchar（）;h=getchar（）;//t为弧尾,h为弧头
if（（i=LocateVex（G,t））<0）returnERROR;
if（（j=LocateVex（G,h））<0）returnERROR;//顶点未找到
p=（ArcNode*）malloc（sizeof（ArcNode））;
if（!
G.vertices.[i].firstarc）G.vertices[i].firstarc=p;
else
{
for（q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc）;
q->nextarc=p;
}
p->adjvex=j;p->nextarc=NULL;
}//while
returnOK;
}//Build_AdjList
7.15
//本题中的图G均为有向无权图,其余情况容易由此写出
StatusInsert_Vex（MGraph&G,charv）//在邻接矩阵表示的图G上插入顶点v
{
if（G.vexnum+1）>MAX_VERTEX_NUMreturnINFEASIBLE;
G.vexs[++G.vexnum]=v;
returnOK;
}//Insert_Vex
StatusInsert_Arc（MGraph&G,charv,charw）//在邻接矩阵表示的图G上插入边（v,w）
{
if（（i=LocateVex（G,v））<0）returnERROR;
if（（j=LocateVex（G,w））<0）returnERROR;
if（i==j）returnERROR;
if（!
G.arcs[i][j].adj）
{
G.arcs[i][j].adj=1;
G.arcnum++;
}
returnOK;
}//Insert_Arc
StatusDelete_Vex（MGraph&G,charv）//在邻接矩阵表示的图G上删除顶点v
{
n=G.vexnum;
if（（m=LocateVex（G,v））<0）returnERROR;
G.vexs[m]<->G.vexs[n];//将待删除顶点交换到最后一个顶点
for（i=0;i {
G.arcs[i][m]=G.arcs[i][n];
G.arcs[m][i]=G.arcs[n][i];//将边的关系随之交换
}
G.arcs[m][m].adj=0;
G.vexnum--;
returnOK;
}//Delete_Vex
分析:
如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加.
StatusDelete_Arc（MGraph&G,charv,charw）//在邻接矩阵表示的图G上删除边（v,w）
{
if（（i=LocateVex（G,v））<0）returnERROR;
if（（j=LocateVex（G,w））<0）returnERROR;
if（G.arcs[i][j].adj）
{
G.arcs[i][j].adj=0;
G.arcnum--;
}
returnOK;
}//Delete_Arc
7.16
//为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出.
StatusInsert_Arc（ALGraph&G,charv,charw）//在邻接表表示的图G上插入边（v,w）
{
if（（i=LocateVex（G,v））<0）returnERROR;
if（（j=LocateVex（G,w））<0）returnERROR;
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=j;p->nextarc=NULL;
if（!
G.vertices[i].firstarc）G.vertices[i].firstarc=p;
else
{
for（q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc）
if（q->adjvex==j）returnERROR;//边已经存在
q->nextarc=p;
}
G.arcnum++;
returnOK;
}//Insert_Arc
7.17
//为节省篇幅,本题只给出较为复杂的Delete_Vex算法.其余算法请自行写出.
StatusDelete_Vex（OLGraph&G,charv）//在十字链表表示的图G上删除顶点v
{
if（（m=LocateVex（G,v））<0）returnERROR;
n=G.vexnum;
for（i=0;i {
if（G.xlist[i].firstin->tailvex==m）//如果待删除的边是头链上的第一个结点
{
q=G.xlist[i].firstin;
G.xlist[i].firstin=q->hlink;
free（q）;G.arcnum--;
}
else//否则
{
for（p=G.xlist[i].firstin;p&&p->hlink->tailvex!
=m;p=p->hlink）;
if（p）
{
q=p->hlink;
p->hlink=q->hlink;
free（q）;G.arcnum--;
}
}//else
}//for
for（i=0;i {
if（G.xlist[i].firstout->headvex==m）//如果待删除的边是尾链上的第一个结点
{
q=G.xlist[i].firstout;
G.xlist[i].firstout=q->tlink;
free（q）;G.arcnum--;
}
else//否则
{
for（p=G.xlist[i].firstout;p&&p->tlink->headvex!
=m;p=p->tlink）;
if（p）
{
q=p->tlink;
p->tlink=q->tlink;
free（q）;G.arcnum--;
}
}//else
}//for
for（i=m;i {
G.xlist[i]=G.xlist[i+1];//修改表头向量
for（p=G.xlist[i].firstin;p;p=p->hlink）
p->headvex--;
for（p=G.xlist[i].firstout;p;p=p->tlink）
p->tailvex--;//修改各链中的顶点序号
}
G.vexnum--;
returnOK;
}//Delete_Vex
7.18
//为节省篇幅,本题只给出Delete_Arc算法.其余算法请自行写出.
StatusDelete_Arc（AMLGraph&G,charv,charw）////在邻接多重表表示的图G上删除边（v,w）
{
if（（i=LocateVex（G,v））<0）returnERROR;
if（（j=LocateVex（G,w））<0）returnERROR;
if（G.adjmulist[i].firstedge->jvex==j）
G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink;
else
{
for（p=G.adjmulist[i].firstedge;p&&p->ilink->jvex!
=j;p=p->ilink）;
if（!
p）returnERROR;//未找到
p->ilink=p->ilink->ilink;
}//在i链表中删除该边
if（G.adjmulist[j].firstedge->ivex==i）
G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink;
else
{
for（p=G.adjmulist[j].firstedge;p&&p->jlink->ivex!
=i;p=p->jlink）;
if（!
p）returnERROR;//未找到
q=p->jlink;
p->jlink=q->jlink;
free（q）;
}//在i链表中删除该边
G.arcnum--;
returnOK;
}//Delete_Arc
7.19
StatusBuild_AdjMulist（AMLGraph&G）//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表
{
InitAMLGraph（G）;
scanf（"%d",&v）;
if（v<0）returnERROR;//顶点数不能为负
G.vexnum=v;
scanf（%d",&a）;
if（a<0）returnERROR;//边数不能为负
G.arcnum=a;
for（m=0;m G.adjmulist[m].data=getchar（）;//输入各顶点的符号
for（m=1;m<=a;m++）
{
t=getchar（）;h=getchar（）;//t为弧尾,h为弧头
if（（i=LocateVex（G,t））<0）returnERROR;
if（（j=LocateVex（G,h））<0）returnERROR;//顶点未找到
p=（EBox*）malloc（sizeof（EBox））;
p->ivex=i;p->jvex=j;
p->ilink=NULL;p->jlink=NULL;//边结点赋初值
if（!
G.adjmulist[i].firstedge）G.adjmulist[i].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while（q）
{
r=q;
if（q->ivex==i）q=q->ilink;
elseq=q->jlink;
}
if（r->ivex==i）r->ilink=p;//注意i值既可能出现在边结点的ivex域中,
elser->jlink=p;//又可能出现在边结点的jvex域中
}//else//插入i链表尾部
if（!
G.adjmulist[j].firstedge）G.adjmulist[j].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while（q）
{
r=q;
if（q->jvex==j）q=q->jlink;
elseq=q->ilnk;
}
if（r->jvex==j）r->jlink=p;
elser->ilink=p;
}//else//插入j链表尾部
}//for
returnOK;
}//Build_AdjList
7.20
intPass_MGraph（MGraphG）//判断一个邻接矩阵存储的有向图是不是可传递的,是则返回1,否则返回0
{
for（x=0;x for（y=0;y if（G.arcs[x][y]）
{
for（z=0;z if（z!
=x&&G.arcs[y][z]&&!
G.arcs[x][z]）return0;//图不可传递的条件
}//if
return1;
}//Pass_MGraph
分析:
本算法的时间复杂度大概是O（n^2*d）.
7.21
intPass_ALGraph（ALGraphG）//判断一个邻接表存储的有向图是不是可传递的,是则返回1,否则返回0
{
for（x=0;x for（p=G.vertices[x].firstarc;p;p=p->nextarc）
{
y=p->adjvex;
for（q=G.vertices[y].firstarc;q;q=q->nextarc）
{
z=q->adjvex;
if（z!
=x&&!
is_adj（G,x,z））return0;
}//for
}//for
}//Pass_ALGraph
intis_adj（ALGraphG,intm,intn）//判断有向图G中是否存在边（m,n）,是则返回1,否则返回0
{
for（p=G.vertices[m].firstarc;p;p=p->nextarc）
if（p->adjvex==n）return1;
return0;
}//is_adj
7.22
intvisited[MAXSIZE];//指示顶点是否在当前路径上
intexist_path_DFS（ALGraphG,inti,intj）//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
if（i==j）return1;//i就是j
else
{
visited[i]=1;
for（p=G.vertices[i].firstarc;p;p=p->nextarc）
{
k=p->adjvex;
if（!
visited[k]&&exist_path（k,j））return1;//i下游的顶点到j有路径
}//for
}//else
}//exist_path_DFS
7.23
intexist_path_BFS（ALGraphG,inti,intj）//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
intvisited[MAXSIZE];
InitQueue（Q）;
EnQueue（Q,i）;
while（!
QueueEmpty（Q））
{
DeQueue（Q,u）;
visited[u]=1;
for（p=G.vertices[i].firstarc;p;p=p->nextarc）
{
k=p->adjvex;
if（k==j）return1;
if（!
visited[k]）EnQueue（Q,k）;
}//for
}//while
return0;
}//exist_path_BFS
7.24
voidSTraverse_Nonrecursive（GraphG）//非递归遍历强连通图G
{
intvisited[MAXSIZE];
InitStack（S）;
Push（S,GetVex（S,1））;//将第一个顶点入栈
visit
（1）;
visited_=1;
while（!
StackEmpty（S））
{
while（Gettop（S,i）&&i）
{
j=FirstAdjVex（G,i）;
if（j&&!
visited[j]）
{
visit（j）;
visited[j]=1;
Push（S,j）;//向左走到尽头
}
}//while
if（!
StackEmpty（S））
{
Pop（S,j）;
Gettop（S,i）;
k=NextAdjVex（G,i,j）;//向右走一步
if（k&&!
visited[k]）
{
visit（k）;
visited[k]=1;
Push（S,k）;
}
}//if
}//while
}//Straverse_Nonrecursive
分析:
本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.
7.25
见书后解答.
7.26
StatusTopoNo（ALGraphG）//按照题目要求顺序重排有向图中的顶点
{
intnew[MAXSIZE],indegree[MAXSIZE];//储存结点的新序号
n=G.vexnum;
FindInDegree（G,indegree）;
InitStack（S）;
for（i=1;i if（!
indegree[i]）Push（S,i）;//零入度结点入栈
count=0;
while（!
StackEmpty（S））
{
Pop（S,i）;
new[i]=n--;//记录结点的拓扑逆序序号
count++;
for（p=G.vertices[i].firstarc;p;p=p->nextarc）
{
k=p->adjvex;
if（!
（--indegree[k]））Push（S,k）;
}//for
}//while
if（count for（i=1;i<=n;i++）printf（"OldNo:
%dNewNo:
%d\n",i,new[i]）
returnOK;
}//TopoNo
分析:
只要按拓扑逆序对顶点编号,就可以使邻接矩阵成为下三角矩阵.
7.27
intvisited[MAXSIZE];
intexist_path_len（ALGraphG,inti,intj,intk）//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径
{
if（i==j&&k==0）return1;//找到了一条路径,且长度符合要求
elseif（k>0）
{
visited[i]=1;
for（p=G.vertices[i].firstarc;p;p=p->nextarc）
{
l=p->adjvex;
if（!
visited[l]）
if（exist_path_len（G,l,j,k-1））return1;//剩余路径长度减一
}//for
visited[i]=0;//本题允许曾经被访问过的结点出现在另一条路径中
}//else
return0;//没找到
}//exist_path_len
7.28
intpath[MAXSIZE],visited[MAXSIZE];//暂存遍历过程中的路径
intFind_All_Path（ALGraphG,intu,intv,intk）//求有向图G中顶点u到v之间的所有简单路径,k表示当前路径长度
{
path[k]=u;//加入当前路径中
visited[u]=1;
if（u==v）//找到了一条简单路径
{
printf（"Foundonepath!
\n"）;
for（i=0;path[i];i++）printf（"%d",path[i]）;//打印输出
}
else
for（p=G.vertices[u].firstarc;p;p=p->nextarc）
{
l=p->adjvex;
if（!
visited[l]）Find_All_Path（G,l,v,k+1）;//继续寻找
}
visited[u]=0;
path[k]=0;//回溯
}//Find_All_Path
main（）
{
...
Find_All_Path（G,u,v,0）;//在主函数中初次调用,k值应为0
...
}//main
7.29
intGetPathNum_Len（ALGraphG,inti,intj,intlen）//求邻接表方式存储的有向图G的顶点i到j之间长度为len的简单路径条数
{
if（i==j&&len==0）return1;//找到了一条路径,且
升级会员 