首页 > 其他分享 >【CS.DS】数据结构 —— 图结构：图的三种表示方法之邻接表(Adjacency List)

【CS.DS】数据结构 —— 图结构：图的三种表示方法之邻接表(Adjacency List)

时间：2024-06-20 18:27:50浏览次数：23  
标签：weight int Adjacency List vertices 邻接 CS 顶点 AddEdge

文章目录

数据结构
在这里插入图片描述

1 概念

  • 优点：空间效率高，适合稀疏图。动态性强，可以方便地添加或删除边。

    • 邻接表表示法是一种高效表示稀疏图的方式。//

  • 缺点：查找某条边是否存在的时间复杂度较高。

  • 示例：

A: B -> D
B: A -> C -> D
C: B
D: A -> B
  • 示例解释：顶点 A 连接到 B 和 D，顶点 B 连接到 A、C 和 D，以此类推。

2 无向图的邻接表

2.1 示例

假设有以下无向图，其中节点 A、B、C、D、E 表示城市，边表示城市之间的道路，权重表示道路的距离。

在邻接表（链式）表示法中，图的边权重是预先给定的，而不是通过某种计算得到的。它们通常是图的定义的一部分，表示从一个顶点到另一个顶点的距离、时间或其他成本。例如，在地图中的路径权重可以表示两个地点之间的距离。

    A----3----B
    |         |
    4         2
    |         |
    C----1----D
    |     
    5     
    |
    E

对应的邻接表为：

A -> B(3) -> C(4)
B -> A(3) -> D(2)
C -> A(4) -> D(1) -> E(5)
D -> B(2) -> C(1)
E -> C(5)

2.2 Mermaid 图示例

表节点链表 顶点 3 3 4 2 5 4 2 1 5 1 ^ C ^ D ^ E D ^ C ^ B A A B A C B D C E

e.g. 顶点 A 的邻接表：

  • 顶点 A 连接到顶点 B，边的权重是 3。
  • 顶点 A 再连接到顶点 C，边的权重是 4。
  • 最后一个节点指向 ^ 表示链表结束。

2.3 C++实现

2.3.1 简单实现
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 表示图的结构: `Edge` 结构体表示图的边，包括目的顶点 `dest`、边的权重 `weight` 和指向下一条边的指针 `next`。
struct Edge {
    int dest;   // 目的顶点
    int weight; // 边的权重
    Edge* next; // 指向下一条边的指针
};

// `Vertex` 结构体表示图的顶点，包括顶点数据 `data` 和指向第一个相邻顶点的指针 `first`。
struct Vertex {
    char data;    // 顶点数据
    Edge* first; // 指向第一个相邻顶点的指针
};

// 初始化图: `addEdge` 函数用于向图中添加边，每次添加新边时，会将其插入到链表的头部。
void addEdge(Vertex vertices[], int src, int dest, int weight) {
    Edge* newEdge = new Edge{dest, weight, vertices[src].first};
    vertices[src].first = newEdge;
}

void printGraph(Vertex vertices[], int V) {
    for (int i = 0; i < V; ++i) {
        cout << "顶点 " << vertices[i].data << " 的邻接表: ";
        Edge* edge = vertices[i].first;
        while (edge) {
            cout << " -> " << vertices[edge->dest].data << " (权重 " << edge->weight << ")";
            edge = edge->next;
        }
        cout << endl;
    }
}

int main() {
    const int V = 5;
    Vertex vertices[V] = {{'A', nullptr}, {'B', nullptr}, {'C', nullptr}, {'D', nullptr}, {'E', nullptr}};

    // 根据图添加边
    addEdge(vertices, 0, 1, 3); // A -> B
    addEdge(vertices, 0, 2, 4); // A -> C
    
    addEdge(vertices, 1, 0, 3); // B -> A
    addEdge(vertices, 1, 3, 2); // B -> D

    addEdge(vertices, 2, 0, 4); // C -> A
    addEdge(vertices, 2, 3, 1); // C -> D
    addEdge(vertices, 2, 4, 5); // C -> E

    addEdge(vertices, 3, 1, 2); // D -> B
    addEdge(vertices, 3, 2, 1); // D -> C

    addEdge(vertices, 4, 2, 5); // E -> C

    printGraph(vertices, V);

    return 0;
}

