首页 > 其他分享 >图(Graph)

图(Graph)

时间：2024-09-22 17:24:18浏览次数：3  
标签：cur Graph 路径 list 邻接 节点 size

基本概念

  1. (x,y)代表节点x与节点y的一条边（无向边）；<x,y>代表节点与节点y的一条弧（x指向y，有向边），x称为弧尾，y称为弧头

  2. x,y互为邻接点当且仅当，(x,y)∈E或<x,y>且<y,x>属于E（E为边集）

  3. 度=入度+出度 ，TD(V)=ID(V)+OD(V)，v的入度为以v作为弧头的边个数，v的出度为以v作为弧尾的边个数，对于无向图而言出入度相等，度等于出度等于入度

  4. 首尾相同的路径：=回路or环 顶点无重复的路径：=简单路径 仅首尾相同的路径：=简单回路or简单环

  5. 连通图（仅针对无向图），G为连通图当且仅当任意的vi，vj∈V，都存在路径，无向图的连通分量为其极大连通子图

  6. 强连通图（仅针对有向图），G为强连通图当且仅当任意的vi，vj∈V，存在vi->vj的路径且存在 vj->vi的路径，有向图的连通分量为其极大强连通图

  7. 完全图，n个节点且边数为n（n-1）/2的无向图；n个节点且边数为n（n-1）的有向图!

  8. 稀疏图：=e<nlog2n（2为底数,n为节点数，e为边数） 稠密图：=e>=nlog2n

  9. 生成树：=极小连通子图，n个节点n-1条边，任意两节点均有路径，少一条边不连通，多一条边成环
    10.网：=带权图

图的表示

邻接矩阵

n个节点就有需要n*n的二维矩阵，统一规定matrix[i][j]为i到j的边
无向无权图： 这一类图最为简单，其邻接矩阵只需要填充0和1即可，0代表i j之间没有存在边，1代表i j之间存在边
无向带权图： 矩阵每个位置填充i j之间的边权值，使用∞代表i j之间没有边连接
有向无权图： 与无向无权图类似，只不过不是对称矩阵
有向有权图： 与无向带权图类似，只不过不是对称矩阵
在这里插入图片描述

邻接表

定义一个邻接表数组，每个位置存放节点值的同时存放一个用于管理该节点的邻接的节点的链表头指针
对于有向图，分为出度邻接表和入度邻接表
无向无权图： 节点结构：= 节点value+下一邻接点地址
无向有权图： 节点结构：= 节点value+权值+下一邻接点地址
有向带权图： 节点结构与无向无权图一致
有向有权图： 节点结构与无向有权图一致
在这里插入图片描述

邻接表和邻接矩阵各有各的优点
邻接矩阵可以高效的访问节点间的关系，并且对于有向图使用邻接矩阵可以同时表示出度和入度，但是邻接矩阵占用空间较大
邻接表占用空间较小，但是读取访问较为麻烦
一般对于稀疏图适合使用邻接表，稠密图适合采用邻接矩阵

图的遍历

深度优先遍历

在这里插入图片描述
DFS算法描述：
以任意节点作为起点，打印该节点的值后取其任意邻接点作为新的起点，重复操作
当某一个节点的所有邻接点均已经被访问时递归结束开始回溯
第一层递归返回后需要检查图中是否有未打印的节点(如图中节点5)，若有以其为起点再次DFS操作

代码：

/*以邻接表表示的图为例，此处的代码应定义在类中，详见文末Gitee*/
/*_list为邻接表，vis用于标记已经访问的节点，getIndex方法用于获取元素在邻接表中的下标，index为元素在邻接表中的下标*/
/*_list节点类型为pair<T,ListNode*>,T为模板参数代表元素真实类型,ListNode为节点*/
void dfsTraversal()
{
	vector<bool> vis(_list.size());  //初始化标记数组
	for (int i = 0; i < _list.size(); ++i)
	{
		if (!vis[i]) _dfsTraversal(vis, i); //有未访问的节点就对齐进行深度遍历
	}
	cout << endl;
}

void _dfsTraversal(vector<bool>& vis, unsigned int index)
{
	cout << _list[index].first << ' ';
	vis[index] = true;
	ListNode* cur = _list[index].second;
	while (cur)
	{
		if (!vis[getIndex(cur->_val)]) _dfsTraversal(vis, getIndex(cur->_val));
		cur = cur->_next;
	}
}

广度优先遍历

