当前位置：首页 > C++目录 > 正文内容

图的访问与存储—临接表

亿万年的星光3个月前 (11-22)C++目录328
        在图论中，邻接表（Adjacency List） 是表示图（包括无向图、有向图、带权图）的一种高效数据结构，核心思想是为图中的每个顶点维护一个 “邻居列表”，记录该顶点直接相连的所有顶点（及边的权重，若为带权图）。
相比于邻接矩阵（用二维数组存储顶点间的连接关系），邻接表在稀疏图（边数远少于顶点数的平方） 中更节省空间，也是工程中最常用的图存储方式之一。

一、基本结构

邻接表的核心是 “数组 + 链表 / 动态数组” 的组合：

  1. 顶点数组：数组的下标对应图的顶点编号（或用哈希表映射顶点标识），数组的每个元素指向该顶点的 “邻居列表”；

  2. 邻居列表：每个顶点对应的列表，存储与该顶点直接相连的顶点（带权图还需存储边的权重）。

二、临接表示例


1.无向图的邻接表

如果上面的图用临接矩阵表示，那么便是一个4*4的矩阵

顶点0123
00110
11010
21101
30010

如果是临接表，那么可以看出一共有4个顶点0、1、2、3

每个顶点都有“邻居”（邻居数组）。

比如顶点0，它的邻居数组是[1,2]

顶点1,它的邻居数组是[0,2]

顶点2,它的邻居数组是[0,1,3]

顶点3,它的邻居数组是[2]

表示成下面这样：

0 → [1, 2]
1 → [0, 2] 
2 → [0, 1, 3]
3 → [2]


参考代码：

