# 图论基础与C++实现：邻接矩阵与邻接表的全面解析

## 图论基本概念与数学模型

图论是研究顶点和边组成的数学结构的学科，在计算机科学中有着广泛的应用。一个图G可以形式化地定义为二元组(V, E)，其中V是顶点集合，E是边集合。根据边的特性，图可以分为无向图和有向图；根据边是否有权重，可以分为无权图和带权图。

```cpp

// 图的基本类型定义

enum GraphType {

    UNDIRECTED,      // 无向图

    DIRECTED,        // 有向图

    WEIGHTED,        // 带权图

    MULTIGRAPH       // 多重图（允许平行边）

};

// 顶点和边的抽象表示

struct Vertex {

    int id;          // 顶点标识符

    string label;    // 可选标签

    // 其他属性...

};

struct Edge {

    int from;        // 起点

    int to;          // 终点

    int weight;      // 权重（对于带权图）

    // 其他属性...

};

```

## 邻接矩阵：直观的二维数组表示

邻接矩阵是最直观的图存储方式，使用二维数组表示顶点间的连接关系。

```cpp

#include <vector>

#include <iostream>

#include <limits>

using namespace std;

class AdjacencyMatrix {

private:

    vector<vector<int>> matrix;  // 邻接矩阵

    int vertexCount;            // 顶点数量

    bool isDirected;           // 是否为有向图

    bool isWeighted;           // 是否为带权图

    const int INF = numeric_limits<int>::max();  // 表示无穷大

public:

    // 构造函数

    AdjacencyMatrix(int n, bool directed = false, bool weighted = false) 

        : vertexCount(n), isDirected(directed), isWeighted(weighted) {

        

        // 初始化矩阵

        matrix.resize(n, vector<int>(n, 0));

        

        if (weighted) {

            // 对于带权图，用INF表示无边

            for (int i = 0; i < n; i++) {

                for (int j = 0; j < n; j++) {

                    if (i != j) matrix[i][j] = INF;

                }

            }

        }

    }

    

    // 添加边

    void addEdge(int u, int v, int weight = 1) {

        if (u < 0 || u >= vertexCount || v < 0 || v >= vertexCount) {

            throw out_of_range("顶点索引越界");

        }

        

        matrix[u][v] = weight;

        

        // 如果是无向图，对称位置也要设置

        if (!isDirected) {

            matrix[v][u] = weight;

        }

    }

    

    // 删除边

    void removeEdge(int u, int v) {

        if (u < 0 || u >= vertexCount || v < 0 || v >= vertexCount) {

            throw out_of_range("顶点索引越界");

        }

        

        if (isWeighted) {

            matrix[u][v] = INF;

            if (!isDirected) matrix[v][u] = INF;

        } else {

            matrix[u][v] = 0;

            if (!isDirected) matrix[v][u] = 0;

        }

    }

    

    // 检查边是否存在

    bool hasEdge(int u, int v) const {

        if (u < 0 || u >= vertexCount || v < 0 || v >= vertexCount) {

            return false;

        }

        

        if (isWeighted) {

            return matrix[u][v] != INF;

        } else {

            return matrix[u][v] != 0;

        }

    }

    

    // 获取边权重

    int getWeight(int u, int v) const {

        if (!hasEdge(u, v)) {

            throw runtime_error("边不存在");

        }

        return matrix[u][v];

    }

    

    // 获取邻居顶点

    vector<int> getNeighbors(int v) const {

        if (v < 0 || v >= vertexCount) {

            throw out_of_range("顶点索引越界");

        }

        

        vector<int> neighbors;

        for (int i = 0; i < vertexCount; i++) {

            if (hasEdge(v, i)) {

                neighbors.push_back(i);

            }

        }

        return neighbors;

    }

    

    // 打印矩阵

    void printMatrix() const {

        cout << "邻接矩阵 (" << vertexCount << "x" << vertexCount << "):\n";

        for (int i = 0; i < vertexCount; i++) {

            for (int j = 0; j < vertexCount; j++) {

                if (isWeighted && matrix[i][j] == INF) {

                    cout << "INF ";

                } else {

                    cout << matrix[i][j] << " ";

                }

            }

            cout << endl;

        }

    }

    

    // 计算顶点度（无向图）

    int getDegree(int v) const {

        if (isDirected) {

            throw runtime_error("有向图应使用入度和出度");

        }

        

        int degree = 0;

        for (int i = 0; i < vertexCount; i++) {

            if (hasEdge(v, i)) degree++;

        }

        return degree;

    }

    

    // 计算入度和出度（有向图）

    pair<int, int> getInOutDegree(int v) const {

        if (!isDirected) {

            throw runtime_error("无向图应使用度");

        }

        

        int inDegree = 0, outDegree = 0;

        for (int i = 0; i < vertexCount; i++) {

            if (hasEdge(i, v)) inDegree++;    // 指向v的边

            if (hasEdge(v, i)) outDegree++;   // 从v出发的边

        }

        return {inDegree, outDegree};

    }

};

// 邻接矩阵使用示例

void adjacencyMatrixDemo() {

    // 创建有5个顶点的无向无权图

    AdjacencyMatrix graph(5, false, false);

    

    // 添加边

    graph.addEdge(0, 1);

    graph.addEdge(0, 4);

    graph.addEdge(1, 2);

    graph.addEdge(1, 3);

    graph.addEdge(1, 4);

    graph.addEdge(2, 3);

    graph.addEdge(3, 4);

    

    // 打印矩阵

    graph.printMatrix();

    

    // 获取顶点0的邻居

    vector<int> neighbors = graph.getNeighbors(0);

    cout << "顶点0的邻居: ";

    for (int n : neighbors) {

        cout << n << " ";

    }

    cout << endl;

    

    // 创建带权有向图

    AdjacencyMatrix weightedGraph(4, true, true);

    

    weightedGraph.addEdge(0, 1, 5);

    weightedGraph.addEdge(0, 3, 10);

    weightedGraph.addEdge(1, 2, 3);

    weightedGraph.addEdge(2, 3, 1);

    

    weightedGraph.printMatrix();

}

```