在这里插入图片描述
BFS算法描述：
借助队列，以任意节点为起点入队，打印队首元素后出队，同时将出队元素标记为已访问，将其邻接点全部入队，重复此操作直至队列为空，和DFS一样为了防止忘记遍历节点5，需要对标记数组进行再检查
入队之前先检查节点是否已经访问，如已经被访问则无需入队

代码：

/*_list为邻接表，q为辅助队列，vis为标记数组*/
void bfsTraversal()
{
	vector<bool> vis(_list.size());
	queue<pair<V, ListNode*>> q;
	q.push(_list.front());
	vis[getIndex(q.front().first)] = true; //入队就标记成已经访问过
BFS:
	while (!q.empty())
	{
		ListNode* head = q.front().second;
		ListNode* cur = head;
		while (cur)
		{
			unsigned int index = getIndex(cur->_val);
			if (!vis[index])
			{
				q.push(_list[index]); //没有被标记过就入队
				vis[index] = true;
			}
			cur = cur->_next;
		}
		cout << q.front().first << ' ';
		q.pop();
	}

	for (int i = 0; i < vis.size(); ++i)
	{
		//检查是否还有剩余未遍历的节点
		if (!vis[i])
		{
			q.push(_list[i]);
			vis[i] = true;
			goto BFS;
		}
	}
	cout << endl;
}

最小生成树算法

对于无向带权图，一般会去研究其最小生成树，其中求最小生成树最经典的算法就是Kruskal和Prim算法，二者都是贪心算法

Kruskal Algorithm

算法描述：
选取边集合中的最小边(借助小根堆)
检查边的两个节点是否已经存在路径 （借助并查集）
存在 则直接丢弃该条边
不存在 则将两节点相连
重复此操作 直至生成树中边数为n-1或堆空
因边数为n-1结束则已经产生最小生成树
因堆空结束则表示没有最小生成树
正确性证明：

（1） 证明G是一颗无向连通图，Kruskal算法一定能给出生成树
根据算法描述可知在不断选取边时丢弃的都是会使得产生环的边，保留的边不会产生环
如果G一开始就是连通图，在丢弃掉那些构成回路的边后也一定是能够保持连通状态的
(2) 算法给出的生成树代价最小
假设算法给出的生成树T不是最小代价，由于生成树的个数一定是有限的，必然存在一个最小代价的生成树U
如果U≠T，就一定有k条边存在于T中但不存在于U中(存在于U中但不存在于T中)
如果可以经过有限次的变换将T变成U，那么T就是最小代价的生成树
从T中取出一条边e加入U，同时从U中删除一条边f

e是存在于T中但不存在于U中，f存在于U中但不存在于T中
e加入U之后肯定会产生环，为了删除环，需要从环中删除一条边f (f是一定存在的，如果没有则T本身就带环了)

经过一次变换之后U的代价变动为 e-f 
f不可能大于e，如果是的话U就不是最小成本了
f不可能小于e，如果是的话算法一定会选择f，这恰恰说明了算法在迭代过程中舍弃了f边
因此e-f=0，经过k次变换后T就是U

因此U=T

具体图例：
在这里插入图片描述

参考代码：

/*W，V为模板参数，分别代表权值和节点值
tuple<V,V,W>为三元组，前2个元素为节点，第三个元素为权值*/
class cmp
{
public:
	bool operator()(const tuple<V, V, W>& t1, const tuple<V, V, W>& t2)
	{
		return get<2>(t1) > get<2>(t2);
	}
};
W Kruskal() //克鲁斯卡尔算法求最小生成树成本
{
	unsigned int edgecnt = 0;   //目前已经选择的边数,当到达n-1就是最小生成树
	W cost = W();				//最小生成树的代价
	priority_queue<tuple<V, V, W>, vector<tuple<V, V, W>>, cmp> heap;
	for (auto& t : _edgeset) heap.push(t); //堆排序
	//借助一个并查集用于判断是否形成回路
	UnionFindSet ufs(_list.size());
	
	while (edgecnt < _list.size() - 1 && !heap.empty())//当生成树的边==n-1或者heap为空时结束
	{
		auto& minedge = heap.top();
		//每一次都挑选一条最小的边，如果该边对应的两个节点已经在一个集合中，跳过，否则连接
		if (!ufs.inSet(getIndex(get<0>(minedge)), getIndex(get<1>(minedge))))
		{
			cost += get<2>(minedge);//成本计数
			++edgecnt;
			ufs.merge(getIndex(get<0>(minedge)), getIndex(get<1>(minedge)));
		}
		heap.pop();//heap中删除已经选取过的边
	}
	//如果边小于n-1，那么没有最小生成树,返回0
	return edgecnt == _list.size() - 1 ? cost : W();
}

