通过邻接矩阵实现图的存储

图的存储结构

通过邻接矩阵的方式建立图

邻接矩阵(Adjacency Matrix)的存储结构就是通过一维数组存储图中顶点的信息，用矩阵表示图中各个顶点的的临界关系，而矩阵通过一个二维数组表示。

图的分类及表示

图的矩阵中表示方法

在无向图中矩阵的表示


无向网中矩阵的表示


存储顶点信息的结构

存储图的信息时，要通过结构体来定义数据类型，以无向网为例定义如下：

1
2
3
4
5
6
7
8
#define MAX_VEX 100            // 图中含有顶点的最多个数
#define INF 65535              //如果两个顶点之间不可达，用无穷表示距离
struct Graph{
    char vexs[MAX_VEX];        //代表顶点信息的名称
    int arc[MAX_VEX][MAX_VEX]; //两个顶点之间的权值
    int numvex;					// 表示顶点的个数
	int	numarc;					// 边的个数
};

图信息的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void CreateGraph(Graph &G){
    int vi, vj, w;
    cout << "please enter the number of vertexes and arcs : \n";
    cin >> G.numvex >> G.numarc;                //输入顶点与边的个数
    for(int i = 0; i < G.numvex; i++){			//为每个顶点初始化信息
        printf("Please enter the NO.%d name of vex : ",i+1);
        cin >> G.vexs[i];
    }
    for(int i = 0; i < G.numvex; i++){			//初始化顶点之间的权值 默认为无穷
        for(int j = 0; j < G.numvex ;j++){
            G.arc[i][j] = INF;
        }
    }
    cout << endl;
    for(int i = 0; i < G.numarc; i++){			//根据边的条数，为每一条边赋值
        cout<< "Enter the subscripts and weights from vertex vi to vertex vj : ";
        cin >> vi >> vj >> w;
        G.arc[vi][vj] = w;						//在无向网中满足图对称性，即Vi-Vj 和Vj-Vi的距离相等，实际就是一条路径
        G.arc[vj][vi] = w;
    }
}

完整实现过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#define MAX_VEX 100
#define INF 65535

using namespace std;
struct Graph{
    char vexs[MAX_VEX];
    int arc[MAX_VEX][MAX_VEX];
    int numvex,numarc;
};
void CreateGraph(Graph &G){
    int vi, vj, w;
    cout << "please enter the number of vertexes and arcs : \n";
    cin >> G.numvex >> G.numarc;
    for(int i = 0; i < G.numvex; i++){
        printf("Please enter the NO.%d name of vex : ",i+1);
        cin >> G.vexs[i];
    }
    for(int i = 0; i < G.numvex; i++){
        for(int j = 0; j < G.numvex ;j++){
            G.arc[i][j] = INF;
        }
    }
    cout << endl;
    for(int i = 0; i < G.numarc; i++){
        cout<< "Enter the subscripts and weights from vertex vi to vertex vj : ";
        cin >> vi >> vj >> w;
        G.arc[vi][vj] = w;
        G.arc[vj][vi] = w;
    }
}
void DispalyGraph(Graph G){
    for(int i = 0; i < G.numvex; i++) cout << G.vexs[i] << " ";
    cout << endl;
    for(int i = 0; i < G.numvex; i++){
        for(int j = 0; j < G.numvex; j++){
            if(G.arc[i][j] == INF) printf("%6s", "∞");
            else printf("%6d", G.arc[i][j]);
        }
        cout << endl;
    }
}
int main(){
    Graph G;
    CreateGraph(G);
    DispalyGraph(G);
    return 0;
}

实现结果

以下面的无向网为例：

  • 顶点个数为9 边数为 16

  • 顶点信息：
    0 1 1
    0 2 5
    1 3 7
    1 4 5
    4 2 1
    2 3 7
    3 6 3
    6 4 6
    4 7 9
    7 5 5
    6 8 7
    7 8 4
    1 2 3
    3 4 2
    4 5 3
    6 7 2

  • 输出结果如下：