封装实现:
优点：

  • 直接性：直接使用链表来表示邻接表，比较直观。
  • 高效性：链表的插入操作比较高效。
    缺点：
  • 复杂性：需要手动管理内存，容易出现内存泄漏问题。
  • 灵活性：不如 STL 容器灵活，操作起来相对繁琐。
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

struct Edge {
    int dest;
    int weight;
    Edge* next;
};

struct Vertex {
    char data;
    Edge* first;
};

class Graph {
public:
	// 构造函数，初始化顶点数量和顶点数组
    Graph(int vertices) : V(vertices) {
        vertex_list = new Vertex[V];
        for (int i = 0; i < V; ++i) {
            vertex_list[i].data = 'A' + i;
            vertex_list[i].first = nullptr;
        }
    }
	// 析构函数，释放所有动态分配的内存
    ~Graph() {
        for (int i = 0; i < V; ++i) {
            Edge* current = vertex_list[i].first;
            while (current) {
                Edge* temp = current;
                current = current->next;
                delete temp;
            }
        }
        delete[] vertex_list;
    }

    void AddEdge(int src, int dest, int weight) {
        Edge* newEdge = new Edge{dest, weight, vertex_list[src].first};
        vertex_list[src].first = newEdge;
    }

    void PrintGraph() const {
        for (int i = 0; i < V; ++i) {
            cout << "顶点 " << vertex_list[i].data << " 的邻接表: ";
            Edge* edge = vertex_list[i].first;
            while (edge) {
                cout << " -> " << vertex_list[edge->dest].data << " (权重 " << edge->weight << ")";
                edge = edge->next;
            }
            cout << endl;
        }
    }

private:
    int V;
    Vertex* vertex_list;
};

int main() {
    Graph g(5);

    // 根据图添加边  
    g.AddEdge(0, 1, 3); // A -> B  
    g.AddEdge(0, 2, 4); // A -> C  
  
    g.AddEdge(1, 0, 3); // B -> A  
    g.AddEdge(1, 3, 2); // B -> D  
  
    g.AddEdge(2, 0, 4); // C -> A  
    g.AddEdge(2, 3, 1); // C -> D  
    g.AddEdge(2, 4, 5); // C -> E  
  
    g.AddEdge(3, 1, 2); // D -> B  
    g.AddEdge(3, 2, 1); // D -> C  
  
    g.AddEdge(4, 2, 5); // E -> C  

    g.PrintGraph();

    return 0;
}

执行后, 输出如下:

顶点 A 的邻接表:  -> C (权重 4) -> B (权重 3) # 对于顶点 `A` 的邻接表：A -> C(4) -> B(3) 或者 A -> B(3) -> C(4) 都是正确的，它们表示的图结构是一样的。关键在于每个顶点的邻接节点及其对应的边权重是否正确记录。
顶点 B 的邻接表:  -> D (权重 2) -> A (权重 3)
顶点 C 的邻接表:  -> E (权重 5) -> D (权重 1) -> A (权重 4)
顶点 D 的邻接表:  -> C (权重 1) -> B (权重 2)
顶点 E 的邻接表:  -> C (权重 5)
2.3.2 优化封装

优点：

  • 简洁性：代码更简洁，易于阅读和维护。
  • 内存管理：使用 STL 容器，不需要手动管理内存，减少内存泄漏风险。
  • 灵活性：STL 容器操作更灵活，提供了更多的功能。
    缺点：
  • 抽象程度：链表的表示方式被隐藏在 STL 容器中，可能不够直观。
#include <iostream>
#include <vector>

class Graph {
public:
    Graph(int vertices)
        : vertices_(vertices) {
        adj_list_.resize(vertices_);
    }

