Loading [MathJax]/jax/output/CommonHTML/jax.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【数据结构】图论基础

【数据结构】图论基础

作者头像
用户11305458
发布于 2024-10-09 09:29:25
发布于 2024-10-09 09:29:25
22700
代码可运行
举报
文章被收录于专栏:学习学习
运行总次数:0
代码可运行

图的概念

图(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)
    • 图中任意两个顶点之间都有边相连,通常表示为

    ,其中

    是顶点数。

图的表示方法

  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。

邻接矩阵的基本框架
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
	//         顶点     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;  //邻接矩阵
	};
}
核心接口

初始化

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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);
}

获取顶点的下标

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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(),说明没有这个顶点,直接抛异常,如果存在,则返回对应的下标 添加边

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
//                   原点        目标点       权值
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;
}

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

邻接表实现图

邻接表是图的一种存储表示方法,常用于存储稀疏图(即边数相对较少的图)。它通过每个顶点对应一个链表或数组来记录与其相邻的顶点。邻接表的空间复杂度相对较小,适合存储大规模图。

对于无向图来说不存在入度和出度的概念,所以只需要一个邻接表表示,下标的邻接表就是用来表示边的集合。

拿第一个点为例,这里使用一个结构体来维护的,这个结构体中有指向一下下一个边集的指针,还有一个权值和目标点的下标。 我们说形象一点:

类似于哈希桶的那个做法

邻接表实现图的基本框架
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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;       //邻接表
};
核心接口

初始化

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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个顶点)
}

获取顶点对应下标

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
size_t GetVertexIndex(const V& v)
{
	auto it = _indexMap.find(v);
	if (it != _indexMap.end()) return it->second;
	else
	{
		// 抛异常出去
		throw invalid_argument("顶点不存在");
		// 过编译器逻辑
		return -1;
	}
}

添加边

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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 --> 1
	if (Direction == false)
	{
		//反向指向
		Edge* eg = new Edge(srci, w);
		eg->_next = _tables[dsti];
		_tables[dsti] = eg;
	}
}

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

总结

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

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

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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-10-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
图论基础,如何快速上手图论?
前面我们学过了一些基本的数据结构,像顺序表,链表,栈,队列,树等...其中最有难度的就属树的部分了,而图论的与树也是有关联的,在后续我们经常可以看到一些图类似树,但是又不是树,他们的区别在哪?二叉树是父亲节点和孩子的关联,是从上到下的,而图没有父亲节点和孩子节点,他主要使用节点描述各个事件之间的关系;
啊QQQQQ
2025/01/20
1510
图论基础,如何快速上手图论?
DS高阶:图论基础知识
        图是比线性表和树更为复杂且抽象的结,和以往所学结构不同的是图是一种表示型的结构,也就是说他更关注的是元素与元素之间的关系。下面进入正题。