Prim Algorithm

算法描述：
以任意节点为起点作为生成树，不断向外扩展节点
新增节点后需要将该节点的邻接边加入小根堆，(需要检查是否重复入堆)
取出堆顶元素，如果堆顶边的两个节点还没有路径，则进行连接，否则不做处理
重复此操作直至生成树中边树为n-1或堆空
正确性证明：
假设算法产生的生成树T不是最小代价，那么必定存在一个最小生成树U
也就意味着存在k条在U中使得代价更小的边
这样的边不可能存在，如果存在，那么算法一定会选择（每一步都会保证局部最优性）
因此U=T

具体图例：
在这里插入图片描述

参考代码：

W Prim()		//普里姆算法构建最小生成树
{
	unsigned int edgecnt = 0;	//已经选取的边数
	W cost = W();				//成本
	priority_queue<tuple<V, V, W>, vector<tuple<V, V, W>>, cmp> heap;
	vector<bool> inset(_list.size());  //标记数组，避免边的重复添加
	//任取一个节点作为起点
	inset[getIndex(_list[0].first)] = true;
	ListNode* cur = _list[0].second;
	while (cur)
	{
		heap.push({ _list[0].first,cur->_val,cur->_weight });
		cur = cur->_next; //将与起点所邻接的边全部加入堆中
	}
	while (edgecnt < _list.size() - 1 && !heap.empty())
	{
		//选取与当前生成树相连的最小权重边(堆顶)
		auto& minedge = heap.top();
		//把新增节点的邻接边加入堆
		unsigned int index = getIndex(get<1>(minedge));  
		unsigned int _index = getIndex(get<0>(minedge)); //获取边上2个节点在邻接表中的下标

		if (inset[index] && inset[_index]) { heap.pop(); continue; }
		//如果堆顶中取出的边顶点已经在生成树中，舍去
		if (inset[index]) index = _index;
		inset[index] = true;
		++edgecnt;
		cost += get<2>(minedge);
		cur = _list[index].second;
		heap.pop(); //一定先删除堆顶后再添加边
		while (cur)
		{
			if(!inset[getIndex(cur->_val)]) heap.push({_list[index].first,cur->_val,cur->_weight});
			cur = cur->_next; 
		}
	}
	return edgecnt == _list.size() - 1 ? cost : W();
}

最短路径算法

对于有向带权图常常关注最短路径算法，其中最经典的就是Dijkstra、BellFord、Floyd算法，前两个算法用来解决单源最短路径，
Floyd算法用来解决多源最短路径。Dijkstra只能用于非负权图，BellFord和Floyd可以解决带负权图
Dijkstra基于贪心算法
BellFord、Floyd基于动态规划

如果图中存在负权环，是没有最短路径的，无解

Dijkstra Algorithm(单源最短路径)

算法描述：
借助一个抽象距离数组D表示节点到源点的当前最短路径
借助一个标记数组S用来确定已经确定最短路径的节点，此后不在对其进行更新
每一次从D中取出最小值(该节点不能在S中)，就可以确定该节点的最短路径为当前值，将节点加入S中
尝试对该节点出边相连的节点进行松弛操作
重复操作N次，最终D中记录的就是各个节点到源点的最短路径
若想要显示具体路径，可以在每一次松弛操作的同时记录路径父节点
正确性证明：
证明每一次从D中选择最小的值就能确定该节点的最短路径
由于图中的每一条边权值都是非负的，当前选出的节点最短路径绝对不可能再经过其他不在S中的节点，否则代价就增加了
具体图例：
在这里插入图片描述
参考代码：

/*以邻接矩阵表示图为例*/
/*dis为D数组，parentpath为P数组，_vertex为节点集合,getMapIndex方法用来获取元素在矩阵中的下标，S为标记数组*/
void Dijkstra(const V& src, vector<W>& dis, vector<int>& parentpath)//源点，距离数组，父节点数组
{
	size_t N = _vertex.size(); //节点个数
	dis.resize(N, MAXW);	   //初始状态到各个节点的距离都是∞
	parentpath.resize(N, -1);  //初始状态各个节点没有父节点
	vector<bool> S(N);		   //标记数组S用来收录已经确定最短路径的节点
	size_t srci = getMapIndex(src);
	dis[srci] = 0;             //源点到源点的最短路径长度为0

	//从dis数组中选出当前距离源点最近的节点
	for (size_t i = 0; i < N; ++i)
	{
		W mindis = MAXW;
		size_t u = srci;
		for (size_t j = 0; j < N; ++j)
		{
			if (!S[j] && dis[j] < mindis)
			{
				u = j;
				mindis = dis[j];
			}
		}
		S[u] = true;
		//此时可以确定的是s->u的最短路径
		//从u开始更新dis数组
		for (size_t k = 0; k < N; ++k)
		{
			if (!S[k] && _matrix[u][k] != MAXW && dis[u] + _matrix[u][k] < dis[k])
			{
				dis[k] = dis[u] + _matrix[u][k];
				parentpath[k] = u;
			}
		}
	}
}

