本文共 1559 字，大约阅读时间需要 5 分钟。

图表是对象和对象之间存在的关系的有限集合，可以通过顶点和边来表示。顶点代表对象，边代表它们之间的关系。根据不同需求，图可以分为有向图和无向图两种形式。

在有向图中，每条边由一对有序顶点(i, j)表示，边从顶点i指向顶点j。在无向图中，边由无序顶点对(i, j)表示，即顶点i和顶点j之间存在相互连接的关系。

探索图形的表示方法，邻接矩阵和邻接表是两种常用的方法。邻接矩阵是一个N×N的二进制矩阵，其中A[i][j]为1表示顶点i到顶点j有边存在。对于示例图D.1，邻接矩阵显示了有向图的边信息，而UD.1的邻接矩阵显示了无向图的边信息。

邻接表则采用数组形式存储，每个顶点对应一个列表，存储直接连接的顶点。在有向图中，D.1的邻接表只添加了起点到终点的连接；而在无向图中，UD.1的邻接表会添加相互连接的调节。

构造邻接矩阵需要初始化一个N×N的矩阵，并为每条边设置对应的值。对于无向图，还需要为反向边设置值。以下是实现邻接矩阵和邻接表的C++代码示例：

#include 
   
    
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector
    
     
      > adj_matrix(n, vector
      
       (n, 0));
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj_matrix[u][v] = 1;
        if (u != v) adj_matrix[v][u] = 1; // 无向图时的处理
    }
    // 输出邻接矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << adj_matrix[i][j] << " ";
        }
        cout << endl;
    }
    adj_list[n].clear();
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj_list[u].push_back(v);
        if (u != v) adj_list[v].push_back(u); // 无向图时的处理
    }
    // 输出邻接表
    for (int i = 0; i < n; ++i) {
        cout << "节点" << i << "的邻接点是：";
        for (int j : adj_list[i]) {
            cout << j << " ";
        }
        cout << endl;
    }
    return 0;
}
      
     
    
   

在实际应用中，邻接矩阵适合密集图，而邻接表更适合稀疏图。Floyd-Warshall算法需要邻接矩阵，而DFS和BFS通常更适合邻接表。因此，选用哪种表示方法取决于具体需求和数据结构。

图的表示方法不仅影响了数据结构和算法的选择，还决定了空间和时间复杂度。邻接矩阵的复杂度为O(N²)，查找边存在的复杂度为O(1)；邻接表则为O(N + M)，查找复杂度为O(度)。在实际应用中，应根据密度判断选择适合的表示方式，以在性能和空间上达到最佳平衡。

转载地址：http://honiz.baihongyu.com/