#include <iostream>
#include <vector>
using namespace std;
// 创建无向图的邻接表
vector<vector<int> > createUndirectedGraph(int numVertices) {
    return vector<vector<int> >(numVertices);
}
// 添加无向边
void addUndirectedEdge(vector<vector<int> >& graph, int u, int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
}
// 打印邻接表 
void printGraph(const vector<vector<int> >& graph) {
    cout << "无向图邻接表:" << endl;
    for (int i = 0; i < graph.size(); i++) {
        cout << "顶点 " << i << " -> ";
        // 循环遍历邻居
        for (int j = 0; j < graph[i].size(); j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
}

// 计算每个顶点的度
vector<int> calculateDegrees(const vector<vector<int> >& graph) {
    vector<int> degrees(graph.size(), 0);
    for (int i = 0; i < graph.size(); i++) {
        degrees[i] = graph[i].size();
    }
    return degrees;
}

// 检查两个顶点之间是否有边 - 使用传统for循环
bool hasEdge(const vector<vector<int> >& graph, int u, int v) {
    for (int j = 0; j < graph[u].size(); j++) {
        if (graph[u][j] == v) {
            return true;
        }
    }
    return false;
}
// 删除无向边 
void removeUndirectedEdge(vector<vector<int> >& graph, int u, int v) {
    // 删除 u->v 的边
    for (int j = 0; j < graph[u].size(); j++) {
        if (graph[u][j] == v) {
            graph[u].erase(graph[u].begin() + j);
            break;
        }
    }
    
    // 删除 v->u 的边
    for (int j = 0; j < graph[v].size(); j++) {
        if (graph[v][j] == u) {
            graph[v].erase(graph[v].begin() + j);
            break;
        }
    }
}
int main() {
    // 创建无向图
    vector<vector<int> > graph = createUndirectedGraph(6);
    // 添加边
    addUndirectedEdge(graph, 0, 1);
    addUndirectedEdge(graph, 0, 2);
    addUndirectedEdge(graph, 1, 3);
    addUndirectedEdge(graph, 1, 4);
    addUndirectedEdge(graph, 2, 4);
    addUndirectedEdge(graph, 3, 5);
    // 打印图
    printGraph(graph);
    cout << endl;
    // 计算顶点度
    vector<int> degrees = calculateDegrees(graph);
    for (int i = 0; i < degrees.size(); i++) {
        cout << "顶点 " << i << " 的度: " << degrees[i] << endl;
    }
    cout << endl;
    // 检查边
    cout << "检查边 0-1: " << (hasEdge(graph, 0, 1) ? "存在" : "不存在") << endl;
    cout << "检查边 0-3: " << (hasEdge(graph, 0, 3) ? "存在" : "不存在") << endl;
    cout << endl;
    // 删除边
    cout << "删除边 0-1 后:" << endl;
    removeUndirectedEdge(graph, 0, 1);
    printGraph(graph);
    return 0;
}



2.有向图的临接表

对于上面这个有向图，如果用临接矩阵表示，是一个4*4的临接矩阵，如下所示

顶点0123
00110
10010
20001
30000

如果是临接表，那么有4个顶点0，1，2，3

对于顶点0来说，它的邻居数组是[1,2]

对于顶点1来说，它的邻居数组是[2]

对于顶点2来说，它的邻居数组是[3]

对于顶点3来说，它的邻居数组是[]

表示成下面

顶点0: [1, 2]  // 0指向1、2
顶点1: [2]     // 1指向2
顶点2: [3]     // 2指向3
顶点3: []      // 3无出边


参考代码

#include <iostream>
#include <vector>
using namespace std;
// 创建有向图的邻接表
vector<vector<int> > createDirectedGraph(int numVertices) {
    return vector<vector<int> >(numVertices);
}
// 添加有向边
void addDirectedEdge(vector<vector<int> >& graph, int from, int to) {
    graph[from].push_back(to);
}
// 打印邻接表 
void printGraph(const vector<vector<int> >& graph) {
    cout << "有向图邻接表:" << endl;
    for (int i = 0; i < graph.size(); i++) {
        cout << "顶点 " << i << " -> ";
        // for循环遍历出边
        for (int j = 0; j < graph[i].size(); j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }
}

// 计算每个顶点的出度
vector<int> calculateOutDegrees(const vector<vector<int> >& graph) {
    vector<int> outDegrees(graph.size(), 0);
    for (int i = 0; i < graph.size(); i++) {
        outDegrees[i] = graph[i].size();
    }
    return outDegrees;
}

// 计算每个顶点的入度
vector<int> calculateInDegrees(const vector<vector<int> >& graph) {
    vector<int> inDegrees(graph.size(), 0);
    for (int i = 0; i < graph.size(); i++) {
        for (int j = 0; j < graph[i].size(); j++) {
            int target = graph[i][j];
            inDegrees[target]++;
        }
    }
    return inDegrees;
}

// 检查是否有从u到v的有向边 - 使用传统for循环
bool hasDirectedEdge(const vector<vector<int> >& graph, int from, int to) {
    for (int j = 0; j < graph[from].size(); j++) {
        if (graph[from][j] == to) {
            return true;
        }
    }
    return false;
}

// 删除有向边 - 使用传统for循环
void removeDirectedEdge(vector<vector<int> >& graph, int from, int to) {
    for (int j = 0; j < graph[from].size(); j++) {
        if (graph[from][j] == to) {
            graph[from].erase(graph[from].begin() + j);
            break;
        }
    }
}


int main() {
    // 创建有向图
    vector<vector<int> > graph = createDirectedGraph(6);
    
    // 添加有向边
    addDirectedEdge(graph, 0, 1);
    addDirectedEdge(graph, 0, 2);
    addDirectedEdge(graph, 1, 3);
    addDirectedEdge(graph, 2, 1);
    addDirectedEdge(graph, 2, 4);
    addDirectedEdge(graph, 3, 5);
    addDirectedEdge(graph, 4, 3);
    addDirectedEdge(graph, 4, 5);
    
    // 打印图
    printGraph(graph);
    cout << endl;
    
    // 计算出度和入度
    vector<int> outDegrees = calculateOutDegrees(graph);
    vector<int> inDegrees = calculateInDegrees(graph);
    
    for (int i = 0; i < graph.size(); i++) {
        cout << "顶点 " << i << " - 出度: " << outDegrees[i] 
             << ", 入度: " << inDegrees[i] << endl;
    }
    cout << endl;
    
    // 检查有向边
    cout << "检查边 0->1: " << (hasDirectedEdge(graph, 0, 1) ? "存在" : "不存在") << endl;
    cout << "检查边 1->0: " << (hasDirectedEdge(graph, 1, 0) ? "存在" : "不存在") << endl;
    cout << "检查边 2->4: " << (hasDirectedEdge(graph, 2, 4) ? "存在" : "不存在") << endl;
    cout << endl; 
    // 删除边
    cout << "删除边 0->2 后:" << endl;
    removeDirectedEdge(graph, 0, 2);
    printGraph(graph);
    
    return 0;
}



3.带权图的邻接表

邻接表需存储 “邻居顶点 + 权重”（通常用二元组 / 结构体）：

对于这个带权图，如果是临接矩阵，那么是4*4的临接矩阵，表示成下面这样

顶点0123
00530
10000
20007
30000

如果是临接表进行表示，

顶点0: [(1,5), (2,3)]
顶点1: []
顶点2: [(3,7)]
顶点3: []


带有权重的图可以使用pair来表示

适用于有向、带权重的场景（如路径长度、费用），用 pair<int, int> 存储「邻居顶点 + 权重」（第一个元素 = 邻居，第二个 = 权重）。


参考答案：

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
//添加带权边 
void addEdgeToGraph(vector<vector<pair<int, int>>>& adj, int u, int v, int weight) {
    adj[u].push_back(pair<int, int>(v, weight));
}
//打印 
void printGraph(vector<vector<pair<int, int>>>& adj) {
    for (int i = 0; i < adj.size(); ++i) {
        cout << "顶点 " << i << " 指向：";
        vector<pair<int, int>> edges = adj[i];
        for (int j = 0; j < edges.size(); ++j) {
            int neighbor = edges[j].first;
            int weight = edges[j].second;
            cout << "(" << neighbor << ", 权重" << weight << ") ";
        }
        cout << endl;
    }
}
int main() {
    // 4个顶点 二维向量 
    vector<vector<pair<int, int>>> graphAdj(4); 
    // 添加边（此时graphAdj已有0-3共4个顶点，访问合法）
    addEdgeToGraph(graphAdj, 0, 1, 13); //加入边和权重 
    addEdgeToGraph(graphAdj, 0, 2, 14);
    addEdgeToGraph(graphAdj, 1, 2, 15);
    addEdgeToGraph(graphAdj, 2, 3, 16);
    addEdgeToGraph(graphAdj, 3, 1, 17);
    cout << "=== 有向带权图===" << endl;
    printGraph(graphAdj);
    cout << endl;
    return 0;
}


    扫描二维码推送至手机访问。

    版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。

    分享给朋友：
    返回列表

    上一篇：图的访问与遍历-深度优先搜索

    下一篇：DEVC++如何支持C++11

    相关文章

    C++ 中的常量

    C++ 中的常量

    一、说明常量和变量是相对的概念 —— 变量是 “能变化的量”，而常量就是一旦定义就固定不变、不能修改的值。用生活里的例子类比，你就能秒懂为什么需要常量：本质是 “给固定不变的东西贴‘只读标签’，避免误...

    【数论】龟速乘

    【数论】龟速乘

    我们前面一篇文章学习了快速幂。它可以解决两类问题：a^b，(a^b)%c对于第一类，我们可以使用递归法或者迭代法可以求出，为了计算的快，我们可以引入位运算操作，但是目前来看，无论怎么优化都不能超过lo...

    质数（素数）的判断

    一、定义法// 1 定义法（除了1和他本身之外，没有任何一个数能被整除）（试除法） bool is_prime3(unsigned long lon...

    【题解】均分纸牌

    【题目描述】有n堆纸牌，编号分别为 1，2，…, n。每堆上有若干张，但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1的堆上取的纸牌，只能移到编号为 2 的堆上；在...

    【数据结构】优先队列（1）

    优先队列（Priority Queue）是一种特殊的队列，它 不遵循“先进先出”（FIFO） 的原则，而是 按照优先级（Priority） 来出队。优先级高的元素 先出队，优先级低的元素 后出队。1....

    【STL】二分查找函数(算法)—binary_search

    【说明】binary_search() 实现了一个二分查找算法。它会在前两个参数指定范围内搜索等同于第三个参数的元素。指定范围的迭代器必须是正向迭代器而且元素必须可以使用 < 运算符来比较。这个...

    鲁ICP备20008475号

    Powered By Z-BlogPHP. Theme by TOYEAN.