四川省建设工程招投标网站,一般网站建设步骤,视频网站怎么建,wordpress网站整站搬迁大家好我是苏麟 , 今天聊聊图的常见算法 . 图里的算法是很多的#xff0c;这里我们介绍一些常见的图算法。这些算法一般都比较复杂#xff0c;我们这里介绍这些算法的基本含义#xff0c;适合面试的时候装*#xff0c;如果手写#xff0c;那就不用啦。 图分析算法#xf…大家好我是苏麟 , 今天聊聊图的常见算法 . 图里的算法是很多的这里我们介绍一些常见的图算法。这些算法一般都比较复杂我们这里介绍这些算法的基本含义适合面试的时候装*如果手写那就不用啦。 图分析算法以图论为驱动进行算法优化结合应用工程业务形态研究不同领域场景模拟不同网络结构通过自由刻画网络图形关系验证结构合理性如边的有向和无向及权重从而辅助分析图形关系、图结构分析、网络结构分析等研究
1.最小生成树(Minimum Spanning Tree)
主要是三种算法: Prim算法、Kruskal算法、Sollin (Boruvka)算法
(1) Prim算法,普里姆算法图论中的一种算法基于一种贪心的思想可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中不但包括了连通图里的所有顶点(英语: Vertex(graph theory) 且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语: Voitech Jarnik)发现:并在1957年由美国计算机科学家罗伯特·普里姆英语: Robert C.Prim) 独立发现1959年艾效格·迪科斯彻再次发现了该算法。因此在某些场合普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆 - 亚尔尼克算法。Prime算法本质是动态规划 (2) Thorup 算法 对于平面有向图一种更快的方法是如Mikkel Thorup在2004年所提出的算法。计算复杂度为其中为增长速度非常缓慢的inverse-Ackermann函数。该算法还可以提供近似最短路径距离以及路由信息。
(3) Kameda算法 如果图形是平面的非循环的并且还表现出以下附加属性则可以使用由1975年的T.Kameda 提出的更快的预处理方法: 所有0-indegree和所有0-outdegree顶点出现 (通常假设为外面)并且可以将该面的边界分割为两个部分使得所有0个不等的顶点出现在一个部分上并目所有的0度外的顶点出现在另一个部分上 (即两种类型的顶点不交替)。
2.连通结构 (Connected Components)
无向图G的极大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个即是其自身非连通的无向图有多个连通分量。这种结构称作连通结构。 3.双联通结构 (Biconnected Components)
任意两点之间都有多于一条的路径则称为双连通图也叫双连通分量双连通分量的术语是biconnectedcomponents,简称为BC这种结构为双联通结构。任何一对顶点之间至少存在有两条路径,在删去某个顶点及与该顶点相关联的边时,也不破坏图的连通性。对于无向图的一个子图是双连通的则称为双连通子图。极大的双连通子图称为双连通分量。一个无向图可以有多个双连通分量一个点也算是双连通分量。 4.强联通结构 (Strongly Connected Components)
有向图的极大强连通子图称为的强连通分量强连通图只有一个强连通分量即是其自身。非强连通的有向图有多个强连通分量。如果任意两点之间都能到达则称为强连通图。如果对于有向图的一个子图是强连通的则称为强连通子图这种结构称为强联通结构。 5.可达性 (Reachability)
在图论中可达性是指在图中从一个顶点到另一个顶点的容易程度。在无向图中可以通过识别图的连接分量来确定所有顶点对之间的可达性。我们的产品解决方案通过定义一个实体为原点通过原点链接计算出图中有向可达路径范围和无向可达路径范围无向可达范围一般大于有向可达。 常用算法为: Floyd-Warshall,Thorup,Kameda这三种算法
(1) Floyd-Warshall算法 Floyd-Warshall算法(Floyd-Warshall algorithm) 是解决任意两点间的最短路径的一种算法可以正确处理有向图或负权的最短路径问题同时也被用于计算有向图的传递闭包。Flovd-Warshal算法的时间复杂度为O(N)空间复杂度为O(N*N)。
(2) Thorup 算法 对于平面有向图一种更快的方法是如Mikkel Thorup在2004年所提出的算法。计算复杂度为其中为增长速度非常缓慢的inverse-Ackermann函数。该算法还可以提供近似最短路径距离以及路由信息。
(3) Kameda算法 如果图形是平面的非循环的并且还表现出以下附加属性则可以使用由1975年的T.Kameda 提出的更快的预处理方法: 所有0-indegree和所有0-outdegree顶点出现 (通常假设为外面)并且可以将该面的边界分割为两人部分使得所有0个不等的顶点出现在一个部分上并且所有的0度外的顶点出现在另一个部分上 (即两种类型的顶点不交替)。
6.K核算法(K-Core)
k-Core算法是一种经典图算法用于寻找一个图中符合指定核心度的顶点的集合即要求每个顶点至少与该子图中的其他k个顶点相关联。k-Core算法用于寻找一个图中符合指定核心度的顶点的集合求每个顶点至少与该子图中的其他k个顶点相关联。这个我们提供1-5Core的图计算在图谱中可以分别找出1-5Core的团结果发现并可以用于子图分类。适用于图推演、生物学、社交网络、金融风控等场景。 7.全路径 (ALL Paths)
全路径就是网络图中的路径集合。分有向和无向有向路径通过源到目标方向不可逆无向路径通过源点和目标之间产生的图关系。在同一图形中无向路径远多于有向。源点是设定的初始点目标是设置的需要通过源点要到达的点。有几种基本情况一是源点和目标点同一设置即自循环有向情况下自循环就是1个节点。二是无向情况下自循环和有向情况一样但二个节点以上则会多种混合循环体。产品可以通过设置源点和目标进行分析源点和目标之间产生的有向无向关系。 8.链结构 (ALL Chains)
链结构包含循环或路径结构从图形结构树的基本循环集派生而来。通过优先搜索图形结构把图中链分解成一组循环或路径从原点出发有向或无向远离根原点后又回到原点则为基本环。如果没有回到原点则为一条路径而不是一个环。每个循环或路径称为链。这种结构称为链结构。 9.Single Source
Single Source称为单源意为只有一个源为基础。首先是不允许有负环单源实体到所有实体的最短路径构成一棵最短路径树。通过单源路径算法可以通过选中实体定义源找出以这个实体源为中心或起始点的图结果. 10.环结构 (Cycles)
环结构即网络的循环结构通过有向或无向路径最后形成回到起点闭环。可以理解为形成一个“圈”。网络的基础循环是循环的最小集合使得网络中的任何循环都可以写成基础中的循环总和。循环基数很有用如单循环(自循环)、双向循环(双实体双向关系)、三角循环(三个实体循环路径) 、四方循环(四个实体循环路径)五边形以此类推。 还有很多 , 就不一一列举了 , 感兴趣的同学自己查查相关资料 . 这期就到这里了 , 再见!