    void AddEdge(int u, int v, int weight) {
        adj_list_[u].emplace_back(v, weight);
        adj_list_[v].emplace_back(u, weight); // 对于无向图，需要双向添加边
    }

    void PrintAdjList() const {
        for (int v = 0; v < vertices_; ++v) {
            std::cout << static_cast<char>('A' + v) << ": ";
            for (const auto& edge : adj_list_[v]) {
                std::cout << static_cast<char>('A' + edge.first) << " (权重 " << edge.second << ") ";
            }
            std::cout << std::endl;
        }
    }

private:
    int vertices_;
    std::vector<std::vector<std::pair<int, int>>> adj_list_;
};

int main() {
    Graph g(5);

    // 根据图添加边
    g.AddEdge(0, 1, 3); // A -> B
    g.AddEdge(0, 2, 4); // A -> C
    g.AddEdge(1, 3, 2); // B -> D
    g.AddEdge(1, 4, 2); // B -> E
    g.AddEdge(2, 3, 1); // C -> D
    g.AddEdge(3, 4, 5); // D -> E

    g.PrintAdjList();

    return 0;
}

2.4 总结

在邻接表表示法中，链表中顶点的顺序实际上是不重要的。邻接表的主要目的是表示每个顶点的邻接关系以及对应的边权重，因此，顶点的顺序并不会影响图的表示和算法的正确性。

总体来看，第二种封装方式更符合现代 C++ 编程规范，更加推荐。主要原因如下：

  1. 简洁性和可维护性：使用 STL 容器使代码更简洁，易于维护和扩展。
  2. 内存管理：STL 容器自动管理内存，减少内存泄漏的风险。
  3. 灵活性：STL 容器提供了丰富的操作接口，使用更加灵活。

当然, 如果你需要对图进行非常细粒度的控制，或者在非常严格的性能要求下，第一种封装方式可能更适合。

3 有向图的邻接表

假设有以下有向图，其中节点 A、B、C、D、E 表示城市，边表示城市之间的道路，权重表示道路的距离。

3.1 示例

    A----3---->B
    |         |
    4         2
    |         |
    v         v
    C<----1----D
    |     
    5     
    |
    v 
    E

对应的邻接表为：

A -> B(3) -> C(4)
B -> D(2)
C -> E(5)
D -> C(1)
E ->

3.2 C++实现

#include <iostream>
#include <vector>

class Graph {
public:
    Graph(int vertices)
        : vertices_(vertices) {
        adj_list_.resize(vertices_);
    }

    void AddEdge(int u, int v, int weight) {
        adj_list_[u].emplace_back(v, weight);
    }

	/*
	// 对比无向图的, 向图中添加边:
	void AddEdge(int u, int v, int weight) {
        adj_list_[u].emplace_back(v, weight);
        adj_list_[v].emplace_back(u, weight); // 对于无向图，需要双向添加边
    }
	*/

    void PrintAdjList() const {
        for (int v = 0; v < vertices_; ++v) {
            std::cout << static_cast<char>('A' + v) << ": ";
            for (const auto& edge : adj_list_[v]) {
                std::cout << static_cast<char>('A' + edge.first) << " (权重 " << edge.second << ") ";
            }
            std::cout << std::endl;
        }
    }

private:
    int vertices_;
    std::vector<std::vector<std::pair<int, int>>> adj_list_;
};

int main() {
    Graph g(5);

    g.AddEdge(0, 1, 3); // A -> B
    g.AddEdge(0, 2, 4); // A -> C
    g.AddEdge(1, 3, 2); // B -> D
    g.AddEdge(3, 2, 1); // D -> C
    g.AddEdge(2, 4, 5); // C -> E

    g.PrintAdjList();

    return 0;
}

3.3 总结

有向图表示的邻接表结构和无向图类似，只是边的方向性需要注意。

4 邻接图的遍历

// **图的遍历（DFS 和 BFS）**
#include <iostream>
#include <vector>
#include <stack>
#include <queue>

class Graph {
public:
    Graph(int vertices)
        : vertices_(vertices) {
        adj_list_.resize(vertices_);
    }

