跳转至

图的存储

一、邻接矩阵

1.1 定义

图的邻接矩阵\(Adjacency Matrix\) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组\(称为邻接矩阵\)存储图中的边或弧的信息。

邻接矩阵是表示图中顶点之间相邻关系的矩阵。设图G有n个顶点，则邻接矩阵是一个n×n的方阵，其中元素A[i][j]表示顶点i和顶点j之间的关系。对于无权图，A[i][j]的值为1或0，1表示顶点i和j之间有边，0表示没有边。对于带权图，A[i][j]的值可以是权值，用一个特定的值（如无穷大）表示没有边。

Text Only
1
2
A[i][j] = 1，当顶点vi与vj之间有边时
A[i][j] = 0，当顶点vi与vj之间没有边时
Text Only
1
2
3
A[i][j] = wij，当顶点vi与vj之间有边且权值为wij时
A[i][j] = ∞（或0），当顶点vi与vj之间没有边时
A[i][i] = 0（或∞），对角线元素处理方式

1.2 数据结构实现

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <limits.h>

#define MAX_VERTEX_NUM 100
#define INFINITY INT_MAX  // 表示无穷大

// 无权图的邻接矩阵
typedef struct {
  char vexs[MAX_VERTEX_NUM];           // 顶点表
  int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
  int vexnum, arcnum;                  // 顶点数和边数
} MGraph;

// 带权图的邻接矩阵
typedef struct {
  char vexs[MAX_VERTEX_NUM];           // 顶点表
  int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵，存储权值
  int vexnum, arcnum;                  // 顶点数和边数
} WeightedMGraph;
C++
 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
#include <vector>
#include <iostream>
using namespace std;

template<typename T>
class AdjacencyMatrix {
private:
    vector<T> vertices;           // 顶点集合
    vector<vector<int>> matrix;   // 邻接矩阵
    int vertexCount;              // 顶点数量
    bool weighted;                // 是否带权
    int noEdgeValue;              // 无边时的值

public:
    // 构造函数
    AdjacencyMatrix(int n, bool isWeighted = false, int noEdge = 0) 
        : vertexCount(n), weighted(isWeighted), noEdgeValue(noEdge) {
        vertices.resize(n);
        matrix.resize(n, vector<int>(n, noEdge));
        
        // 如果是带权图，对角线设为0，否则设为noEdge
        for (int i = 0; i < n; i++) {
            matrix[i][i] = weighted ? 0 : noEdge;
        }
    }
    
    // 其他成员函数...
};

1.3 邻接矩阵示例

graph LR
    A --- B
    A --- C
    B --- C
    B --- D
    C --- D

邻接矩阵

| -- | 0 | 1 | 2 | 3 |
| 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 2 | 1 | 1 | 0 | 1 |
| 3 | 0 | 1 | 1 | 0 |

特点：

  • 矩阵对称：A[i][j] = A[j][i]
  • 对角线为0（无自环）
graph LR
    A --> B
    A --> C
    B --> D
    C --> B
    C --> D

邻接矩阵

| -- | 0 | 1 | 2 | 3 |
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 0 | 0 | 0 |

特点：

  • 矩阵不对称
  • 行为出度，列为入度
graph LR
    A --> B
    A --> C
    B --> D
    C --> B
    C --> D

邻接矩阵

| -- | 0 | 1 | 2 | 3 |
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 0 | 0 | 0 |

1.4 邻接矩阵完整实现示例

邻接矩阵设计以及完整代码实现

二、领接表

三、十字链表

四、领接多重表

五、边集数组