精华内容
下载资源
问答
  • 首先要先弄清楚有向图中弧、无向图中边以及路径的概念;    为了加深自己的理解,再来两个题目练练手呢     注:以上题目节选自《2018年数据结构考研复习指导》(王道考研)...
    •           首先要先弄清楚有向图中弧、无向图中边以及路径的概念;

     

    •              为了加深自己的理解,再来两个题目练练手呢

     

     

    注:以上题目节选自《2018年数据结构考研复习指导》(王道考研)

    展开全文
  • 根据电信数据的特点,以关系数据库为基础,实现了一个极大连通子图求解算法(MCSG)。该算法利用等价类的概念实现了图数据分层处理,利用边标识法表示极大连通子图,确保了结果中顶点和边信息的完整性。实验表明,...
  • 连通图:最短路径就是形成闭环。 一个有向无环图的拓扑序列不是唯一的: 注意: 1)只有有向无环图才存在拓扑序列; 2)对于一个DAG(Directed Acyclic Graph,有向无环图),可能存在多个拓扑序列; 进行拓扑排序...

    目录

     

    拓扑排序

    图的基础知识 

    1.图的定义

    2.无向图

    3.简单图多重图

    4.完全图

    5.子图

    6.连通,强连通、连通图、连通分量(极大连通子图)

    7.强连通图、强连通分量

    8.生成树和生成森林,深度优先生成树和广度优先生成树

    9.顶点的度、入度和出度

    10.边的权和网

    11.路径、路径长度和回路

    12.简单路径、简单回路

    13.距离

    14.有向树

    15连通图详解

    16 强连通图


    拓扑排序,DAG,AOV网,

     

    1. 一些概念
    DAG(directed acycline graph):有向无环图
    检查一个有向图是否存在环:从有向图上某个顶点v出发遍历,DFS(v)结束之前,出现一条从顶点u到v的回边,u在生成树上是v的子孙,则有向图中必定存在包含顶点v和u的环。
    AOV网(Activity On Vertex Network):在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系。这样的有向图为顶点表示活动的网,我们称为AOV网。
    AOV网中不应该出现环,因为这意味着某项活动是以自己为先决条件的。所以对给定的AOV网,应该先判断是否有环。判断方式可以用拓扑排序。

    2. 拓扑排序(Topological Sorting)(简单记忆:拖地:拓扑排,dfs
    拓扑排序是一个DAG的所有顶点的线性序列。且该序列必须满足下面两个条件:
    ①每个顶点出现且只出现一次。
    ②若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
    具体实现方式:
    ①从 DAG 图中选择一个 没有前驱(即入度为0)的顶点并输出。
    ②从图中删除该顶点和所有以它为起点的有向边。
    ③重复 1 和 2 直到当前的 DAG 图为空,并且当前图中不存在无前驱的顶点为止。如果出现图不为空,但不存在无前驱的顶点的情况说明有向图中必然存在环。

    二. 关键路径 - AOE网(边上的活动)

    应用:(边活动,带权,关键路径:最长。工程时间问题。)
    1. 一些概念
    AOE网(activity on edge network):和AOV网相对,即边表示活动的网。是一个带权、有向、无环图。其中顶点表示事件(evnet),边表示活动,权表示活动持续的时间。通常用来估算工程的完成时间。
    关键路径(critical path):从开始点到完成点的最长路径长度,叫做关键路径。如果看成一个工程,这条关键路径的长度,也是整个工程能完成的最短时间。
    关键活动:某一条弧,弧上的权值增加,响应的最长路径长度也会增加。这条弧叫关键活动。
    最短路径只是某一点到另一点走的最快最短的路径。

    关键路径点为事件,线为过程,需要将所有工程完成时的路径,所以选最长路径为关键路径才能确保所有工程都完成

    一个有向无环图的拓扑序列不是唯一的:

    注意:

       1)只有有向无环图才存在拓扑序列;

       2)对于一个DAG(Directed Acyclic Graph,有向无环图),可能存在多个拓扑序列;

    进行拓扑排序的算法并不复杂:(思想)
    1)在有向图中选一个没有前驱(入度为0)的顶点且输出之
    2)从图中删除该顶点及它发出的弧(这样就得到了别的入度为0的顶点)。
     重复上述两步,直至图空,
    或者图不空但找不到无前驱的顶点为止。然后输出全部顶点。

    从描述上可以看出,我们需要记录每个顶点的入度,实现如下:由于没有记录入度这一信息,先要求出一个入度数组,来表示每个顶点的入度,这个入度数组还要动态更新,当一个顶点被删除后,它指向的顶点的入度都要减1.

     拓扑排序可能是唯一的又有可能是不唯一的。(存在环)。。。。比如

     

    dfs:

     

    拓扑排序基于DFS;

    一. 拓扑排序 - AOV网(顶点上的活动,AOV(Activity On Vertex Network,活动在顶点上的网

    应用:(点上的活动,强调点之间关系,这里可以用来解决源头的问题)

    AOE网的关键路径

    AOV:有向图中,用顶点表示事件,用有向边表示活动之间开始的先后顺序,则称这种有向图为AOV(Activity On Vertex)网络;AOV网络可以反应任务完成的先后顺序(拓扑排序)。

    AOE:在AOV网的边上加上权值表示完成该活动所需的时间,则称这样的AOV网为AOE(Activity On Edge)网,如图: 

     

    如何求AOE网中各事件(节点)和各活动(边)的最早开始时间和最迟开始时间以及工程的关键路径?

    整个活动的完成时间是AOE图中从始点到终点的最长路径的长度,这条路径称为关键路径。关键路径上的活动称作关键活动。

    关键路径求解步骤:

    1. 最早发生时间:从前往后,前驱结点到当前结点所需时间,取最大值。
    2. 最迟发生时间:从后往前,后继结点的最迟发生时间-边权值,取最小值。
    3. 关键路径:最早发生时间和最迟发生时间相同的结点即为关键路径上的节点。
    4. 简单记忆:早晚,先早后晚;在左到右,在右到左;先Max,后min;

    注意:关键路径不一定只有一条。

    1.最早发生时间:从前往后,前驱结点到当前结点所需时间,取最大值。

    解答步骤

    如上图中的节点4有两个前驱结点(节点2和3),节点2到节点4的最早发生时间是a1+a3也就是8,节点3到节点4的最早发生时间是a2+a4也就是12,因为12>8,所以节点4的最早发生时间是12.

    --------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    结束节点(10)的最早发生时间和最迟发生时间相同。

    --------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    2.最迟发生时间:从后往前,后继结点的最迟发生时间-边权值,取最小值。

    如上图中的节点9的最迟发生时间为其后继节点10(只有一个)的最迟发生时间减去a14即24-2=22.

    事件 4 5 6 7 8 9 10
    最早发生时间 0 5 6 12 15 16 17 19 22 24
    最迟发生时间 0 9 6 12 16 20 17 20 22 24

    3.关键路径:最早发生时间和最迟发生时间相同的结点即为关键路径上的节点。

     

      


     

    图的基础知识 

    1.图状结构是我们研究的结构里面最复杂的结构

    我们在讲解数据的逻辑结构时给大家讲到数据结构有如下四个:集合,线性结构,树形结构,图状结构或网状结构。集合只有同属于一个集合;线性结构存在一对一的关系;树形结构存在一对多的关系;图状结构存在多对多的关系

    2.图的相关关系非常复杂,相关概念非常多

    图有有向图,有无向图;有简单图,有多重图;有连通图,非连通图等等等等。如果把图画出来,我们人去看一个图比较简单,我们会有各种各样去分析这个图的方法,计算机不同,他们没有人这么强大的大脑,很多对于图的分析很死板,需要我们把图分析好了再做处理(如果人工智能发展比较好的话,这个问题可能会解决)。

    但是图又很重要,不管是地图,人物关系等,把每个人或者每个地方看作一个点,其他的点都会与之有上千万的联系。所有就都有及其复杂的网络,不管是路径规划,导航提醒还是警察在断案,其实本质上都是图的应用。

    图的定义

    图G由顶点集V和边集E组成,记为G=(V,E),其中V(G)表示图G中顶点的有限非空集;E(G)表示图G中顶点之间的关系(边)的集合。

    注意:线性表可以是空表,树可以是空树,图不可以是空图,图可以没有边,但是至少要有一个顶点

    1.有向图

    若E是有向边(简称弧)的有限集合时,则G为有向图。弧是顶点的有序对,记为<v,w>,其中 v,w 是顶点,v 是弧尾,w 是弧头。称为从顶点v到顶点w的弧。

    有向图

     如上图所示G可表示为:

    1. G=(V,E)

    2. V={1,2,3}  vertex:顶点

    3. E={<1,2>, <2,1>, <2,3>}  edge:边

    2.无向图

    若E是无向边(简称边)的有限集合时,则G为无向图。边是顶点的无序对,记为 (v,w) 或(w,v) ,且有 (v,w) =(w,v) 。其中 v,w 是顶点。

    无向图

    如上图所示,无向图G可表示为:

    1. G=(V, E)

    2. V={1,2,3,4}
    3. E={(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}

    3.简单图多重图

    简单图满足以下两条内容:

    1)不存在重复边

    2)不存在顶点到自身的边

    所以上面的有向图和无向图都是简单图。与简单图相对的是

    多重图,即:两个结点直接边数多于一条,又允许顶点通过同一条边与自己关联。但是我们在数据结构中仅讨论简单图,所以多重图不单独讲解啦。

    4.完全图

    无向图中任意两点之间都存在边,称为无向完全图

    有向图中任意两点之间都存在方向向反的两条弧,称为有向完全图;如示例中的图就不是完全图,但如果没有顶点3和指向顶点3 的边,就是一个完全图。即下图是一个完全图。

    5.子图

    若有两个图G=(V,E),G1=(V1,E2),若V1是V的子集且E2是E的子集,称G1是G的子图。

    右侧这个不是图

    6.连通,强连通、连通图、连通分量(极大连通子图)

    • 在无向图中,两顶点有路径存在,就称为连通的。
    • 若图中任意两顶点都连通,同此图为连通图。
    • 无向图中的极大连通子图称为连通分量

    下图中最后2个是连通分量(极大连通子图),但是这个4都是联通子图,注意连通分量和联通子图

     

    7.强连通图、强连通分量

    在有向图中,两顶点两个方向都有路径,两顶点称为强连通。若任一顶点都是强连通的,称为强连通。

    有向图中极大强连通子图为有向图的强连通分量

    强连通图12345、强连通分量5(极大其实就是其本身)

    8.生成树和生成森林,深度优先生成树和广度优先生成树

    生成树

    连通图进行遍历,过程中所经过的边和顶点的组合可看做是一棵普通树,通常称为生成树。


    连通图及其对应的生成树
    图 1 连通图及其对应的生成树


    如图 1 所示,图 1a) 是一张连通图,图 1b) 是其对应的 2 种生成树。

    连通图中,由于任意两顶点之间可能含有多条通路,遍历连通图的方式有多种,往往一张连通图可能有多种不同的生成树与之对应。

    连通图中的生成树必须满足以下 2 个条件:

    1. 包含连通图中所有的顶点;
    2. 任意两顶点之间有且仅有一条通路;


    因此,连通图的生成树具有这样的特征,即生成树中边的数量 = 顶点数 - 1

    生成森林

    生成树是对应连通图来说

    生成森林是对应非连通图来说的。

    我们知道,非连通图可分解为多个连通分量,而每个连通分量又各自对应多个生成树(至少是 1 棵),因此与整个非连通图相对应的,是由多棵生成树组成的生成森林。


    非连通图和连通分量
    图 2 非连通图和连通分量


    如图 2 所示,这是一张非连通图,可分解为 3 个连通分量(极大连通子图),注意和连通子图区分,其中各个连通分量对应的生成树如图 3 所示:


    生成森林
    图 3 生成森林

    注意,图 3 中列出的仅是各个连通分量的其中一种生成树

    因此,多个连通分量对应的多棵生成树就构成了整个非连通图的生成森林。

     

    深度优先生成树和广度优先生成树

     

    其实在对无向图进行遍历的时候,遍历过程中所经历过的图中的顶点和边的组合,就是图的生成树或者生成森林。



    图 1 无向图
     

    例如,图 1 中的无向图是由 V1~V7 的顶点和编号分别为 a~i 的边组成。当使用深度优先搜索算法时,假设 V1 作为遍历的起始点,涉及到的顶点和边的遍历顺序为(不唯一):



    此种遍历顺序构建的生成树为:




    图 2 深度优先生成树


    由深度优先搜索得到的树为深度优先生成树。

    同理,广度优先搜索成的树为广度优先生成树,图 1 无向图以顶点 V1 为起始点进行广度优先搜索遍历得到的树,如图 3 所示:



    图 3 广度优先生成树

    连通图的生成森林

    非连通图在进行遍历时,实则是对非连通图中每个连通分量分别进行遍历,在遍历过程经过的每个顶点和边,就构成了每个连通分量的生成树。

    非连通图中,多个连通分量构成的多个生成树为非连通图的生成森林。

    1 深度优先生成森林


    图 4 深度优先生成森林


    例如,对图 4 中的非连通图 (a) 采用深度优先搜索算法遍历时,得到的深度优先生成森林(由 3 个深度优先生成树构成)如 (b) 所示(不唯一)。

    非连通图在遍历生成森林时,可以采用孩子兄弟表示法将森林转化为一整棵二叉树进行存储。

     

    运行程序,拿图 4(a)中的非连通图为例,构建的深度优先生成森林,使用孩子兄弟表示法表示为:



    图5 孩子兄弟表示法表示深度优先生成森林

    图中,3 种颜色的树各代表一棵深度优先生成树,使用孩子兄弟表示法表示,也就是将三棵树的树根相连,第一棵树的树根作为整棵树的树根。

     

    2 广度优先生成森林

    非连通图采用广度优先搜索算法进行遍历时,经过的顶点以及边的集合为该图的广度优先生成森林。

    拿图 4(a)中的非连通图为例,通过广度优先搜索得到的广度优先生成森林用孩子兄弟表示法为:



    图6 广度优先生成森林(孩子兄弟表示法)

     

    9.顶点的度、入度和出度

    顶点的度为以该顶点为一个端点的边的数目。

    对于无向图,顶点的边数为度,度数之和是顶点边数的两倍。

    对于有向图,入度是以顶点为终点,出度相反。有向图的全部顶点入度之和等于出度之和且等于边数。顶点的度等于入度与出度之和。

    注意:入度与出度是针对有向图来说的。

    10.边的权和网

    图中每条边上标有某种含义的数值,该数值称为该边的权值。这种图称为带树图,也称作网

    11.路径、路径长度和回路

    两顶点之间的路径指顶点之间经过的顶点序列,经过路径上边的数目称为路径长度。若有n个顶点,且边数大于n-1,此图一定有环。

    12.简单路径、简单回路

    顶点不重复出现的路径称为简单路径。

    除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路。

    13.距离

    若两顶点存在路径,其中最短路径长度为距离。

    14.有向树

    有一个顶点的入度为0,其余顶点的入度均为1的有向图称作有向树。如下图:

     

     

     

    15连通图详解

    连通:图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。

    例如图 1 中,虽然 V1 和 V3 没有直接关联,但从 V1 到 V3 存在两条路径,分别是 V1-V2-V3 和 V1-V4-V3,因此称 V1 和 V3 之间是连通的。


    顶点之间的连通状态示意图
    图 1 顶点之间的连通状态示意图


    连通图:无向图中,如果任意两个顶点之间都能够连通,则称此无向图为连通图

    例如,图 2 中的无向图就是一个连通图,因为此图中任意两顶点之间都是连通的。


    连通图示意图
    图 2 连通图示意图


    连通分量:若无向图不是连通图,但图中存储某个子图符合连通图的性质,则称该子图为连通分量(极大连通子图)

    极大连通子图:由图中部分顶点和边构成的图为该图的一个子图,但这里的子图指的是图中"最大"的连通子图(也称"极大连通子图")。

    如图 3 所示,虽然图 3a) 中的无向图不是连通图,但可以将其分解为 3 个"最大子图"(图 3b)),它们都满足连通图的性质,因此都是连通分量。



    图 3 连通分量示意图

    提示,图 3a) 中的无向图只能分解为 3 部分各自连通的"最大子图"。

    需要注意的是,连通分量的提出是以"整个无向图不是连通图"为前提的,因为如果无向图是连通图,则其无法分解出多个最大连通子图,因为图中所有的顶点之间都是连通的。

    16 强连通图

    强连通图:有向图中,若任意两个顶点 Vi 和 Vj,满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通,也就是都含有至少一条通路,则称此有向图为强连通图。如图 4 所示就是一个强连通图。


    强连通图
    图 4 强连通图


    强连通分量:与此同时,若有向图本身不是强连通图,但其包含的最大连通子图具有强连通图的性质,则称该子图为强连通分量


    强连通分量
    图 5 强连通分量


    如图 5 所示,整个有向图虽不是强连通图,但其含有两个强连通分量。

    总结

    连通图是在无向图的基础上对图中顶点之间的连通做了更高的要求,

    强连通图是在有向图的基础上对图中顶点的连通做了更高的要求

     

     

     

     

     

    展开全文
  • 1. 对有向图G进行DFS,记录时间戳Ai,形成森林W1 2. 将G中所有边反向形成G' 3.按时间戳由大到小对G'进行DFS,形成新森林W2. 由此,形成的每棵树都是一个极大连通子图。...

    1. 对有向图G进行DFS,记录时间戳Ai,形成森林W1

    2. 将G中所有边反向形成G'

    3.按时间戳由大到小对G'进行DFS,形成新森林W2.

    由此,形成的每棵树都是一个极大强连通子图。

    展开全文
  • 极大强连通分量的Tarjan算法 首先,在有向图G中,如果两个顶点vi,vj间(vi<>vj)都有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个...非强连通图有向图的极大连通子图,称为强连通...

                                 求极大强连通分量的Tarjan算法

       首先,在有向图G中,如果两个顶点vi,vj间(vi<>vj)都有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components),如果一个强连通分量中不再能加入任何一个顶点,则这个强连通分量是一个极大强连通分量。

       由上面的定义,可以知道,强连通分量中各点可以互相到达,则我们可以找到每个极大强通分量的“根结点”,再通过从底层节点向上推的方法求出一个极大强连通分量,所以关键在于求出根结点,所以这里加入两个数组,dfn,和low,其中dfn为搜索序号,表示第几个搜到该点,而low表示该节点向上最远可以回到的节点,显然当一个节点的dfn[i]=low[i]时,它就是这一个极大强连通分量的根,之后搜索到的点包含在这个极大强连通分量中,下面就要考虑一下如何取出这个极大强连通分量,于是维护一个栈,每搜索一个节点,就把它压入栈中,那么当我们发现根结点时,在它后面入栈的都是它代表的极大强连通分量中的节点,只需要弹栈直到根结点出栈即可。

    【程序伪代码】

       Dfs(k)

         Inc(time);    //搜索的序号变量

         Low[x]=time   //当前节点最远可以回到的点的时间戳

         Dfn[x]=time    //时间戳

         Push(x)   //入栈

         Instack[x]=true   //将x节点在栈中标记为真

         For i=x的所有儿子

           If 没有访问过 x   //还没有被搜索过

             Dfs(i)

             Low[x]=Min(low[x],low[i])

    //搜索之后发现儿子节点能到达的最早时间戳比x要早,则更新 

           Else //已经搜索过

             If  (i在栈中)and(dfn[i]<low[x])

    //在栈中说明属于同一个强连通分量,而如果时间戳更早,显然需要更新

               Low[x]=dfn[i]

          If dfn[x]=low[x] //如果该节点是一个强连通的根结点

            Inc(num) //强连通数增加

            While true do

              Pop //弹出该强连通的结点

              Instack[stack[top]]=false//在栈内标记为假

              If stack[top+1]=x//如果根结点已经输出

                Break //跳出

    View Code
     1 program targan(input,output);
    2 type
    3 node = ^link;
    4 link = record
    5 goal : longint;
    6 next : node;
    7 end;
    8 var
    9 stack : array[1..1000] of longint;
    10 l : array[1..1000] of node;
    11 instack : array[1..1000] of boolean;
    12 dfn : array[1..1000] of longint;
    13 low : array[1..1000] of longint;
    14 ans : array[1..1000] of longint;
    15 num,e : longint;
    16 m,n,top,cnt : longint;
    17 procedure add(x,y: longint );
    18 var
    19 t : node;
    20 begin
    21 new(t);
    22 t^.goal:=y;
    23 t^.next:=l[x];
    24 l[x]:=t;
    25 end; { add }
    26 procedure init;
    27 var
    28 i,x,y : longint;
    29 begin
    30 readln(n,m);
    31 cnt:=0;
    32 for i:=1 to n do
    33 l[i]:=nil;
    34 fillchar(instack,sizeof(instack),false);
    35 for i:=1 to m do
    36 begin
    37 readln(x,y);
    38 add(x,y);
    39 end;
    40 end; { init }
    41 procedure dfs(x :longint );
    42 var
    43 t : node;
    44 begin
    45 inc(cnt);
    46 dfn[x]:=cnt;
    47 low[x]:=cnt;
    48 inc(top);
    49 stack[top]:=x;
    50 instack[x]:=true;
    51 new(t);
    52 t:=l[x];
    53 while t<>nil do
    54 begin
    55 if dfn[t^.goal]=0 then
    56 begin
    57 dfs(t^.goal);
    58 if low[t^.goal]<low[x] then
    59 low[x]:=low[t^.goal];
    60 if dfn[t^.goal]<low[x] then
    61 low[x]:=dfn[t^.goal];
    62 end
    63 else
    64 if (instack[t^.goal]=true)and(dfn[t^.goal]<low[x]) then
    65 begin
    66 low[x]:=dfn[t^.goal];
    67 end;
    68 t:=t^.next;
    69 end;
    70 if low[x]=dfn[x] then
    71 begin
    72 inc(num);
    73 while true do
    74 begin
    75 ans[stack[top]]:=num;
    76 instack[stack[top]]:=false;
    77 dec(top);
    78 if stack[top+1]=x then
    79 break;
    80 end;
    81 end;
    82 end; { dfs }
    83 procedure print;
    84 var
    85 i : longint;
    86 begin
    87 for i:=1 to n do
    88 write(ans[i],'');
    89 end; { print }
    90 begin
    91 init;
    92 for e:=1 to n do
    93 if dfn[e]=0 then
    94 dfs(e);
    95 print;
    96 End.

    转载于:https://www.cnblogs.com/neverforget/archive/2011/10/13/2209611.html

    展开全文
  • 非强连通图有向图的极大连通子图,称为强连通分量(strongly connected components)。朴素算法根据定义我们不难想到, 对同一张图同时进行正反两次遍历, 对两次的遍历结果取交集, 这里得到的便是强连通图。
  • 1、强连通:如果两个顶点u和v之间...4、极大连通子图:G是一个极大连通子图,当且仅当G是一个强连通子图,且不存在另一个强连通子图G‘使得G是G’的真子集。   一、kosaraju算法 思路:(基于两次dfs有向连...
  • 首先需要了解什么是连通图、无向连通图、极大连通子图等概念,这些概念都来自数据结构-图,这里简单介绍一下。 下图是连通图和非连通图,都是无向的,这里不扩展有向图: 连通分量(connected ...
  • tarjan求极大连通分量

    2016-02-29 08:14:07
    Tarjan算法的用途之一是,求一个有向图G=(V,E)里极大连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话,那么这个强连通分量就是极大连通分量...
  • 在有向图G中,如果两个顶点vi,vj间有一条从vi到vj的...有向图的极大连通子图(即:一个图的(强)连通子图,并且加入任何一个不在它的点集中的点都会导致它不再(强)连通。),称为强连通分量(strongly connected c
  • 求无向图连通图点双连通分支

    千次阅读 2016-08-22 15:23:35
    点双连通分支:不包含割点的极大连通子图 算法思路: 建立一个栈,存储当前双连通分支,在搜索图时,每找到一条树枝边或反向边(连到树中祖先 的边),就把这条边加入栈中。如果遇到某树枝边(u,v) 满足dfn(u)...
  • 边双连通分支:不包含桥的极大连通子图 算法思路: 只需在求出所有的桥以后,把桥边删除,原图变成了多个连通块,则每个连通块就是一个 边双连通分支。桥不属于任何一个边双连通分支,其余的边和每个顶点都属于且...
  • 一、解释在有向图G中,如果两个顶点...非强连通图有向图的极大连通子图,称为强连通分量(strongly connected components)。 求解有向图的强连通分量算法有很多,例如Kosaraju,Gabow和Tarjan算法,其中Gabow和Tarja
  • Tarjan算法应用之强连通分量

    千次阅读 2017-02-23 11:43:32
    Tarjan是一个对图的分析的强有力的算法,主要应用有:有向图的强连通分量、无向图的割点桥与双连通分量、LCA...一个图的极大连通子图称为改图的强连通分量。Tarjan算法求解强连通分量通过Tarjan算法可以得到每个点属于
  • 本文是《刘汝佳算法竞赛》的双连通分量... 极大连通子图:对于一个连通图,极大连通子图就是其连通分量也就是 其本身,非连通图有多个连通分量则就有多个极大连通子图。主要理解的是极大,极大指的是这个连通子图不...
  • 连通分量 tarjan算法

    2017-03-29 20:31:30
    强连通分量 tarjan算法(转) [有向图强连通分量]在有向图G中,...非强连通图有向图的极大连通子图,称为强连通分量(strongly connected components)。下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两
  • 连通分量 Tarjan算法

    2017-08-04 09:43:38
    什么是Tarjan算法!!!! Tarjan算法:一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法。这时候你可能会问什么是强连通,什么是强连通分量?...有向图的极大连通子图,称为强连通分量(Strongly Con
  • (绘图什么真辛苦) 强连通分量: 在有向图 G 中。若两个顶点相互可达,则称两...非强连通图有向图的极大连通子图。称为强连通分量(strongly connected components)。比方上面这幅图( a, b, e ), ( d, c...
  • 前言 做Tarjan\tt TarjanTarjan 的题,屑教练给的课件实在是太La Ji了,于是重新整理一下 Tarjan\...非强联通图的极大强联通子图称作强联通分量。Tarjan\tt TarjanTarjan 算法就是用于找有向图的强联通分量。 首先,有
  • 连通图的算法

    2014-06-08 12:55:04
    有向图强连通分量的Tarjan算法 [有向图强连通分量] ...非强连通图有向图的极大连通子图,称为强连通分量(strongly connected components)。 下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1
  •   强连通分量: 如果一个有向图G不是强连通图,那么可以把他分成多个子图,其中每个子图的内部是强连通的,而且这些子图已经扩展到最大,不能与子图外的任意点强连通,称这样的一个 “极大连通子图是G的一个...
  • 连通分量求解算法

    千次阅读 2018-10-23 20:32:14
    有向图的极大连通子图就是有向图的强连通分量(Strongly Conneted Component)。 强连通有如下性质: (1)自反性:任意顶点v和自身是强连通的。 (2)对称性:如果v和w是强连通的,那么w和v也是强连通的。 ...
  • 非强连通图的极大连通子图称为强连通分量。 这里,极大连通子图可以理解为一个子图是强连通图,且它的任意子图都不是强联通。 我们来看下面几张图。 这是强连通图。 这是强连通分量。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 483
精华内容 193
关键字:

极大连通子图算法