对于任一确定的有向图,邻接矩阵是不是唯一的,邻接表呢?

发布网友发布时间：2022-04-24 16:44

共1个回答

热心网友时间：2023-10-23 10:24

邻接矩阵
所谓邻接矩阵（Adjacency Matrix）的存储结构，就是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。假设图G＝（V，E）有n 个确定的顶点，即V＝{v0,v1,…,vn-1},则表示G 中各顶点相邻关系为一个n×n 的矩阵，矩阵的元素为：

下面举个栗子：

代码实现如下：
#include<iostream>
using namespace std;

//————图的邻接矩阵存储表示————

#define MaxInt 0//表示权值的无穷
#define MVNum 100//最大顶点数，应由用户定义
#define OK 1

typedef int Status;
typedef char VerTexType;//定点的数据类型
typedef int ArcType;//边的权值类型

typedef struct{
VerTexType vexs[MVNum];//顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum,arcnum;//图的当前顶点数和边数
}AMGraph;

Status LocateVex(AMGraph G,VerTexType v){
int i;
for(i=0;i<G.vexnum;i++){
if(v==G.vexs[i])
return i;
}
}

Status CreateUDN(AMGraph &G){//采用邻接矩阵表示法，创建无向网
Status i,j,k,w;
VerTexType v1,v2;
printf("请输入总顶点数和总边数:");
scanf("%d %d",&G.vexnum,&G.arcnum);// 总顶点数,总边数
printf("请依次输入顶点:\n");
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;
puts("请依次输入边的两个顶点以及权值:");
for(k=0;k<G.arcnum;k++){//构造邻接矩阵
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 OK;
}

int main(){
int i,j;
AMGraph G;
CreateUDN(G);
puts("构成的邻接矩阵为：");
for(i=0;i<G.vexnum;i++){
for(j=0;j<G.vexnum;j++)
printf("%d\t",G.arcs[i][j]);
printf("\n");
}
return 0;