小陈在拼命
2024/05/04
1270
DS高阶:图论基础知识
图详解第一篇:图的基本概念及其存储结构(邻接矩阵和邻接表)
无向图中,顶点对(x, y)是无序的,顶点对(x,y)称为顶点x和顶点y相关联的一条边,这条边没有特定方向,(x, y)和(y,x)是同一条边,比如下图G1和G2为无向图
YIN_尹
2024/01/23
5.9K0
图详解第一篇:图的基本概念及其存储结构(邻接矩阵和邻接表)
【c++高阶DS】图
比如:某公司今年校招全国总共招生10人,西安招4人,成都招3人,武汉招3人,10个人来自不同的学校,起先互不相识,每个学生都是一个独立的小团体,现给这些学生进行编号:{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体,数组中的数字代表:该小集体中具有成员的个数
用户11029103
2024/12/25
1280
【c++高阶DS】图
【高阶数据结构】秘法(二)——图(一):图的基本概念和存储结构
图是一种非线性的数据结构:G=(V,E),它由节点(也称为顶点)和连接这些节点的边组成。图可以用来表示现实世界中的各种关系,如社交网络、交通网络、电路网络等。
GG Bond1
2024/09/05
1820
【高阶数据结构】秘法(二)——图(一):图的基本概念和存储结构
图的基本概念以及DFS与BFS算法
顶点和边:图中结点称为顶点,第 i 个顶点记作 vi。两个顶点 vi 和 vj 相关联称作顶点 vi 和顶点 vj 之间有一条边,图中的第 k 条边记作 ek,ek = (vi,vj) 或 <vi,vj>。
利刃大大
2023/04/12
6890
图的基本概念以及DFS与BFS算法
【算法与图】通向高效解决方案的钥匙
BFS(广度优先搜索)是一种图的遍历算法,用于从一个起始节点出发,逐层访问图中的所有节点。其基本流程如下:
用户11305458
2024/10/09
1.1K0
【算法与图】通向高效解决方案的钥匙
DS高阶:图论算法经典应用
连通图中的每一棵生成树,都是原图的一个极大无环子图,即:从其中删去任何一条边,生成树就不在连通;反之,在其中引入任何一条新边,都会形成一条回路。
小陈在拼命
2024/05/06
1550
DS高阶:图论算法经典应用
图详解第三篇:最小生成树(Kruskal算法+Prim算法)
连通图中的每一棵生成树,都是原图的一个极大无环子图,即:从其中删去任何一条边,生成树就不在连通;反之,在其中引入任何一条新边,都会形成一条回路。
YIN_尹
2024/01/23
4.3K0
图详解第三篇:最小生成树(Kruskal算法+Prim算法)
【c++高阶DS】最小生成树
连通图中的每一棵生成树,都是原图的一个极大无环子图,即:从其中删去任何一条边,生成树就不在连通;反之,在其中引入任何一条新边,都会形成一条回路,且这些边的权值之和最小
用户11029103
2024/12/28
2270
【c++高阶DS】最小生成树
【数据结构与算法】图的最短路径算法实现:Dijkstra && Bellman-Ford && Floyd-Warshall
​ 最短路径问题:从在带权有向图 G 中的某一顶点出发,找出一条通往另一顶点的最短路径,最短也就是沿路径各边的权值总和达到最小。
利刃大大
2025/03/19
4550
【数据结构与算法】图的最短路径算法实现:Dijkstra && Bellman-Ford && Floyd-Warshall
图详解第二篇:图的遍历(广度优先+深度优先)
其实我们之前学过的二叉树的层序遍历就是一种广度优先遍历,要借助一个队列来搞,下面对图的广度优先遍历也是一样
YIN_尹
2024/01/23
1.4K0
图详解第二篇:图的遍历(广度优先+深度优先)
最小生成树算法:Kruskal 与 Prim算法
连通图中的每一棵生成树,都是原图的一个极大无环子图,即:从其中删去任何一条边,生成树就不再连通;反之,在其中引入任何一条新边,都会形成一条回路。
利刃大大
2023/04/12
2.2K0
最小生成树算法:Kruskal 与 Prim算法
【c++高阶DS】图的遍历
给定一个图G和其中任意一个顶点v0,从v0出发,沿着图中各边访问图中的所有顶点,且每个顶点仅被遍历一次。"遍历"即对结点进行某种操作
用户11029103
2024/12/26
1470
【c++高阶DS】图的遍历
数据结构10 图
这一篇我们要总结的是图(Graph),图可能比我们之前学习的线性结构和树形结构都要复杂,不过没关系,我们一点一点地来总结。那么关于图,我将从以下几点进行总结: 1、图的定义 2、图相关的概念和术语 3、图的创建和遍历 1、图的定义 什么是图呢? 图是一种复杂的非线性结构。 在线性结构中,数据元素之间满足唯一的线性关系,每个数据元素(除第一个和最后一个外)只有一个直接前驱和一个直接后继; 在树形结构中,数据元素之间有着明显的层次关系,并且每个数据元素只与上一层中的一个元素(父节点)及下一层的多个元素(孩子节点
nnngu
2018/03/15
8290
数据结构10 图
为实习准备的数据结构(11)-- 图论算法 集锦
又要画图了。一到这里就莫名其妙的烦,之前写过的图相关博客已经让我都删了,讲的语无伦次。 希望这篇能写好点。
看、未来
2021/09/18
6490
数据结构-图结构
图Graph是由顶点(图中的节点被称为图的顶点)的非空有限集合V与边的集合E(顶点之间的关系)构成的。 若图G中的每一条边都没有方向,则称G为无向图。 若图G中的每一条边都有方向,则称G为有向图。
WuShF
2023/07/08
4510
数据结构-图结构
重学数据结构(七、图)
图是一种比线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继;在树形结构中,数据元素之间有着明显的层次关系,并且每一层中的数据元素可能和下一层中的多个元素(即其孩子结点)相关,但只能和上一层中一个元素(即其双亲结点)相关; 而在图结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。
三分恶
2020/12/01
7850
重学数据结构(七、图)
数据结构之图
基本概念 图(Graph):图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间可能存在关系。即结点之间的关系可以是任意的,图中任意元素之间都可能相关。 图G由两个集合V(顶点Vertex)和E(边Edge)组成,定义为G=(V,E) 线性结构:是研究数据元素之间的一对一关系。在这种结构中,除第一个和最后一个元素外,任何一个元素都有唯一的一个直接前驱和直接后继。 树结构:是研究数据元素之间的一对多的关系。在这种结构中
xiangzhihong
2018/02/05
8710
数据结构之图
图的基本操作
图是一种非线性数据结构, 由【顶点Vertex】 和 【边Edge】组成。我们可以将图G抽象地表示为一组顶点V 和一组边 E 地集合。
用户11097514
2024/05/30
1500
图的基本操作
相关推荐
图论基础,如何快速上手图论?
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档