【数据结构】图论基础

news/2024/12/21 21:40:22/

在这里插入图片描述

文章目录

  • 图的概念
    • 图的基本概念
    • 图的类型
    • 图的表示方法
  • 图的相关基本概念
    • 1. 路径（Path）
    • 2. 连通性（Connectivity）
    • 3. 图的度（Degree）
    • 4. 子图（Subgraph）
    • 5. 生成树（Spanning Tree）
    • 6. 二分图（Bipartite Graph）
    • 7. 拓扑排序（Topological Sort）
    • 8. 欧拉图和哈密顿图
  • 实现图
    • 邻接矩阵实现图
      • 邻接矩阵的基本框架
      • 核心接口
    • 邻接表实现图
      • 邻接表实现图的基本框架
      • 核心接口
  • 总结

图的概念

图（Graph）是离散数学中的一种重要数据结构，用于描述对象（称为顶点，或节点）之间的关系（称为边）。图可以表示各种事物之间的连接关系，比如网络中的路由器、社交网络中的用户、城市之间的道路等。

图的基本概念

  1. 顶点（Vertex）：

    • 图中的基本单位，也称为节点（Node）。一个图通常由若干个顶点组成，用来表示实体或对象。

  2. 边（Edge）：

    • 顶点之间的连接关系称为边。边可以是有方向的（有向图）或无方向的（无向图）。在无向图中，边表示双向关系；在有向图中，边表示单向关系。

  3. 有向图（Directed Graph, Digraph）：

    • 在有向图中，边是有方向的，表示从一个顶点指向另一个顶点的单向连接。通常用有向边表示诸如“影响”或“依赖”的关系。
      在这里插入图片描述

  4. 无向图（Undirected Graph）：

    • 无向图中的边没有方向，表示两个顶点之间的对称关系，如“相邻”或“连接”。
      在这里插入图片描述

  5. 邻接（Adjacency）：

    • 如果两个顶点之间有一条边连接，这两个顶点称为邻接的。

  6. 度（Degree）：

    • 一个顶点的度是连接到该顶点的边的数目。在有向图中，区分入度（In-degree）和出度（Out-degree），分别表示进入该顶点和从该顶点发出的边的数量。

图的类型

  1. 稀疏图（Sparse Graph）：

    • 边的数量远远少于顶点数量的平方（E << V²），大部分顶点之间没有边连接。

  2. 稠密图（Dense Graph）：

    • 边的数量接近顶点数量的平方（E ≈ V²），大多数顶点之间有边连接。

  3. 加权图（Weighted Graph）：

    • 图中的每条边带有一个权重，用来表示顶点之间的某种度量，如距离、成本或容量。

  4. 连通图（Connected Graph）：

    • 对于无向图，若任意两个顶点之间都有路径相连，则称为连通图。有向图中则需区分强连通和弱连通。

  5. 简单图（Simple Graph）：

    • 不包含自环和多重边的图。自环是指从顶点到自身的边，多重边是指两个顶点之间存在多条边。

  6. 完全图（Complete Graph）：

    • 图中任意两个顶点之间都有边相连，通常表示为 K n K_n Kn​，其中 n n n 是顶点数。

图的表示方法

  1. 邻接矩阵（Adjacency Matrix）：

    • 使用一个二维矩阵来表示顶点之间的连接关系，矩阵中的元素表示边的存在性或权重。

  2. 邻接表（Adjacency List）：

    • 对每个顶点，维护一个链表（或数组）来存储与之相邻的顶点列表，适合稀疏图。

  3. 边集列表（Edge List）：

    • 直接列出图中所有的边，用边的起点和终点来描述，适合图的遍历或算法中的具体操作。

图的相关基本概念

在理解图的结构和操作时，有一些与图密切相关的概念有助于更好地分析和处理图的算法和应用。

1. 路径（Path）

