维基百科：在图论和网络分析中，中心性指标为图中相应网络位置的节点分配排名或数值。中心性这一概念最初起源于社交网络分析，因此很多衡量中心性的术语也反映了其社会学背景。不同中心性指标对“重要”的衡量方式不同，因此适用于不同的情形。katz和PageRank都可以视为特征向量中心性的变体。一、特征向量中心性（eigenvectorcentrality） 特征向量这一概念最早应该是在线性代数这门课程中接触到的，而取名中的特征向量也与它最初的概念相关，我们先回顾下什么是“特征值”和“特征向量”。1.1线性代数中的特征向量定义：设A是n阶方阵，若存在向量使得 ，则称x为A的特征向量， 为A的特征值（严格
一.情景导入x1-x0求x3-x0的最大值；二.数学解法联立式子2和5，可得x3-x0三.图论但式子多了我们就不好解了，或者说在计算机中怎么解呢？我们可以想到，不妨把式子转为图的形式。我们令x0-->x1的边表示为x1-x0则以上式子可以画图为：这边，x3-x0可以为：（即x3-x0也可以为：（即x3-x0还可以为:（即x3-x0所以我们取最短路径即可！ 四.差分约束这个即是差分约束的模型注意：当出现负环的情况，我们可知，式子是无解的！（所以要用spfa算法判断负环）当要求的两个点没有联通时，可知这两个式子没有约束！所有解都有可能！五.例题：3169--布局(poj.org) 样例输入：421
文章目录求最短路算法总览Dijkstra朴素Dijkstra算法（⭐原理讲解！⭐重要！）（用于稠密图）例题：849.Dijkstra求最短路I代码1——使用邻接表代码2——使用邻接矩阵补充：稠密图和稀疏图&邻接矩阵和邻接表堆优化版Dijkstra算法（⭐原理讲解！⭐重要！）用于稀疏图例题：850.Dijkstra求最短路IIbellman-ford例题：853.有边数限制的最短路为什么需要对dis数组进行备份？spfa算法（bellman-ford算法的优化）例题：851.spfa求最短路例题：852.spfa判断负环Floyd（很暴力的三重循环）例题：854.Floyd求最短路求最短路算法总
最短路单源最短路所有边权都是正数朴素Dijkstra算法基本思路:从1号点到其他点的最短距离步骤:定义一个s集合包含当前已确定最短距离的点1、初始化距离dis[1]=0,dis[其它]=正无穷2、fori0-n循环n次 2.1找到不在s中的距离最近的点->t 2.2把t加到s当中去 2.3用t来更新其它点的距离模板代码如下:#include#include#includeusingnamespacestd;constintN=510;intn,m;intg[N][N];//dis表示从1号点到其它点的距离intdist[N];//st表示每个点的最短路是否确定boolst[N];int
力扣-图论深度优先搜索剑指OfferII111.计算除法我的题解:**思路:*字符串a/b=2.0,b/c=3.0可以求:b/c=3.0,c/b=1.0/3.0,因此我们可以将a/b描述为从a到b的一条边，这样就抽象画出一张图，我们将所有的点与权值加入图中，然后遍历queries首先看这两个字符是否包含在图中若没有则不需要搜索，直接将该点赋为-1.0，若两个点都在图中，且都是同一个点，那么自己到自己，将该点赋为1.0,其它情况我们进行深度优先搜索对图进行遍历，我们每访问一个节点就对该节点进行标记，去搜索与该节点连接的节点，若是目标节点就直接返回，若找到目标节点，即该路径存在就返回该路径的值*当
理论基础： 第一题、所有可能的路径 力扣题目链接classSolution{private:vector>result;vectorpath;voiddfs(vector>&graph,intx){if(x==graph.size()-1){result.push_back(path);return;}for(inti=0;i>allPathsSourceTarget(vector>&graph){path.push_back(0);dfs(graph,0);returnresult;}};第二题、岛屿数量 力扣题目链接深搜版：classSolution{private:intdir[4][2
第一题、被围绕的区域 力扣题目链接classSolution{private:intdir[4][2]={-1,0,0,-1,1,0,0,1};voiddfs(vector>&board,intx,inty){board[x][y]='A';for(inti=0;i=board.size()||nexty=board[0].size())continue;if(board[nextx][nexty]=='X'||board[nextx][nexty]=='A')continue;dfs(board,nextx,nexty);}return;}public:voidsolve(vector>&b
目录最小环有向带权图最小环算法例题无向带权图最小环算法例题无权图最小环算法例题最大环无权图最大环算法例题环计数三元环计数算法例题四元环计数算法例题最小环有向带权图最小环这里不考虑自环，若存在自环，答案与所有自环取最小值即可。算法解法一：dijkstra枚举边，复杂度O(M(N+M)logN)O(M(N+M)logN)O(M(N+M)logN)。对环上一条有向边v→uv\rightarrowuv→u，从uuu到vvv的最短路ddd加上边长www就是包含该边的最小环长，因此枚举所有边即可。一种剪枝优化是可以比较队头与答案大小，若不优显然无需继续跑当前最短路。解法二：dijkstra枚举顶点，复杂度
文章目录二分图介绍染色法判定二分图例题：860.染色法判定二分图匈牙利匹配二分图最大匹配匈牙利匹配算法思想例题：861.二分图的最大匹配二分图介绍https://oi-wiki.org/graph/bi-graph/二分图是图论中的一个概念，它的所有节点可以被分为两个独立的集合，每个边的两个端点分别来自这两个不同的集合。换句话说，二分图中不存在连接同一集合内两个节点的边。染色法判定二分图如何判断一个图是二分图？当且仅当图中不含奇数环。（奇数环指的是环中边的个数是奇数）（因为每一条边都是从一个集合走到另一个集合，只有走偶数次才有可能回到同一个集合。）染色：相邻的节点的颜色不一样。因为没有奇数环，
目录①基准法②并查集③逆向思维之标记环边④并查集压缩路径①基准法在图论中，一条边被称为“桥”代表这条边一旦被删除，这张图的连通块数量会增加。等价地说，一条边是一座桥当且仅当这条边不在任何环上。一张图可以有零或多座桥。因此找桥边最简单粗暴的思想，也就是基准算法的思想就是可以暴力枚举每一条边，将这条边删除后，判断图的连通分量有没有因此而增加，如果图的连通分量增加了，那么说明这是一条桥边。如图1所示，我们将图的每一条边都删除一遍，然后数一下图的连通分量有没有因此而增加，如果图的连通分量因此增加了，那么说明我们刚刚删除的这条边就是桥边。图1基准暴力枚举图的连通分量的个数可以通过深度遍历的次数来计算，将