BellFord Algorithm(单源最短路径)

算法描述：
BellFord借助每一个节点的入度表，不断尝试对最短路径进行优化
如果有节点能经过其他节点使得与源点更近，那么就进行一次松弛操作
这种迭代最多进行n-1次，超过则说明带有负权环
(原因是最短路径边数最多为n-1条，即至多只需要n-1轮松弛更新)
具体图例：
在这里插入图片描述

参考代码：

void BellFord(const V& src, vector<W>& dis, vector<int>& parentpath)
{
	size_t N = _vertex.size();
	size_t sweepcnt = 0;  //扫描次数,sweepcnt==N时无解
	size_t srci = getMapIndex(src);
	bool hasupdate = false;   //记录上一次扫描有没有更新dis，没有则退出
	parentpath.resize(N, -1);
	dis.resize(N, MAXW);
	dis[srci] = 0;
	
	do
	{
		hasupdate = false;
		if (++sweepcnt == N) break;
		for (size_t i = 0; i < N; ++i) //检索所有节点，尝试优化
		{
			for (size_t j = 0; j < N; ++j)
			{
				if (_matrix[j][i]!=MAXW && dis[i] - _matrix[j][i] > dis[j]) //处理溢出情况
				{
					dis[i] = _matrix[j][i] + dis[j];
					parentpath[i] = j;
					hasupdate = true;
				}
			}
		}
	} while (hasupdate);
	if (sweepcnt == N) { cout << "no solution\n"; return; }
}

Floyd Algorithm(多源最短路径)

算法描述：
以每一个节点作为中间节点尝试优化最短路径
在这里插入图片描述
三维数组可以优化成二维数组
具体图例：
在这里插入图片描述
参考代码：

void Floyd(vector<vector<W>>& D, vector<vector<int>>& P) //D是距离矩阵，P是父节点矩阵
{
	D = _matrix; //初始阶段D就是邻接矩阵
	size_t N = _vertex.size();
	P.resize(N, vector<int>(N, -1));
	for(int i=0;i<N;++i)
		for (int j = 0; j < N; ++j)
			if (_matrix[i][j] != MAXW && i != j) P[i][j] = i;
	for (size_t k = 0; k < N; ++k)  //每一个节点都选择当一次中间节点尝试更新动规表
	{
		for (size_t i = 0; i < N; ++i)
		{
			for (size_t j = 0; j < N; ++j)
			{
				if (D[i][k] + D[k][j] < D[i][j])
				{
					D[i][j] = D[i][k] + D[k][j];
					P[i][j] = P[k][j]; //不能赋值为k，K->^^^^->j
				}
			}
		}
	}
}

拓扑排序

拓扑排序是一个有向无环图的所有顶点的线性序列。
序列满足下面两个条件：
每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面
进行拓扑排序的时候一般需要借助邻接表（邻接矩阵）和入度数组，其中入度数组用来表示节点的入度
可以通过广度优先的方式实现拓扑排序，借助辅助队列
每一次从队首取出元素更新其邻接点的入度，如果有邻接点的入度变为0，则将其入队
迭代操作直至队列为空
以LeetCode课程表为例：

class Solution {
public:
   bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
       //1、创建邻接表和入度数组
       unordered_map<int,vector<int>> edges(numCourses);
       vector<int> in(numCourses);
       //2、填充入度数组和邻接表
       for(auto& e:prerequisites)
       {
           int a=e[0],b=e[1]; //b为先决条件
           edges[b].push_back(a);
           in[a]++;
       }
       //3、拓扑排序
       queue<int> q;
       for(int i=0;i<numCourses;++i)
           if(!in[i]) q.push(i);
       while(!q.empty())
       {
           int t=q.front();q.pop();
           for(int i:edges[t])
           {
               //更新邻接节点的入度
               in[i]--;
               if(!in[i]) q.push(i);
           }
       }

       for(auto x:in) if(x) return false; //如果还有入度不为0的节点，则无法拓扑排序
       return true;
   }
};

