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

图的访问与存储—临接表

亿万年的星光2个月前 (11-22)C++目录223
        在图论中，邻接表（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++语言中最常见的漏洞。最常见的溢出包括数组溢出、数溢出、缓冲区溢出、指针溢出以及栈溢出。二、数组溢出    ...

c++ 如何用链表存取数据

c++ 如何用链表存取数据

由于单链表的每个结点都有一个数据域和一个指针域。所以，每个结点可以定义成一个记录。其中，DATA数据元素，可以为你想要储存的任何数据格式，可以是数组，可以是int，甚至可以是结构体（这就是传说中的结构...

CSP-J2021年普及组复赛T2——插入排序

CSP-J2021年普及组复赛T2——插入排序

【题目描述】插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老 师刚刚在上课的时候讲了插入排序算法。 假设比较两个元素的时间为 O(1)，则插入排序可以以 O(n 2...

C++读取磁盘文件

0.前言简单介绍一下C++读取文件的基本操作。关键技术：freopen() 文件的打开函数 FILE *fp fp=fopen(文件名,使用文件方式) 例如： fp...

2021CSP-J/S全国晋级二轮分数线公布

普及组CSP-J序号省市CSP-J人数CSP-J晋级晋级比例最高分晋级最低分1甘肃13413399.25%86152宁夏10310198.06%65243天津46345197.41%8615.54云南...

unsigned

在一些代码中，经常能看到unsigned这种数据类型，比如下面这样的。#include<iostream> using namespace std; int&nbs...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.