## 邻接表：高效的稀疏图表示

对于稀疏图（边数远小于顶点数平方），邻接表是更高效的存储方式。

```cpp

#include <list>

#include <vector>

#include <iostream>

#include <queue>

#include <stack>

using namespace std;

// 邻接表节点定义（用于带权图）

struct AdjListNode {

    int dest;           // 目标顶点

    int weight;         // 边权重

    AdjListNode* next;  // 下一个节点

    

    AdjListNode(int d, int w = 1) : dest(d), weight(w), next(nullptr) {}

};

class AdjacencyList {

private:

    vector<AdjListNode*> heads;  // 邻接表头指针数组

    int vertexCount;             // 顶点数量

    bool isDirected;             // 是否为有向图

    bool isWeighted;             // 是否为带权图

    

public:

    // 构造函数

    AdjacencyList(int n, bool directed = false, bool weighted = false) 

        : vertexCount(n), isDirected(directed), isWeighted(weighted) {

        heads.resize(n, nullptr);

    }

    

    // 析构函数

    ~AdjacencyList() {

        clear();

    }

    

    // 清空邻接表

    void clear() {

        for (int i = 0; i < vertexCount; i++) {

            AdjListNode* current = heads[i];

            while (current != nullptr) {

                AdjListNode* temp = current;

                current = current->next;

                delete temp;

            }

            heads[i] = nullptr;

        }

    }

    

    // 添加边

    void addEdge(int u, int v, int weight = 1) {

        if (u < 0 || u >= vertexCount || v < 0 || v >= vertexCount) {

            throw out_of_range("顶点索引越界");

        }

        

        // 创建新节点并添加到链表头部

        AdjListNode* newNode = new AdjListNode(v, weight);

        newNode->next = heads[u];

        heads[u] = newNode;

        

        // 如果是无向图，添加反向边

        if (!isDirected) {

            AdjListNode* reverseNode = new AdjListNode(u, weight);

            reverseNode->next = heads[v];

            heads[v] = reverseNode;

        }

    }

    

    // 删除边

    void removeEdge(int u, int v) {

        if (u < 0 || u >= vertexCount || v < 0 || v >= vertexCount) {

            throw out_of_range("顶点索引越界");

pe.daojubao.com>tz.daojubao.com>n1.daojubao.com>

        }

        

        // 从u的邻接表中删除v

        removeFromList(u, v);

        

        // 如果是无向图，从v的邻接表中删除u

        if (!isDirected) {

            removeFromList(v, u);

        }

    }

    

    // 从链表中删除节点

    void removeFromList(int src, int dest) {

        AdjListNode* current = heads[src];

        AdjListNode* prev = nullptr;

        

        while (current != nullptr) {

            if (current->dest == dest) {

                if (prev == nullptr) {

                    // 删除头节点

                    heads[src] = current->next;

                } else {

                    prev->next = current->next;

                }

                delete current;

                return;

            }

            prev = current;

            current = current->next;

        }

    }

    

    // 检查边是否存在

    bool hasEdge(int u, int v) const {

        if (u < 0 || u >= vertexCount || v < 0 || v >= vertexCount) {

            return false;

        }

        

        AdjListNode* current = heads[u];

        while (current != nullptr) {

            if (current->dest == v) {

                return true;

            }

            current = current->next;

        }

        return false;

    }

    

    // 获取边权重

    int getWeight(int u, int v) const {

        if (!hasEdge(u, v)) {

            throw runtime_error("边不存在");

        }

        

        AdjListNode* current = heads[u];

        while (current != nullptr) {

            if (current->dest == v) {

                return current->weight;

            }

            current = current->next;

        }

        throw runtime_error("边不存在");

    }

    

    // 获取邻居顶点

    vector<int> getNeighbors(int v) const {

        if (v < 0 || v >= vertexCount) {

            throw out_of_range("顶点索引越界");

        }

        

        vector<int> neighbors;

        AdjListNode* current = heads[v];

        while (current != nullptr) {

            neighbors.push_back(current->dest);

            current = current->next;

        }

        return neighbors;

    }

    

    // 获取带权邻居（返回顶点和权重对）

    vector<pair<int, int>> getWeightedNeighbors(int v) const {

        if (v < 0 || v >= vertexCount) {

            throw out_of_range("顶点索引越界");

        }

        

        vector<pair<int, int>> neighbors;

        AdjListNode* current = heads[v];

        while (current != nullptr) {

            neighbors.push_back({current->dest, current->weight});

            current = current->next;

        }

        return neighbors;

    }

    

    // 打印邻接表

    void printList() const {

        cout << "邻接表:\n";

        for (int i = 0; i < vertexCount; i++) {

            cout << "顶点 " << i << ": ";

            AdjListNode* current = heads[i];

            while (current != nullptr) {

                cout << current->dest;

                if (isWeighted) {

                    cout << "(" << current->weight << ")";

                }

                cout << " ";

                current = current->next;

            }

            cout << endl;

        }

    }

    

    // 广度优先搜索

    vector<int> bfs(int start) const {

        if (start < 0 || start >= vertexCount) {

            throw out_of_range("起始顶点索引越界");

        }

        

        vector<bool> visited(vertexCount, false);

        vector<int> traversal;

        queue<int> q;

        

        visited[start] = true;

        q.push(start);

        

        while (!q.empty()) {

            int current = q.front();

            q.pop();

            traversal.push_back(current);

            

            // 获取所有邻居

            AdjListNode* node = heads[current];

            while (node != nullptr) {

                int neighbor = node->dest;

                if (!visited[neighbor]) {

                    visited[neighbor] = true;

                    q.push(neighbor);

                }

                node = node->next;

            }

        }

        

        return traversal;

    }

    

    // 深度优先搜索（递归）

    vector<int> dfsRecursive(int start) const {

        if (start < 0 || start >= vertexCount) {

            throw out_of_range("起始顶点索引越界");

        }

        

        vector<bool> visited(vertexCount, false);

        vector<int> traversal;

        dfsHelper(start, visited, traversal);

        return traversal;

    }

    

    // 深度优先搜索（迭代）

    vector<int> dfsIterative(int start) const {

        if (start < 0 || start >= vertexCount) {

            throw out_of_range("起始顶点索引越界");

        }

        

        vector<bool> visited(vertexCount, false);

        vector<int> traversal;

        stack<int> s;

        

        s.push(start);

        

        while (!s.empty()) {

            int current = s.top();

            s.pop();

            

            if (!visited[current]) {

                visited[current] = true;

                traversal.push_back(current);

                

                // 将邻居逆序压栈，保持遍历顺序

                vector<int> neighbors = getNeighbors(current);

                for (auto it = neighbors.rbegin(); it != neighbors.rend(); ++it) {

                    if (!visited[*it]) {

                        s.push(*it);

                    }

                }

            }

        }

        

        return traversal;

    }

    

private:

    // DFS辅助函数（递归）

    void dfsHelper(int v, vector<bool>& visited, vector<int>& traversal) const {

        visited[v] = true;

        traversal.push_back(v);

        

        AdjListNode* current = heads[v];

        while (current != nullptr) {

            int neighbor = current->dest;

            if (!visited[neighbor]) {

                dfsHelper(neighbor, visited, traversal);

            }

            current = current->next;

        }

    }

};

// 邻接表示例

void adjacencyListDemo() {

    // 创建有5个顶点的无向无权图

    AdjacencyList graph(5, false, false);

    

    // 添加边

    graph.addEdge(0, 1);

    graph.addEdge(0, 4);

    graph.addEdge(1, 2);

    graph.addEdge(1, 3);

    graph.addEdge(1, 4);

    graph.addEdge(2, 3);

    graph.addEdge(3, 4);

    

    // 打印邻接表

    graph.printList();

    

    // BFS遍历

    vector<int> bfsResult = graph.bfs(0);

    cout << "从顶点0开始的BFS: ";

    for (int v : bfsResult) {

        cout << v << " ";

    }

    cout << endl;

    

    // DFS遍历

    vector<int> dfsResult = graph.dfsRecursive(0);

    cout << "从顶点0开始的DFS（递归）: ";

    for (int v : dfsResult) {

        cout << v << " ";

    }

    cout << endl;

    

    // 创建带权有向图

    AdjacencyList weightedGraph(4, true, true);

    

    weightedGraph.addEdge(0, 1, 5);

    weightedGraph.addEdge(0, 3, 10);

    weightedGraph.addEdge(1, 2, 3);

    weightedGraph.addEdge(2, 3, 1);

    

    weightedGraph.printList();

   qm.daojubao.com>wap.daojubao.com>rw.daojubao.com>

}

```

