主题：用邻接矩阵表示图
yybb
[专家分：0] 发布于 2006-08-15 11:02:00
//***以下是用邻接矩阵表示图******
#define N 100 //图的顶点数
#define E 100 //图的边数
#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef char vextype; //顶点的数据类型
typedef float adjtype; //权值类型
typedef struct
{
vextype vexs[N]; //顶点
adjtype arcs[N][N]; //权值
}graph;
void creatgraph(graph *ga,int n,int e); //建立无向网络
main()
{
graph *ga;
int i,j,n,e; //n是图的顶点数,e是图的边数
ga=(graph *)malloc(sizeof(graph));
printf("请输的顶点数和边数:");
scanf("%d %d",&n,&e);
creatgraph(ga,n,e);
printf("输出无向网络的顶点:");
for(i=0;i<=n;i++)
printf("v%c ",ga->vexs[i]);
printf("\n");
printf("图的路径形成的情况:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%-2.0f",ga->arcs[i][j]);
printf("\n");
}
}
void creatgraph(graph *ga,int n,int e) //建立无向网络
{
int i,j,k;
float w;
printf("请按顺序输入%d个顶点(按下标输入):",n);
for(i=0;i<=n;i++)
scanf("%c",&ga->vexs[i]); //读入顶点信息，建立顶点表
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
ga->arcs[i][j]=0; //邻接矩阵初始化
for(k=0;k<e;k++)
{
printf("请输入第%d条的起点、终点和权:",k+1);
scanf("%d %d %f",&i,&j,&w); //读入边(vi,vj)上的权w
ga->arcs[i][j]=w;
ga->arcs[j][i]=w; //有向图和无向图的区别
}
}
//***以上是用邻接矩阵表示图******
[em9][em9][em9][em9][em9][em18][em18][em18][em18][em20][em20][em1][em1][em1][em1][em1][em1]
回复列表 （共8个回复）
沙发
tgbtgb [专家分：490] 发布于 2006-08-19 07:13:00
读入顶点信息，建立顶点表
时，你是否回按回车键？
板凳
tgbtgb [专家分：490] 发布于 2006-08-19 07:41:00
＂读入边(vi,vj)上的权w＂
时，输入的是数字，而在
＂读入顶点信息，建立顶点表＂
时你是用的字符．这里就有了矛盾．
3 楼
tgbtgb [专家分：490] 发布于 2006-08-19 07:42:00
＂ printf("请按顺序输入%d个顶点(按下标输入):",n);
for(i=0;i<=n;i++)
scanf("%c",&ga->vexs[i]); //读入顶点信息，建立顶点表＂
时，要么i=1,要么i<n.进行循环．
4 楼
tgbtgb [专家分：490] 发布于 2006-08-19 07:54:00
我个人觉得
＂ for(k=0;k<e;k++)
{
printf("请输入第%d条的起点、终点和权:",k+1);
scanf("%d %d %f",&i,&j,&w); //读入边(vi,vj)上的权w
ga->arcs[i][j]=w;
ga->arcs[j][i]=w; //有向图和无向图的区别
}＂
应改为
＂char i,j;"再定义："int n,m,t;"
"for(k=0;k<e;k++)
{printf("请输入（Ａ－－通－－Ｂ）的两个顶点及权值Ｗ:\n");
printf("NO.%d\n",e+1);
scanf("%c %c %f",&i,&j,&w);
for(t=1;t<=e;t++)
{if(ga->vexs[t]==i)
n=t;
if(ga->vexs[t]==j)
m=t;
ga->arcs[n][m]=w;
ga->arcs[n][m]=w;
}
}
5 楼
tgbtgb [专家分：490] 发布于 2006-08-19 07:57:00
对不起！上面应改为：
for(t=0;t<e;t++)
......
n=t+1;
......
m=t+1;
.....
6 楼
yybb [专家分：0] 发布于 2006-08-19 08:58:00
有，也可以让它自动输入啊:
printf("请按顺序输入%d个顶点(按下标输入):",n);
for(i=0;i<=n;i++)
scanf("%c",&ga->vexs[i]); //读入顶点信息，建立顶点表
改为:
for(i=0;i<n;i++)
ga->vexs[i]=char(i+1);
[em13][em13][em13][em13][em13][em13][em7][em7][em7][em9][em9][em9][em15][em16][em16][em16][em16][em16][em16][em16][em16][em16]
7 楼
yybb [专家分：0] 发布于 2006-08-19 09:02:00
顶点和权是两回事啊，两者数据类型可以不同啊
[em1][em1][em1][em1][em1][em1][em1][em1][em1][em1][em1][em1][em1][em1][em16][em16][em16][em16][em16][em16][em16][em16][em16][em16][em16][em16]
8 楼
tgbtgb [专家分：490] 发布于 2006-08-19 12:23:00
你看看吧！
#define max 100
#include "malloc.h"
typedef struct
{char dd[max];
int w[max][max];
int bs;
int dds;
}g;
g *creat2(void)
{g *mg;
int i,j,a,b,c,v1,v2,v3;
char aa,w1,w2;
mg=(g *)malloc(sizeof(g));
printf("请输入顶点数和边数:\n");
scanf("%d%d",&mg->dds,&mg->bs);
printf("请输入各个顶点:(为一个字符)\n");
for(b=0;b<mg->dds;b++)
{printf("NO.%d\n",b+1);
scanf("%c",&aa);
scanf("%c",&mg->dd[b]);
}
for(i=0;i<mg->dds;i++)
for(j=0;j<mg->dds;j++)
mg->w[i][j]=0;
for(a=0;a<mg->bs;a++)
{printf("请输入A-到-B的权值w(注:总共要输入3个.):\n");
scanf("%c",&aa);
scanf("%c",&w1);
printf("\n到\n");
scanf("%c",&aa);
scanf("%c",&w2);
printf("\n权值:\n");
scanf("%c",&aa);
scanf("%d",&v3);
for(c=0;c<mg->dds;c++)
{if(w1==mg->dd[c])
v1=c+1;
if(w2==mg->dd[c])
v2=c+1;
}
mg->w[v1-1][v2-1]=v3;
}
return(mg);
}
void print2(g *mm)
{int i,j,v1,v2;
printf("数组表示为:\n");
printf("\n");
for(i=0;i<mm->dds;i++)
{for(j=0;j<mm->dds;j++)
printf("%4d",mm->w[i][j]);
printf("\n");
}
printf("\n");
printf("其它信息为:\n");
printf("\t总共有顶点: %d\n",mm->dds);
printf("\t总共有边: %d\n",mm->bs);
printf("\t相通的顶点为:\n");
for(v1=0;v1<mm->dds;v1++)
for(v2=0;v2<mm->dds;v2++)
if(mm->w[v1][v2]!=0)
printf("\n\t%c---到---%c\n",mm->dd[v1],mm->dd[v2]);
}
g *creat1(void)
{g *mg;
int i,j,a,b,c,v1,v2,v3;
char aa,w1,w2;
mg=(g *)malloc(sizeof(g));
printf("请输入顶点数和边数:\n");
scanf("%d%d",&mg->dds,&mg->bs);
printf("请输入各个顶点:(为字符)\n");
for(b=0;b<mg->dds;b++)
{printf("NO.%d\n",b+1);
scanf("%c",&aa);
scanf("%c",&mg->dd[b]);
}
for(i=0;i<mg->dds;i++)
for(j=0;j<mg->dds;j++)
mg->w[i][j]=0;
for(a=0;a<mg->bs;a++)
{printf("请输入A-连-B的权值w(注:总共要输入3个.):\n");
scanf("%c",&aa);
scanf("%c",&w1);
printf("\n通\n");
scanf("%c",&aa);
scanf("%c",&w2);
printf("\n权值:\n");
scanf("%c",&aa);
scanf("%d",&v3);
for(c=0;c<mg->dds;c++)
{if(w1==mg->dd[c])
v1=c+1;
if(w2==mg->dd[c])
v2=c+1;
}
mg->w[v1-1][v2-1]=v3;
mg->w[v2-1][v1-1]=v3;
}
return(mg);
}
void print1(g *mm)
{int i,j,v1,v2;
printf("\n");
printf("\n");
printf("\n");
printf("数组表示为:\n");
printf("\n");
for(i=0;i<mm->dds;i++)
{for(j=0;j<mm->dds;j++)
printf("%4d",mm->w[i][j]);
printf("\n");
}
printf("\n");
printf("\t其它信息为:\n");
printf("\t总共有顶点: %d\n",mm->dds);
printf("\t总共有边: %d\n",mm->bs);
printf("\t相通的顶点为:\n");
for(v1=0;v1<mm->dds;v1++)
for(v2=0;v2<mm->dds;v2++)
if(mm->w[v1][v2]!=0&&v1>=v2)
printf("\t%c---通---%c\n",mm->dd[v1],mm->dd[v2]);
}
main()
{g *m,*n;
int fag,i;
do{
printf("\n");
printf("\t=====================\n");
printf("\t1----------建立有向图.\n");
printf("\t2----------输出有向图.\n");
printf("\t3----------建立无向图.\n");
printf("\t4----------输出无向图.\n");
printf("\t0----------退出.\n");
printf("\t=====================\n");
printf("\n");
printf("请选择:\n");
scanf("%d",&i);
switch(i)
{case 0:fag=0;break;
case 1:m=creat2();break;
case 2:print2(m);break;
case 3:n=creat1();break;
case 4:print1(n);break;
defult :printf("ERROR\n");
}
}while(fag);
}
我来回复
您所在位置：