https://gitee.com/chxchenhaixiao/test_c/blob/master/Graph 图–代码参考

标签：cur,Graph,路径,list,邻接,节点,size
From： https://blog.csdn.net/2301_78863061/article/details/142422209

相关文章

  • GraphRAG 与 RAG 的比较分析
    检索增强生成（RAG）技术概述检索增强生成（Retrieval-AugmentedGeneration，简称RAG）是一种旨在提升大型语言模型（LargeLanguageModels，LLMs）性能的技术方法。其核心思想是通过整合外部可靠知识库的信息来增强模型的输出质量。RAG的工作原理可以概括如下：当LLM接收到查询时，它不仅依赖......
  • RAG+Agent人工智能平台：RAGflow实现GraphRAG知识库问答，打造极致多模态问答与AI编排流体
    RAG+Agent人工智能平台：RAGflow实现GraphRAG知识库问答，打造极致多模态问答与AI编排流体验1.RAGflow简介最近更新：2024-09-13增加知识库问答搜索模式。2024-09-09在Agent中加入医疗问诊模板。2024-08-22支持用RAG技术实现从自然语言到SQL语句的转换。2024-08-02......
  • 【论文阅读笔记】【Hand Pose Estimation-Interacting Hand】 Interacting Attention
    CVPR2022(Oral)读论文思考的问题论文试图解决什么问题？写作背景是什么？问题：如何将图卷积神经网络（GCN）结构应用到双手交互识别上，且能很好地解决双手的遮挡、相似和交互的问题？背景：双手识别的挑战：1.严重的相互遮挡，双手形状类似。2.难以有效地建模交互的上下文信息......
  • 大模型入门到进阶：什么是Graph RAG？
    自从ChatGPT的出现引爆了人工智能的炒作之后，检索增强生成(RAG)就主导了关于如何让GenAI应用程序变得有用的讨论。这个想法很简单。一旦我们将LLM连接到我们的私人数据，它就会变得特别有用。每个人都可以访问的基础模型与我们特定领域的数据相结合，作为秘密武器，产生......
  • RAG+Agent人工智能平台：RAGflow实现GraphRA知识库问答，打造极致多模态问答与AI编排流体
    RAG+Agent人工智能平台：RAGflow实现GraphRA知识库问答，打造极致多模态问答与AI编排流体验1.RAGflow简介最近更新：2024-09-13增加知识库问答搜索模式。2024-09-09在Agent中加入医疗问诊模板。2024-08-22支持用RAG技术实现从自然语言到SQL语句的转换。2024-08-02支持Gr......
  • R语言安装graph包报错：package graph is not available for this version of R
    我的R语言版本是4.0.2，安装graph包的时候出现如下报错尝试过换源都无法下载后来尝试在google想搜索graph包的官网，搜出来：https://cran.r-project.org/web/packages/graph/index.html 应该是graph包被CRAN更新了，现在已不在使用根据它的提示，进入链接：https://www.bioconductor.or......
  • P9705 「TFOI R1」Unknown Graph题解
    思路题目给出了每个点的初度和入度，由于图是无重边无自环的有向图。要求满足限制的图有多少条边与建图方案。我们可以考虑使用网络流中的最大流。我们知道这是一道网络流后，题目的难点就转移到网络流的建模以及输出方案的办法。网络流的建模：题目所给的条件没有源点汇点并指出......
  • Paper Reading: Deep forest auto-Encoder for resource-Centric attributes graph em
    目录研究动机文章贡献本文方法整体思想autoencoder预处理器深度森林编码生成器实验结果数据集和实验设置节点分类节点聚类用户推荐消融实验调参实验优点和创新点PaperReading是从个人角度进行的一些总结分享，受到个人关注点的侧重和实力所限，可能有理解不到位的地方。具体的细节......
  • Shader Graph自定义渐变色节点Gradiant
    ShaderGraph自定义渐变色节点GradiantUnity自带Shader中的Gradiant不能暴露在外部使用定义CustomFunction来制作暴露给外部的GradiantShaderGraph节点图CustomFunction代码if(inputValue<location1){outFloat=color1;}else......
  • AnomalyLLM: Few-shot Anomaly Edge Detection for Dynamic Graphs using Large Langu
    本文是LLM系列文章，针对《AnomalyLLM:Few-shotAnomalyEdgeDetectionforDynamicGraphsusingLargeLanguageModels》的翻译。AnomalyLLM：使用大型语言模型对动态图进行少量异常边缘检测摘要1引言2相关工作3前言4方法5实验6结论摘要检测动态图的......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99