## 邻接矩阵与邻接表的比较分析

两种表示方法各有优劣，适用于不同场景：

```cpp

class GraphComparison {

public:

    // 时间复杂度比较

    struct TimeComplexity {

        // 邻接矩阵

        struct Matrix {

            bool hasEdge(int u, int v) { return O(1); }

            int getWeight(int u, int v) { return O(1); }

            vector<int> getNeighbors(int v) { return O(V); }

            int addEdge(int u, int v) { return O(1); }

            int removeEdge(int u, int v) { return O(1); }

        };

        

        // 邻接表

        struct List {

            bool hasEdge(int u, int v) { return O(degree(u)); }

            int getWeight(int u, int v) { return O(degree(u)); }

            vector<int> getNeighbors(int v) { return O(degree(v)); }

            int addEdge(int u, int v) { return O(1); }

            int removeEdge(int u, int v) { return O(degree(u) + degree(v)); }

        };

    };

    

    // 空间复杂度比较

    static void spaceAnalysis(int V, int E) {

        int matrixSpace = V * V * sizeof(int);  // 邻接矩阵

        int listSpace = (E * 2) * sizeof(AdjListNode);  // 邻接表（无向图）

        

        cout << "顶点数 V = " << V << ", 边数 E = " << E << endl;

        cout << "邻接矩阵空间: " << matrixSpace / 1024 << " KB" << endl;

        cout << "邻接表空间: " << listSpace / 1024 << " KB" << endl;

        

        // 稀疏图标准：E << V^2

        bool isSparse = E < V * V / 10;

        cout << "图类型: " << (isSparse ? "稀疏图" : "稠密图") << endl;

        cout << "推荐表示: " << (isSparse ? "邻接表" : "邻接矩阵") << endl;

    }

    

    // 选择指南

    static string getRecommendation(int V, int E, const string& operation) {

        double density = static_cast<double>(E) / (V * V);

        

        if (density < 0.1) {

            // 稀疏图通常使用邻接表

            return "推荐使用邻接表：空间效率高，添加边快";

        } else if (density > 0.5) {

            // 稠密图可以使用邻接矩阵

            return "推荐使用邻接矩阵：边存在性检查快";

        }

        

        // 根据操作类型选择

        if (operation == "frequent_edge_check") {

            return "频繁检查边存在性：推荐邻接矩阵(O(1))";

        } else if (operation == "frequent_neighbor_iteration") {

            return "频繁遍历邻居：推荐邻接表(O(degree(v)))";

        } else if (operation == "dynamic_graph") {

            return "动态图（频繁添加删除）：推荐邻接表";

        }

        

        return "默认推荐邻接表（适用于大多数场景）";

    }

};

// 性能测试函数

void performanceComparison() {

    int V = 1000;  // 1000个顶点

    

    // 测试稀疏图

    cout << "=== 稀疏图测试 (E = V) ===\n";

    GraphComparison::spaceAnalysis(V, V);

    

    // 测试稠密图

    cout << "\n=== 稠密图测试 (E = V^2) ===\n";

    GraphComparison::spaceAnalysis(V, V * V);

}

```