路径是在图中从一个顶点到另一个顶点的行进序列，它由一系列边和顶点组成。根据图的类型和要求，路径可以分为几类：

  • 简单路径（Simple Path）：路径中的顶点不重复出现。
  • 回路（Cycle）：路径的起点和终点是同一个顶点，且路径中的其他顶点不重复。
    在这里插入图片描述

2. 连通性（Connectivity）

图的连通性描述了图中顶点与顶点之间的可达性。

  • 连通图（Connected Graph）：对于无向图，如果从任意一个顶点能到达其他所有顶点，则图是连通的。
  • 强连通图（Strongly Connected Graph）：对于有向图，如果任意两个顶点之间都有路径相通，则图是强连通的。
  • 弱连通图（Weakly Connected Graph）：对于有向图，如果将其所有边看作无向边，能够使整个图连通，则图是弱连通的。
    在这里插入图片描述

3. 图的度（Degree）

图中一个顶点的度表示与该顶点连接的边的数量。

  • 入度（In-degree）：有向图中指向该顶点的边的数量。
  • 出度（Out-degree）：有向图中从该顶点发出的边的数量。
    在这里插入图片描述

4. 子图（Subgraph）

子图是从原始图中选取部分顶点和边构成的图。常见的子图类型包括：

  • 生成子图（Spanning Subgraph）：包含图的所有顶点，但边可能有所删减。
  • 诱导子图（Induced Subgraph）：包含图中某些顶点及这些顶点之间的所有边。
    在这里插入图片描述

5. 生成树（Spanning Tree）

生成树是无向图的一个子图，包含图中的所有顶点，且是一个树形结构（无环、连通）。

  • 最小生成树（Minimum Spanning Tree, MST）：在加权图中，生成树的边权和最小的生成树。

生成树：
在这里插入图片描述
最小生成树：
在这里插入图片描述

6. 二分图（Bipartite Graph）

二分图是一种特殊的图，可以将顶点集合分为两个不相交的子集，且所有边都连接两个不同子集中的顶点，而子集中没有内部连接。
在这里插入图片描述

7. 拓扑排序（Topological Sort）

对于有向无环图（DAG），拓扑排序是一种将顶点按依赖关系线性排序的算法，通常用于解决调度、依赖管理等问题。

8. 欧拉图和哈密顿图

  • 欧拉路径（Eulerian Path）：经过图中每条边一次且仅一次的路径。如果这样的路径是闭合的，即路径的起点和终点相同，则称为欧拉回路（Eulerian Circuit）。
  • 哈密顿路径（Hamiltonian Path）：经过图中每个顶点一次且仅一次的路径。如果这样的路径是闭合的，则称为哈密顿回路（Hamiltonian Circuit）。

实现图

邻接矩阵实现图

在这里插入图片描述
如果是无向图的话，那么邻接矩阵就是沿着对角线对称的。
在这里插入图片描述
如果是无向图的话，那么就可以通过压缩只存储一半。
除了需要一个存储权值的邻接矩阵我们还需要一个vector来存储顶点，如果涉及到邻接矩阵，那么就会涉及到下标，所以我们应该还需要一个顶点映射下标的map。

邻接矩阵的基本框架

	//         顶点     weight                       有向图/无向图   template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>class Graph{public:private:vector<V> _vertexs;         //顶点集合map<V, int> _indexMap;      //顶点对应下标的关系（顶点---->下标）vector<vector<W>> _matrix;  //邻接矩阵};
}

核心接口

初始化

Graph(const V* a, size_t n)
{// 开辟n个空间_vertexs.resize(n);for (size_t i = 0;i < n;i++){_vertexs[i] = a[i];//顶点----->下标_indexMap[a[i]] = i;}_matrix.resize(n);//权值用MAX_W初始化for (size_t i = 0;i < n;i++) _matrix[i].resize(n, MAX_W);
}

获取顶点的下标

