图的基本操作算法汇总B5.docx
- 文档编号:11016301
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:53
- 大小:34.37KB
图的基本操作算法汇总B5.docx
《图的基本操作算法汇总B5.docx》由会员分享,可在线阅读,更多相关《图的基本操作算法汇总B5.docx(53页珍藏版)》请在冰点文库上搜索。
图的基本操作算法汇总B5
//图的基本操作算法
//1.
voidCreatGraph(AdjListg)//建立有n个顶点和m条边的无向图的邻接表存储结构
{
intn,m;
scanf("%d%d",&n,&m);
for(i=1,i<=n;i++)//输入顶点信息,建立顶点向量
{
scanf(&g[i].vertex);
g[i].firstarc=null;
}
for(k=1;k<=m;k++)//输入边信息
{
scanf(&v1,&v2);//输入两个顶点
i=GraphLocateVertex(g,v1);
j=GraphLocateVertex(g,v2);//顶点定位
p=(ArcNode*)malloc(sizeof(ArcNode));//申请边结点
p->adjvex=j;
p->next=g[i].firstarc;
g[i].firstarc=p;//将边结点链入
p=(ArcNode*)malloc(sizeof(ArcNode));//无向图双向连接
p->adjvex=i;
p->next=g[j].firstarc;
g[j].firstarc=p;
}
}//算法CreatGraph结束
//2.
voidCreatAdjList(AdjListg)//建立有向图的邻接表存储结构
{
intn;
scanf("%d",&n);
for(i=1;i<=n;j++)
{
scanf(&g[i].vertex);
g[i].firstarc=null;
}//输入顶点信息
scanf(&v1,&v2);
while(v1&&v2)//题目要求两顶点之一为0表示结束
{
i=GraphLocateVertex(g2,v1);
p=(ArcNode*)malloc(sizeof(ArcNode));//有向图只需要单边
p->adjvex=j;
p->next=g[i].firstarc;
g[i].firstarc=p;
scanf(&v1,&v2);
}
}
//5.
voidInvertAdjList(AdjListgin,gout)//将有向图的出度邻接表改为按入度建立的逆邻接表
{
for(i=1;i<=n;i++)//设有向图有n个顶点,建逆邻接表的顶点向量。
{
gin[i].vertex=gout[i].vertex;
gin.firstarc=null;
}//逆邻接表顶点初始化
for(i=1;i<=n;i++)//邻接表转为逆邻接表
{
p=gout[i].firstarc;//取指向邻接表的指针邻接表头结点i的第一条边
while(p!
=null)
{
j=p->adjvex;//邻接表边结点中的j顶点信息
s=(ArcNode*)malloc(sizeof(ArcNode));//申请逆邻接表的边结点空间
s->adjvex=i;//对逆邻接表的
s->next=gin[j].firstarc;//对逆邻接表的
gin[j].firstarc=s;//
p=p->next;//邻接表中找下一个邻接点。
}//while
}//for
}
//6.
voidAdjListToAdjMatrix(AdjListgl,AdjMatrixgm)//将图的邻接表表示转换为邻接矩阵表示
{
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][p->adjvex]=1;
p=p->next;
}//下一个邻接点
}//for
}//算法结束
//7.
voidAdjMatrixToAdjList(AdjMatrixgm,AdjListgl)//图的邻接矩阵表示法转换为邻接表表示法
{
for(i=1;i<=n;i++)//邻接表表头向量初始化。
{
scanf(&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));//申请结点空间。
p->adjvex=j;//顶点i的邻接点是j
p->next=gl[i].firstarc;//下一个邻接边结点
gl[i].firstarc=p;//链入顶点i的邻接点链表中
}
}//end
//[算法讨论]算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。
//9.
voidDeletEdge(AdjListg,inti,j)
//在用邻接表方式存储的无向图g中,删除边(i,j)
{
p=g[i].firstarc;
pre=null;//删顶点i的边结点(i,j),pre是前驱指针
while(p)
if(p->adjvex==j)//找到了要删除的结点
{
if(pre==null)
g[i].firstarc=p->next;//要删除的是第一个邻接点,重新设置第一邻接点
else
pre->next=p->next;//要删除的不是第一邻接点重新设置pre后链跳过p链上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。
//10.
voidDeleteArc(AdjListg,vertypevi,vj)
//删除以邻接表存储的有向图g的一条弧
{
i=GraphLocateVertex(g,vi);
j=GraphLocateVertex(g,vj);//顶点定位
p=g[i].firstarc;
pre=null;
while(p)
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;
}
}//结束不用再查找j比无向图省事
//★★图的遍历算法★★
//12.在有向图的邻接表中,求顶点的出度容易,只要简单在该顶点的邻接点链表中查结点个数即可。
//而求顶点的入度,则要遍历整个邻接表。
intcount(AdjListg,intk)
//在n个顶点以邻接表表示的有向图g中,求指定顶点k(1<=k<=n)的入度。
{
intcount=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的入度.
}
//8.在有向图中,判断顶点Vi和顶点Vj间是否有路径,可采用遍历的方法,从顶点Vi出发,
//不论是深度优先遍历(dfs)还是宽度优先遍历(bfs),在未退出dfs或bfs前,若访问到Vj,
//则说明有通路,否则无通路。
设一全程变量flag,初始化为0,若有通路,则flag=1。
//算法1:
intvisited[]=0;//全局变量,访问数组初始化
intdfs(AdjListg,vertypevi,vj)
//以邻接表为存储结构的有向图g,判断顶点Vi到Vj是否有通路,返回1或0表示有或无
{
visited[vi]=1;//visited是访问数组,假设顶点的信息就是顶点编号。
p=g[vi].firstarc;//第一个邻接点。
while(p!
=null)
{
j=p->adjvex;
if(j==vj)
{
flag=1;
return
(1);
}//vi和vj有通路。
if(visited[j]==0)
dfs(g,j,vj);//递归进行深度遍历
p=p->next;//遍历完返回,继续下一边
}//while
if(!
flag)
return(0);//最后没有通路返回0
}//结束
//[算法讨论]若顶点vi和vj不是编号,必须先用顶点定位函数,查出其在邻接表顶点向量中的下标i和j。
//下面算法2输出vi到vj的路径,其思想是用一个栈存放遍历的顶点,遇到顶点vj时输出路径。
//算法2:
voiddfs(AdjListg,inti,j)
//有向图g的顶点vi(编号i)和顶点vj(编号j)间是否有路径,如有,则输出。
{
inttop=0,stack[];//stack是存放顶点编号的栈
visited[i]=1;//visited数组在进入dfs前已初始化。
stack[++top]=i;
p=g[i].firstarc;//求第一个邻接弧结点.
while(p)
{
if(p->adjvex==j)//弧p的顶点即为j,遇到顶点vj输出路径
{
stack[++top]=j;//顶点j入栈
printf("顶点vi和vj的路径为:
\n");
for(i=1;i<=top;i++)
printf("%4d",stack[i]);
exit(0);
}//if
else
if(visited[p->adjvex]==0)//弧p的顶点p->adjvex尚未被访问
{
dfs(g,p->adjvex,j);
top--;
p=p->next;
}//递归进行深度遍历出栈
}//while
}//结束算法2
//算法3:
本题用非递归算法求解。
intConnectij(AdjListg,vertypevi,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);
intstack[],top=0;
stack[++top]=i;
while(top>0)
{
k=stack[top--];
p=g[k].firstarc;
while(p!
=null&&visited[p->adjvex]==1)
p=p->next;//查第k个链表中第一个未访问的弧结点。
if(p==null)
top--;
else
{
i=p->adjvex;
if(i==j)
return
(1);//顶点vi和vj间有路径。
else
{
visited[i]=1;
stack[++top]=i;
}//else
}//else
}//while
return(0);
}//顶点vi和vj间无通路。
//13.有向图判断回路要比无向图复杂。
利用深度优先遍历,将顶点分成三类:
未访问;
//已访问但其邻接点未访问完;已访问且其邻接点已访问完。
下面用0,1,2表示这三种状态。
//前面已提到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v和u的回路。
//对应程序中v的状态为1,而u是正访问的顶点,若我们找出u的下一邻接点的状态为1,就可以输出回路了。
voidPrint(intv,intstart)//输出从顶点start开始的回路。
{
for(i=1;i<=n;i++)
if(g[v][i]!
=0&&visited[i]==1)//若存在边(v,i),且顶点i的状态为1。
{
printf("%d",v);
if(i==start)
printf("\n");
else
Print(i,start);//递归
break;
}
voiddfs(intv)
{
visited[v]=1;//0:
未访问;1:
已访问但其邻接点未访问完;2:
已访问且其邻接点已访问完
for(j=1;j<=n;j++)
if(g[v][j]!
=0)//存在边(v,j)
if(visited[j]!
=1)//0:
未访问或2:
已访问且其邻接点已访问完
{
if(!
visited[j])
dfs(j);
}//0:
未访问j未访问深度遍历j
else
{
cycle=1;
Print(j,j);
}//1:
已访问且其邻接点未访问完
visited[v]=2;//访问v完成2:
已访问且其邻接点已访问完
}//dfs
voidfind_cycle()//判断是否有回路,有则输出邻接矩阵。
visited数组为全局变量。
{
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(!
visited[i])
dfs(i);
}//find_cycle
//16.本题应使用深度优先遍历,从主调函数进入dfs(v)时,开始记数,若退出dfs()前,
//已访问完有向图的全部顶点(设为n个),则有向图有根,v为根结点。
//将n个顶点从1到n编号,各调用一次dfs()过程,就可以求出全部的根结点。
//题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。
//建立有向图g的邻接表存储结构参见上面第2题,这里只给出判断有向图是否有根的算法。
intnum=0,visited[]=0;//num记访问顶点个数,访问数组visited初始化。
constn=用户定义的顶点数;
AdjListg;//用邻接表作存储结构的有向图g。
voiddfs(v)
{
visited[v]=1;
num++;//访问的顶点数+1
if(num==n)
{
printf("%d是有向图的根。
\n",v);
num=0;
}//重新计数
p=g[v].firstarc;//第一边结点
while(p)
{
if(visied[p->adjvex]==0)
dfs(p->adjvex);//未访问递归深度遍历
p=p->next;
}//while
visited[v]=0;
num--;//恢复顶点v全局变量重新计数便于后边遍历
}//dfs
voidJudgeRoot()//判断有向图是否有根,有根则输出之。
{
staticinti;
for(i=1;i<=n;i++)//从每个顶点出发,调用dfs()各一次。
{
num=0;
visited[1..n]=0;
dfs(i);
}
}//JudgeRoot
//算法中打印根时,输出顶点在邻接表中的序号(下标),若要输出顶点信息,可使用g[i].vertex。
//17.图的遍历可以求出图的连通分量。
进入dfs或bfs一次,就可以访问到图的一个连通分量的所有顶点。
voiddfs()
{
visited[v]=1;
printf("%3d",v);//输出连通分量的顶点。
p=g[v].firstarc;
while(p!
=null)
{
if(visited[p->adjvex]==0)
dfs(p->adjvex);//深度递归访问
p=p->next;
}//while
}//dfs
voidCount()//深度优先遍历求图中连通分量的个数
{
intk=0;
staticAdjListg;//设无向图g有n个结点
for(i=1;i<=n;i++)
if(visited[i]==0)
{
printf("\n第%d个连通分量:
\n",++k);
dfs(i);
}
}//Count
//算法中visited[]数组是全程变量,每个连通分量的顶点集按遍历顺序输出。
//这里设顶点信息就是顶点编号,否则应取其g[i].vertex分量输出。
//18.
voidbfs(AdjListGL,vertypev)//从v发非递归广度优先遍历以邻接表为存储结构的无向图GL。
{
visited[v]=1;
printf("%3d",v);//输出第一个遍历的顶点。
QueueInit(Q);
QueueIn(Q,v);//先置空队列,然后第一个顶点v入队列,设队列容量足够大
while(!
QueueEmpty(Q))
{
v=QueueOut(Q);//v出队列。
p=GL[v].firstarc;//GL是全局变量,第一个邻接边结点
while(p!
=null)
{
if(visited[p->adjvex]==0)//第一个邻接点未访问
{
printf("%3d",p->adjvex);
visited[p->adjvex]=1;
QueueIn(Q,p->adjvex);
}//if//访问入队
p=p->next;//下一个邻接边结点即广度优先
}//while
}//while(!
QueueEmpty(Q))
}//bfs
voidBFSCOM()//广度优先搜索,求无向图G的连通分量。
{
intcount=0;//记连通分量个数。
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(visited[i]==0)
{
printf("\n第%d个连通分量:
\n",++count);
bfs(i);
}//if
}//BFSCOM
//27.D_搜索类似BFS,只是用栈代替队列,入出队列改为入出栈。
//查某顶点的邻接点时,若其邻接点尚未遍历,则遍历之,并将其压入栈中。
//当一个顶点的所有邻接点被搜索后,栈顶顶点是下一个搜索出发点。
voidD_BFS(AdjListg,vertypev0)//从v0顶点开始,对以邻接表为存储结构的图g进行D_搜索。
{
ints[],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("%3d",i);//入栈;访问
while(top>0)
{
i=s[top--];//退栈,准备找邻接点
p=g[i].firstarc;//取第一个邻接边结点
while(p!
=null)//处理顶点的所有邻接边结点
{
j=p->adjvex;//邻接点
if(visited[j]==0)//未访问的邻接点
{
visited[j]=1;
printf("%3d",i);
s[++top]=j;
}//访问并入栈
p=p->next;//广度优先遍历
}//下一个邻接点
}//while(top>0)
}//if
}//D_BFS
//20.
voidTraver(AdjListg,vertypev)
//图g以邻接表为存储结构,算法从顶点v开始实现非递归深度优先遍历。
{
structarc*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->n
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本 操作 算法 汇总 B5