本篇文章给大家谈谈c语言如何输入无向图,以及c++无向图的创建对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。
本文目录一览:
1、怎么用c语言生成一个固定顶点数和固定边数的无向图2、c语言编写请简单点。用带权邻接矩阵输入一幅无向图,使用两种不同的算法计算出最短路径长度并输出路径。3、C语言实现无向图
怎么用c语言生成一个固定顶点数和固定边数的无向图
#defineInfinity1000#defineMaxVertexNum35#defineMAX40#include#include#include#include#includetypedefstructarcell//边的权值信息{intadj;//权值}arcell,adjmatrix[MaxVertexNum][MaxVertexNum];//图的邻接矩阵类型typedefstructvexsinfo//顶点信息{intposition;//景点的编号charname[32];//景点的名称charintroduction[256];//景点的介绍}vexsinfo;typedefstructmgraph//图结构信息{vexsinfovexs[MaxVertexNum];//顶点向量(数组)adjmatrixarcs;//邻接矩阵intvexnum,arcnum;//分别指定顶点数和边数}mgraph;//全局变量intvisited[35];//用于标志是否已经访问过intd[35];//用于存放权值或存储路径顶点编号mgraphcampus;//图变量(大学校园)//(1)对图初始化mgraphinitgraph(){inti=0,j=0;mgraphc;c.vexnum=28;//顶点个数c.arcnum=39;//边的个数for(i=0;i”,c.vexs[d[s]].name);//输出该路径。s=0时为起点mprintf(“%s”,c.vexs[d[s]].name);//输出最后一个景点名(即顶点n的名字,此时s==k)printf(“\n\n”);}else{s=0;while(sc.vexnum){printf(“\n你所输入的景点编号不存在\n”);printf(“请重新输入:”);scanf(“%d”,v0);}//whilefor(v=0;v%s”,c.vexs[w].name);}printf(“—-%s”,c.vexs[v].name);printf(“\n总路线长为%d米\n\n”,d[v]);}//for}//shortestpath//(6)-(11)修改图的信息。包括建图、更新信息、删除、增加结点和边//(6)构造图的邻接矩阵intcreatgragh(mgraphc)//建图。以图的邻接矩阵存储图{inti,j,m,n;intv0,v1;intdistance;printf(“请输入图的顶点数和边数:\n”);scanf(“%d%d”,c.vexnum,c.arcnum);printf(“下面请输入景点的信息:\n”);for(i=0;i=0n=0){c.arcs[m][n].adj=distance;c.arcs[n][m].adj=c.arcs[m][n].adj;}}return1;}//creatgragh//(7)更新图的部分信息。返回值:1intnewgraph(mgraphc){intchangenum;//计数。用于记录要修改的对象的个数inti,m,n,t,distance,v0,v1;printf(“\n下面请输入你要修改的景点的个数:\n”);scanf(“%d”,changenum);while(changenumc.vexnum){printf(“\n输入错误!请重新输入”);scanf(“%d”,changenum);}for(i=0;ic.arcnum){printf(“\n输入错误!请重新输入”);scanf(“%d”,changenum);}printf(“\n下面请输入更新边的信息:\n”);for(i=1;i=0n=0){c.arcs[m][n].adj=distance;c.arcs[n][m].adj=c.arcs[m][n].adj;}}return1;}//newgraph
c语言编写请简单点。用带权邻接矩阵输入一幅无向图,使用两种不同的算法计算出最短路径长度并输出路径。
//Floyed 实现赋权无向图定点对间的最短路径,时间复杂度O(n^3)
1,从任意一条单边路径开始。所有两点之间的距离是边的权,或者无穷大,如果两点之间没有边相连。
2,对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
#includestdio.h
int main()
{
int c[20][20],parth[20][20],i,j,k,t1,t2,t3,n,x,y,re;
printf(“输入图的顶点数:”);
scanf(“%d”,n);
for(i=1;i=n;i++)
{
for(j=i+1;j=n;j++)
{
printf(“输入边(%d,%d)的权值,若不存在输入10000:”,i,j);
scanf(“%d”,c[i][j]);
}
}
如果是有向图就删掉这里”//for(i=1;i=n;i++)
//{
///////////////////////////////////////for(j=1;j=i;j++)
////////////////////////////////////////c[i][j]=c[j][i];
/////////////////////////////////////////}”
for(i=1;i=n;i++)
c[i][i]=0;//自己到自己的权值为0
for(i=1;i=n;i++) //初始化路径
{
for(j=1;j=n;j++)
parth[i][j]=0;
}
for(k=1;k=n;k++)//k是中间节点,i是起点j是中点。其实就是枚举中间节点,来求i j 的最短路径
{
for(i=1;i=n;i++)
{
for(j=1;j=n;j++)
{
t1=c[i][k];
t2=c[k][j];
t3=c[i][j];
if(t1!=10000t2!=10000(t3==10000||t1+t2t3)) //松弛 覆盖原来的最短路
{c[i][j]=t1+t2,parth[i][j]=k;}//记录i j的中间点是k
}
}
}
while(1)//也可以用递归的形式输出parth
{
printf(“输入2点:”);
scanf(“%d%d”,x,y);
printf(“最短距离为%d\n”,c[x][y]);
printf(“%d “,x);
re=y;
while(parth[x][y]!=0)
{
printf(“%d “,parth[x][y]);
y=parth[x][y];
}
printf(“%d\n”,re);
}
return 0;
}
C语言实现无向图
可以用邻接矩阵表示法:
#define max 100
typedef struct
{
int vex[max];//存储顶点值,类型可以变
int edge[max][max];//存储顶点之间的关系,以1或者0表示,1为有边,0为无
int e,v;//vertex存储顶点数,edge存储边的条数,所以无向图1的个数是边的个数的两倍,谢谢。
}m;
关于c语言如何输入无向图和c++无向图的创建的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。