提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
一、无向网
1、思路:
(1)输入总顶点数和总边数
(2)依次输入顶点的信息放入顶点表中
(3)初始化邻接矩阵,极大值∞
(4)构造邻接矩阵
2、代码
#include<iostream>
using namespace std;
#define MaxInt 32767 //表示极大值
#define MVNum 100 //最大顶点数
typedef char VerTexType; //设置顶点类型为字符型
typedef int ArcType; //设置权重为整型
typedef struct{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //顶点数和边数
}AMGraph;
从顶点表中查找顶点
int LocateVex(AMGraph G,VerTexType u){
int i;
for(i=0;i<G.vexnum;i++)
if(u==G.vexs[i]) return i;
return -1;
}
//构造无向网
int CreateUDN(AMGraph &G){
int i,j,k;
cout<<"请输入顶点数和边数:";
cin>>G.vexnum>>G.arcnum; //输入顶点数和边数
cout<<"输入顶点:";
for(i=0;i<G.vexnum;i++)
cin>>G.vexs[i]; //顶点表
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=MaxInt; //初始化邻接矩阵
for(k=0;k<G.arcnum;k++){ //构造邻接矩阵
VerTexType v1,v2;
ArcType w;
cout<<"请输入依附的顶点和权值:";
cin>>v1>>v2>>w;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=w; //边(v1,v2)权重置为w
G.arcs[j][i]=G.arcs[i][j]; //无向网,对称
}
return 1;
}
void Show(AMGraph G){
int i,j;
for(i=0;i<G.vexnum;i++){
for(j=0;j<G.vexnum;j++)
if(G.arcs[i][j]==MaxInt) cout<<"∞"<<' ';
else cout<<G.arcs[i][j]<<' ';
cout<<endl;
}
}
int main(){
AMGraph G;
CreateUDN(G);
cout<<endl<<"构造的无向网为:";
Show(G);
return 1;
}
3、运行结果
![](https://img-blog.csdnimg.cn/5a3158437ce84ad88e62e030c91defc0.jpeg)
![](https://img-blog.csdnimg.cn/8f026f7052774aea97e87ff19ab3268f.png)
三、其他
(1)无向图
初始化邻接矩阵时,w均为0
构造邻接矩阵时,w为1
//构造无向图
int CreateUDG(AMGraph &G){
int i,j,k;
cout<<"请输入顶点数和边数:";
cin>>G.vexnum>>G.arcnum;
cout<<"输入顶点:";
for(i=0;i<G.vexnum;i++) cin>>G.vexs[i];
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=0; //初始化邻接矩阵,权为0
for(k=0;k<G.arcnum;k++){
VerTexType v1,v2;
ArcType w;
cout<<"输入依附的顶点:";
cin>>v1>>v2;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=1; //构造邻接矩阵,权为1
G.arcs[j][i]=G.arcs[i][j];
}
return 1;
}
![](https://img-blog.csdnimg.cn/4c7bb5c10a90403f941e554d15e62316.jpeg)
![](https://img-blog.csdnimg.cn/e52d4f3f408b41f8b6aab00a2a9b2539.png)
(2)有向网
非对称,无需G.arcs[j][i]=G.arcs[i][j]
//构造有向网
int CreateDN(AMGraph &G){
int i,j,k;
cout<<"请输入顶点数和边数:";
cin>>G.vexnum>>G.arcnum;
cout<<"输入顶点:";
for(i=0;i<G.vexnum;i++)
cin>>G.vexs[i];
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=MaxInt;
for(k=0;k<G.arcnum;k++){
VerTexType v1,v2;
ArcType w;
cout<<"请输入依附的顶点和权值:";
cin>>v1>>v2>>w;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=w;
//G.arcs[j][i]=G.arcs[i][j]; //去掉该条语句
}
return 1;
}
![](https://img-blog.csdnimg.cn/cf84042ead35449cb3d57b73fafccbf2.jpeg)
![](https://img-blog.csdnimg.cn/d636b66da9d04428a39289de04317a83.png)
(3)有向图
初始化w为0
构造时w为1
无需G.arcs[j][i]=G.arcs[i][j]
//构造有向图
int CreateDG(AMGraph &G){
int i,j,k;
cout<<"输入顶点数和边数:";
cin>>G.vexnum>>G.arcnum;
cout<<"输入顶点:";
for(i=0;i<G.vexnum;i++) cin>>G.vexs[i];
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=0; //初始化为0
for(k=0;k<G.arcnum;k++){
VerTexType v1,v2;
cout<<"输入依附的顶点:";
cin>>v1>>v2;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=1; //构造时权重为1
}
return 1;
}
![](https://img-blog.csdnimg.cn/df95343323eb4ebd8b707d5aeb6b5ee5.jpeg)
![](https://img-blog.csdnimg.cn/1ca16524aab345198157efe0038fad7d.png)