邻接矩阵表示法
使用邻接矩阵创建无向图
需要一个顶点表和邻接矩阵
邻接矩阵的存储结构
采用邻接矩阵建立无向网
- 输入总顶点数和总边数。
- 输入点的信息存入顶点表中。
- 初始化化为邻接矩阵，使每个权值初始化为极大值。
- 构造邻接矩阵
算法实现
在图中查找顶点
代码实现
#include <bits/stdc++.h>
#define MVnum 100
//定义最大值
using namespace std;
typedef pair<int, int> PII;
const int N = 100008;
typedef struct { //邻接矩阵的存储结构
int vexs[MVnum];//定义一个顶点表
int arcs[MVnum][MVnum];//定义一个邻接矩阵
int vexnum, arcnum;
} AMGraph;
int Localevex(AMGraph G, int u) {
for (int i = 0; i < G.vexnum; i++) {
if (u == G.vexs[i]) {
return i;//找到返回下标值,没有找到返回-1
}
}
return -1;
}
/*
该函数用来建立邻接矩阵
参数为邻接矩阵的结构类型
*/
void Create(AMGraph& G) {
cin >> G.vexnum >> G.arcnum; //读入顶点数和边数
for (int i = 0; i < G.vexnum; i++) {
cin >> G.vexs[i]; //读入顶点表的值
}
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0x3f3f3f3f; //赋值为无穷大
}
}
//构造邻接矩阵
int v1, v2, w;
for (int k = 0; k < G.arcnum; k++) {
cin >> v1 >> v2 >> w;
int i = Localevex(G, v1);
int j = Localevex(G, v2); //找到符合下标位置
G.arcs[i][j] = w; //无向图建立两条边
G.arcs[j][i] = w; //读入权值
}
}
int main () {
AMGraph G;
Create(G);
return 0;
}