    void AddEdge(int u, int v, int weight) {
        adj_list_[u].emplace_back(v, weight);
    }

    void DFS(int start) {
        std::vector<bool> visited(vertices_, false);
        std::stack<int> stack;
        stack.push(start);

        while (!stack.empty()) {
            int v = stack.top();
            stack.pop();

            if (!visited[v]) {
                std::cout << static_cast<char>('A' + v) << " ";
                visited[v] = true;
            }

            for (const auto& edge : adj_list_[v]) {
                if (!visited[edge.first]) {
                    stack.push(edge.first);
                }
            }
        }
        std::cout << std::endl;
    }

    void BFS(int start) {
        std::vector<bool> visited(vertices_, false);
        std::queue<int> queue;
        queue.push(start);
        visited[start] = true;

        while (!queue.empty()) {
            int v = queue.front();
            queue.pop();
            std::cout << static_cast<char>('A' + v) << " ";

            for (const auto& edge : adj_list_[v]) {
                if (!visited[edge.first]) {
                    queue.push(edge.first);
                    visited[edge.first] = true;
                }
            }
        }
        std::cout << std::endl;
    }

    void PrintAdjList() const {
        for (int v = 0; v < vertices_; ++v) {
            std::cout << static_cast<char>('A' + v) << ": ";
            for (const auto& edge : adj_list_[v]) {
                std::cout << static_cast<char>('A' + edge.first) << " (权重 " << edge.second << ") ";
            }
            std::cout << std::endl;
        }
    }

private:
    int vertices_;
    std::vector<std::vector<std::pair<int, int>>> adj_list_;
};

int main() {
    Graph g(5);

    g.AddEdge(0, 1, 3); // A -> B
    g.AddEdge(0, 2, 4); // A -> C
    g.AddEdge(1, 3, 2); // B -> D
    g.AddEdge(3, 2, 1); // D -> C
    g.AddEdge(2, 4, 5); // C -> E

    std::cout << "邻接表:" << std::endl;
    g.PrintAdjList();

    std::cout << "DFS 从 A 开始:" << std::endl;
    g.DFS(0);

    std::cout << "BFS 从 A 开始:" << std::endl;
    g.BFS(0);

    return 0;
}

5 拓展补充

  • 时间复杂度分析：
    • 添加边：O(1) - 在邻接表中添加一条边的时间复杂度为常数时间，因为只需将新边添加到链表头部。
    • 删除边：O(E) - 删除一条边可能需要遍历整个链表，时间复杂度为 O(E)，其中 E 是链表的长度。
    • 查找邻接点：O(V) - 查找某个顶点的所有邻接点的时间复杂度为 O(V)，其中 V 是顶点的数量。
    • 查找某条边：O(E) - 查找某条边是否存在的时间复杂度为 O(E)，其中 E 是链表的长度。
  • 图的遍历：
    • **深度优先搜索（DFS）和广度优先搜索（BFS）**都可以在邻接表上高效实现。时间复杂度均为 O(V + E)，其中 V 是顶点的数量，E 是边的数量。
  • 存储结构：
    • 邻接表可以使用数组、链表、向量（std::vector）、哈希表（std::unordered_map）等数据结构来实现，具体选择取决于需求和编程语言。
  • 内存消耗：
    • 相比邻接矩阵（Adjacency Matrix），邻接表在稀疏图（Sparse Graph）上更加节省内存。对于具有 V 个顶点和 E 条边的图，邻接矩阵需要 O(V^2) 的空间，而邻接表只需要 O(V + E) 的空间。
  • 变种：
    • 加权图：每条边都有权重（已在示例中展示）。
    • 有向图和无向图：有向图的每条边有方向，反映在邻接表中只在一个方向上添加边；无向图在两个顶点之间添加双向边。
    • 多重图（Multigraph）：允许在两个顶点之间存在多条边。邻接表可以通过链表或向量来支持多重图。
  • 图的表示法转换：
    • 邻接表可以轻松转换为邻接矩阵，反之亦然，但在稀疏图上邻接表更有效。
  • 动态图：
    • 对于动态变化的图（例如频繁添加或删除边），邻接表比邻接矩阵更具优势，因为添加和删除操作更高效。

