数据结构-邻接矩阵

介绍

邻接矩阵，是表示图的一种常见方式，具体表现为一个记录了各顶点连接情况的呈正方形的矩阵。

假设一共有以下顶点，其连接关系如图所示

那么，怎么表示它们之间的连接关系呢？

我们发现，各条边所连接的都是两个顶点，联想到我们之前学过的能表示两个量直接关系的数据结构，二维数组就是一个不错的选择。

如果i,j两个节点之间存在边联系它们，那么就将graph[i][j]值记为1，如果不存在边联系它们，就记为0.

这样一来，可以表示图中节点关系的邻接矩阵可以具象化为：

由于例图为无向图（即各顶点间路径没有具体指向），所以graph[i][j]与graph[j][i]的值相同，有向图中则需要将两个值单独判断

具体实现

根据输入的各条边的信息（即两个顶点）可以生成邻接矩阵

    cin>>n>>m;for (int i=0;i<n;i++) {for (int j=0;j<n;j++) {graph[i][j]=0;//初始化邻接矩阵}}for (int i=0;i<m;i++) {int u,v;cin>>u>>v;//读入边信息，更新邻接矩阵graph[u][v]=1;graph[v][u]=1; //如果是无向图，则还要更新graph[v][u]}for (int i=0;i<n;i++) {// 输出邻接矩阵for (int j=0;j<n;j++) {cout<<graph[i][j]<< " ";}cout<<endl;}

根据邻接矩阵来实现各顶点相邻顶点的输出

1）借助结构体来方便记录各顶点的相邻情况

#define MAXN 100 // 最大顶点数
int graph[MAXN][MAXN]; // 邻接矩阵
struct Node{int value;int num;//记录相邻顶点数目Node** neib;//记录相邻顶点
};

2）遍历邻接矩阵，将相邻的顶点添入结构体内，记录相邻顶点

Node* init(int v) {//初始化顶点信息Node* temp=(Node*)malloc(sizeof(Node));temp->value=v;temp->num=0;//邻居数开始为0temp->neib=NULL;//记录邻居的指针一开始为空return temp;
}
Node** generateGraph() {Node** nodes=(Node**)malloc(n*sizeof(Node*));//为结构体分配空间储存每个顶点信息for (int i=0; i<=n; i++) {nodes[i]=init(i);//初始化每一个顶点代表的结构体}for (int i=0; i<=n; i++) {for (int j=i; j<=n; j++) {if (graph[i][j]==1) {//如果两个顶点相邻addNeighbor(nodes[i],nodes[j]);addNeighbor(nodes[j],nodes[i]); // 无向图需要更新nodes[j]->neibm++;}}}return nodes;
}

3）为邻接矩阵中为1的两个顶点更新邻居信息

void addNeighbor(Node* temp,Node* neighbor) {temp->num++;//邻居数增加
//重新分配指针内存，增加指针数，用来指向新的邻居temp->neib=(Node**) realloc(temp->neib,temp->num*sizeof(Node*));temp->neib[temp->num-1]=neighbor;//记录新邻居地址
}

这里用realloc来重新分配内存空间

malloc与realloc的不同：

malloc：用于申请一块指定大小的内存空间，并返回指向该空间的地址

realloc：接受两个参数：旧的内存指针与新的大小，用于重新调整一个已经分配完空间的内存大小，并可以将原空间的内容复制到新开辟的空间中，同时释放原内存

4）输出顶点信息

for (int i=0;i<=n;i++) {cout<<nodes[i]->value)<<":";for (int j=0;j<=nodes[i]->num;j++) {//输出所有相邻顶点cout<<nodes[i]->neib[j]->value<<" ";}cout<<endl;}