## 实际应用案例：社交网络图

```cpp

class SocialNetwork {

private:

    AdjacencyList graph;

    unordered_map<int, string> userIdToName;

    unordered_map<string, int> userNameToId;

    int nextId = 0;

    

public:

    SocialNetwork(int maxUsers = 10000) : graph(maxUsers, false, false) {}

    

    // 添加用户

    int addUser(const string& name) {

        if (userNameToId.find(name) != userNameToId.end()) {

            return userNameToId[name];

        }

        

        int userId = nextId++;

        userIdToName[userId] = name;

        userNameToId[name] = userId;

        return userId;

    }

    

    // 添加朋友关系

    void addFriendship(const string& name1, const string& name2) {

        int id1 = addUser(name1);

        int id2 = addUser(name2);

        

        graph.addEdge(id1, id2);

        cout << name1 << " 和 " << name2 << " 成为朋友\n";

    }

    

    // 获取朋友列表

    vector<string> getFriends(const string& name) {

        if (userNameToId.find(name) == userNameToId.end()) {

            return {};

        }

        

        int userId = userNameToId[name];

        vector<int> friendIds = graph.getNeighbors(userId);

        

        vector<string> friends;

        for (int id : friendIds) {

            friends.push_back(userIdToName[id]);

        }

        return friends;

    }

    

    // 计算共同朋友

    vector<string> getMutualFriends(const string& name1, const string& name2) {

        vector<string> friends1 = getFriends(name1);

        vector<string> friends2 = getFriends(name2);

        

        // 排序以便求交集

        sort(friends1.begin(), friends1.end());

        sort(friends2.begin(), friends2.end());

        

        vector<string> mutualFriends;

        set_intersection(friends1.begin(), friends1.end(),

                        friends2.begin(), friends2.end(),

                        back_inserter(mutualFriends));

        

        return mutualFriends;

    }

    

    // 计算最短路径（BFS）

    vector<string> shortestPath(const string& from, const string& to) {

        if (userNameToId.find(from) == userNameToId.end() ||

            userNameToId.find(to) == userNameToId.end()) {

            return {};

        }

        

        int startId = userNameToId[from];

        int targetId = userNameToId[to];

        

        // BFS记录路径

        vector<bool> visited(graph.getVertexCount(), false);

        vector<int> parent(graph.getVertexCount(), -1);

        queue<int> q;

        

        visited[startId] = true;

        q.push(startId);

        

        while (!q.empty()) {

            int current = q.front();

            q.pop();

            

            if (current == targetId) {

                // 重建路径

                vector<string> path;

                for (int v = targetId; v != -1; v = parent[v]) {

                    path.push_back(userIdToName[v]);

                }

                reverse(path.begin(), path.end());

                return path;

            }

            

            vector<int> neighbors = graph.getNeighbors(current);

            for (int neighbor : neighbors) {

                if (!visited[neighbor]) {

                    visited[neighbor] = true;

                    parent[neighbor] = current;

                    q.push(neighbor);

                }

            }

        }

        

        return {};  // 没有路径

    }

};

// 社交网络示例

void socialNetworkDemo() {

    SocialNetwork sn;

    

    // 添加朋友关系

    sn.addFriendship("Alice", "Bob");

    sn.addFriendship("Alice", "Charlie");

    sn.addFriendship("Bob", "David");

    sn.addFriendship("Charlie", "David");

    sn.addFriendship("David", "Eve");

    

    // 查询朋友

    cout << "\nAlice的朋友: ";

    vector<string> friends = sn.getFriends("Alice");

    for (const string& f : friends) {

        cout << f << " ";

    }

    cout << endl;

    

    // 计算共同朋友

    cout << "\nAlice和David的共同朋友: ";

    vector<string> mutual = sn.getMutualFriends("Alice", "David");

    for (const string& f : mutual) {

        cout << f << " ";

    }

    cout << endl;

    

    // 最短路径

    cout << "\n从Alice到Eve的最短路径: ";

    vector<string> path = sn.shortestPath("Alice", "Eve");

    for (const string& p : path) {

        cout << p << " ";

    }

    cout << endl;

}

```

## 总结：选择合适的图表示方法

图论在计算机科学中应用广泛，从社交网络到路由算法，从编译器优化到机器学习。掌握邻接矩阵和邻接表的实现原理，理解它们的适用场景和性能特征，是进行图算法开发的基础。

关键选择标准：

1. **空间效率**：稀疏图用邻接表，稠密图可考虑邻接矩阵

2. **操作频率**：频繁检查边存在性用矩阵，频繁遍历邻居用邻接表

3. **动态性**：频繁添加删除边用邻接表

4. **算法需求**：某些算法（如Floyd-Warshall）天然适合邻接矩阵

通过本文的完整实现和对比分析，读者可以建立对图表示方法的全面理解，为后续学习更复杂的图算法（如Dijkstra、Prim、拓扑排序等）打下坚实基础。