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

图的访问与存储—临接表

亿万年的星光2个月前 (11-22)C++目录221
        在图论中，邻接表（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

相关文章

【题解】采药的最短路径

【题目描述】少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有...

图的访问与遍历-广度优先搜索

对于无向图的广度优先搜索#include <iostream> #include <vector> #include <queue>...

C++中双冒号（：：）的用法

一、作用域符号前面一般是类名称，后面一般是该类的成员名称，C++为例避免不同的类有名称相同的成员而采用作用域的方式进行区分如：A,B表示两个类，在A,B中都有成员member。那么A::member就...

DEVC++中的断点调试

DEVC++中的断点调试

1.调试程序的两种方法编程的时候经常会遇到自己的输出结果跟标准结果或者预期的结果不一样，这个时候就要用到调试程序的功能。调试程序的目的有两个，一个是找出程序中的错误，另一个是监视变量的变化。2.DEV...

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

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

【入门篇】C++ 中变量的简单使用

【入门篇】C++ 中变量的简单使用

1.什么是变量”变量“通俗来讲就是能变的量。在程序设计中，变量是一个个不同类型的盒子，当盒子里装了苹果时，盒子就代表苹果，当然，我们需要给一个个盒子起不同的名字。像下面的图片一样，一个盒子，给他取一个...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.