size_t GetVertexIndex(const V& v)
{auto it = _indexMap.find(v);if (it != _indexMap.end()) return it->second;else{// 抛异常出去throw invalid_argument("顶点不存在");// 过编译器逻辑return -1;}
}

通过map的接口find找到v对应的下标，如果it为end()，说明没有这个顶点，直接抛异常，如果存在，则返回对应的下标
添加边

//                   原点        目标点       权值
void AddEdge(const V& src, const V& dst, const W& w)
{// 获取原点下标size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);_matrix[srci][dsti] = w;// 无向图添加两个权值if (Direction == false) _matrix[dsti][srci] = w;
}

找到原点和目标点对应的下标，如果是有向图的话，只需要添加原点到目标点的边，如果是无向图的话，就需要反向添加一下目标点到原点的边了。

邻接表实现图

邻接表是图的一种存储表示方法，常用于存储稀疏图（即边数相对较少的图）。它通过每个顶点对应一个链表或数组来记录与其相邻的顶点。邻接表的空间复杂度相对较小，适合存储大规模图。
在这里插入图片描述
对于无向图来说不存在入度和出度的概念，所以只需要一个邻接表表示，下标的邻接表就是用来表示边的集合。
在这里插入图片描述
拿第一个点为例，这里使用一个结构体来维护的，这个结构体中有指向一下下一个边集的指针，还有一个权值和目标点的下标。
我们说形象一点：
在这里插入图片描述

类似于哈希桶的那个做法

邻接表实现图的基本框架

template<class W>
struct Edge
{int _dsti;  //目标点的下标W _w;       //权值Edge<W>* _next;Edge(int dsti,const W& w):_dsti(dsti),_w(w),_next(nullptr){}
};
//         顶点   weight         有向图/无向图   
template<class V, class W,bool Direction = false>
class Graph
{typedef Edge<W> Edge;
public:private:vector<V> _vertexs;         //顶点集合map<V, int> _indexMap;      //顶点对应下标的关系（顶点---->下标）vector<Edge*> _tables;       //邻接表
};

核心接口

初始化

Graph(const V* a, size_t n)
{// 开辟n个空间_vertexs.resize(n);for (size_t i = 0;i < n;i++){_vertexs[i] = a[i];//顶点----->下标_indexMap[a[i]] = i;}_tables.resize(n,nullptr);//给tables开辟n个空间（n个顶点）
}

获取顶点对应下标

size_t GetVertexIndex(const V& v)
{auto it = _indexMap.find(v);if (it != _indexMap.end()) return it->second;else{// 抛异常出去throw invalid_argument("顶点不存在");// 过编译器逻辑return -1;}
}

添加边

void AddEdge(const V& src, const V& dst, const W& w)
{// 获取原点下标size_t srci = GetVertexIndex(src);size_t dsti = GetVertexIndex(dst);//1 --> 2//原点到目标的权值Edge* eg = new Edge(dsti, w);//这里进行头插eg->_next = _tables[srci];_tables[srci] = eg;//无向图进行特殊处理//2 --> 1if (Direction == false){//反向指向Edge* eg = new Edge(srci, w);eg->_next = _tables[dsti];_tables[dsti] = eg;}
}

这个和邻接矩阵就不一样，邻接表中添加边应该先创建一个对应边的结构体，然后将这个结构体头插到原点对应下标的边集的位置上，如果是无向图的话，需要反向添加一条目标点到原点的边。注意：头插之后需要改变头的位置

总结

通过本篇文章的介绍，我们初步了解了图的基本概念、图的表示方法（如邻接矩阵和邻接表）、以及图中的各种基本性质。图论作为计算机科学和数学中的一个重要分支，其应用范围广泛，从网络设计到路径规划，都有着广泛的应用场景。

在接下来的学习中，我们可以进一步探讨更高级的图算法，如最短路径算法（Dijkstra、Bellman-Ford 等）、图的遍历算法（深度优先搜索、广度优先搜索）、以及图的连通性和最小生成树等高级主题。这些内容将为解决更复杂的实际问题提供坚实的理论基础。

图论的世界广阔而有趣，期待你能在之后的学习和实践中不断挖掘其奥秘！


http://www.ppmy.cn/news/1533851.html

相关文章

通信工程学习：什么是DQDB分布式队列双总线

通信工程学习：什么是DQDB分布式队列双总线

DQDB&#xff1a;分布式队列双总线 DQDB&#xff08;Distributed Queue Dual Bus&#xff09;&#xff0c;即分布式队列双总线&#xff0c;是美国电气电子工程师学会(IEEE)802.6标准中定义的一种城域网(MAN)数据链路层通信协议。该协议主要用于城域网的数据、语音和视频传输&am…
阅读更多...
Android中使用RecyclerView制作横向轮播列表及索引点

Android中使用RecyclerView制作横向轮播列表及索引点

在Android开发中&#xff0c;RecyclerView是一个非常强大的组件&#xff0c;用于展示列表数据。它不仅支持垂直滚动&#xff0c;还能通过配置不同的LayoutManager实现横向滚动&#xff0c;非常适合用于制作轮播图或横向列表。本文将详细介绍如何使用RecyclerView在Android应用中…
阅读更多...
Gitlab服务搭建相关

Gitlab服务搭建相关

修改用户密码&#xff0c;以root用户为例 # 从host中进入gilab的docker环境 docker exec -it gitlab bash#------ 后续命令均在gitlab docker中执行 ------# # 进入gitlab的bin目录&#xff0c;并启动控制台程序 cd /opt/gitlab/bin gitlab-rails consoleuUser.where(id:1).fi…
阅读更多...
课设实验-数据结构-线性表-手机销售

课设实验-数据结构-线性表-手机销售

题目&#xff1a; 代码&#xff1a; #include<stdio.h> #include<string.h> #define MaxSize 10 //定义顺序表最大长度 //定义手机结构体类型 typedef struct {char PMod[10];//手机型号int PPri;//价格int PNum;//库存量 }PhoType; //手机类型 //记录手机的顺序…
阅读更多...
【easypoi 一对多导入解决方案】

【easypoi 一对多导入解决方案】

easypoi 一对多导入解决方案 1.需求2.复现问题2.1校验时获取不到一对多中多的完整数据2.2控制台报错 Cannot add merged region B5:B7 to sheet because it overlaps with an existing merged region (B3:B5). 3.如何解决第二个问题处理&#xff1a; Cannot add merged region …
阅读更多...
【Ansys Fluent】计算数据导入tecplot傅里叶分析

【Ansys Fluent】计算数据导入tecplot傅里叶分析

来自&#xff1a;fluent计算数据导入tecplot进行傅里叶分析 首先在fluent计算结果中找到监测点压力曲线变化的输出文件&#xff0c;本例是pr0104.out&#xff0c;将文件后缀改为pr0104.txt&#xff0c;并用文本文档打开&#xff0c;将前几行的标题删除&#xff0c;只保留数据&…
阅读更多...
查找与排序-归并排序

查找与排序-归并排序

排序算法可以分为内部排序和外部排序&#xff0c; 内部排序是数据记录在内存中进行排序&#xff0c; 外部排序是因排序的数据很大&#xff0c;一次不能容纳全部的排序记录&#xff0c;在排序过程中需要访问外存。 常见的内部排序算法有&#xff1a;插入排序、希尔排序、选择…
阅读更多...
remote table dblink no_merge提升性能

remote table dblink no_merge提升性能

-----------remote table DML DDL 不能使用DRIVING_SITE hints------ DRIVING_SITE hint is not working for DML or DDL. Remember DRIVING_SITE hint is for query optimization and not intended for DML or DDL, as a distributed DML statement must execute on the data…
阅读更多...
最新文章

Copyright @ 2022~2023