References

标签：weight,int,Adjacency,List,vertices,邻接,CS,顶点,AddEdge
From： https://blog.csdn.net/Charlie_Lee_CS/article/details/139835431

相关文章

  • 关于CStringList的剖析
    CStringList是一个双向链表。它的内存管理依赖于CPlex结构。`__declspec(align(8))structCPlex{CPlex*pNext;//BYTEdata[maxNum*elementSize];void*data(){returnthis+1;}staticCPlex*PASCALCreate(CPlex*&head,UINT_PTRnMax,UINT_PTRcbElement); //......
  • ElasticSearch入门(实战)
    环境准备：VMwaredocker   创建一个linux虚拟机，使用dockerpullelasticsearch 部署单体服务： dockerpullelasticsearch:6.8.13#elasticsearch十分占用内存，用这种方式启动会导致Linux卡机dockerrun-d--nameelasticsearch-p9200:9200-p9300:9300-e"discover......
  • 2024年智慧城市、系统与交通运输国际会议（ICSCST 2024）
    2024InternationalConferenceonSmartCities,Systems,andTransportation【1】大会信息会议简称：ICSCST 2024大会地点：中国·珠海投稿邮箱：icscst@sub-paper.com 【2】会议简介2024年智慧城市、系统与交通运输国际会议即将召开，此次会议旨在汇聚全球智慧城市建设......
  • CSP历年复赛题-P9749 [CSP-J 2023] 公路
    原题链接：https://www.luogu.com.cn/problem/P9749题意解读：有n个加油点，每个加油点距离、油价不同，每升油走d公里，加油必须整升加，问走完所有点最少加油的金额。解题思路：本题有两种思考方式：1、先走，再看油从哪里加依次走到第2,3,4......n个加油点，看每两个点之间距离需要加多少油由......
  • datalist 是什么？以及作用是什么？
    datalist 是HTML5中引入的一个新元素，它允许你为 <input> 元素提供一个“预定义”的选项列表。用户可以在输入时从这些选项中选择，但也可以输入不在列表中的其他值。datalist 元素与 <input> 元素一起使用，通过 <option> 元素在 datalist 中定义可用的选项。datalist......
  • 学生个人html静态网页制作 基于HTML+CSS+JavaScript+jquery仿苏宁易购官网商城模板
    ......
  • MFC---列表框控件ListBox、组合框控件Combo Box（常用控件）
    前面两节讲了比较常用的按钮控件，并通过按钮控件实例说明了具体用法。本文要讲的是列表框控件（ListBox）及其使用实例。列表框控件简介列表框给出了一个选项清单，允许用户从中进行单项或多项选择，被选中的项会高亮显示。列表框可分为单选列表框和多选列表框，顾名思义，单选列表框中......
  • Vue - 使用 transition 过渡动画、Animate.css 库动画
     一.transitiontransition标签包裹的内容会有一个过渡的动画效果使用transition过渡组件需要满足的条件：条件渲染（v-if）条件展示（v-show）动态组件可以使用 name 属性给 transition 标签起名字class选择器名字和 name 属性有关系，这里 name 属性名为 fade,则cla......
  • 压缩列表（ziplist）
    压缩列表（ziplist）：ziplist是列表键和哈希键的底层实现之一当一个列表键只包含少量列表项，并且每个列表项要么是小整数或者短字符串，那么redis会使用ziplist来做列表键的实现当一个哈希键只包含少量键值对，且每个键值对的键和值要么是小整数或短字符串，那么redis会使用ziplist来......
  • 203. Remove Linked List Elements
    Giventheheadofalinkedlistandanintegerval,removeallthenodesofthelinkedlistthathasNode.val==val,andreturnthenewhead.Example1:Input:head=[1,2,6,3,4,5,6],val=6Output:[1,2,3,4,5]Example2:Input:head=[],val=......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99