精华内容
下载资源
问答
  • 强连通分量求解算法
    千次阅读
    2018-10-23 20:32:14

    强连通分量

    有向图中,如果顶点v和w相互可达,则称这两个顶点之间强连通。一幅图中任意两点之间强连通则称这幅图为强连通图。有向图的极大强连通子图就是有向图的强连通分量(Strongly Conneted Component)。

    强连通有如下性质:

    (1)自反性:任意顶点v和自身是强连通的。

    (2)对称性:如果v和w是强连通的,那么w和v也是强连通的。

    (3)传递性:如果v和w是强连通的且w和x也是强连通的,那么v和x也是强连通的。

    强连通分量即是基于强连通的性质,将相互均为强连通的顶点划分在一起构成的最大子集。强连通性是非常重要的抽象,它突出了相互关联的几组顶点(强连通分量),对事物的分类有很大帮助。

    Kosaraju算法

    Kosaraju算法是求解有向图连通分量较简单的算法,它需要用到原图及其转置图(转置图即所有边的方向与原图一一对应且相反)来进行深度优先搜索。既然强连通是指顶点之间相互可达,那么我们只需要求出原图的连通分量(求解图的连通分量),然后在其转置图中再执行搜寻,原图和转置图对应的每一个连通分量的交集就是我们要求的强连通分量。

    在对转置图进行搜寻的过程中,起始顶点的选择需要有所限制,否则可能搜寻到其他连通分量中,这是不允许的(强连通分量只能存在于单个强连通图,即单棵树中)。Kosaraju算法巧妙地选择了“最晚离开的”顶点,因为对任意顶点v和w假设是强连通的,在第一次搜寻过程中已经得到了v→w,那么就需要证明存在路径使得w→v,即证明转置图中存在路径使得v→w。在对转置图进行深度优先搜索的过程中,dfs(w)肯定在dfs(v)之前就结束了,且在原图中存在v→w即转置图中存在w→v,所以只可能有唯一一种情况——在转置图中对dfs(w)的调用必然在dfs(v)之前结束,因此可以证明该算法思想的正确性。

    对于“最晚离开的”顶点,我们联想栈调用的特性就可以知道,对原图的逆后序遍历得到的顶点顺序就是要对转置图进行深度优先搜索时应遵循的起始顶点顺序。再结合拓扑排序的特点,如果我们把求出来的每个强连通分量收缩成一个点,并且用求出每个强连通分量的顺序来标记收缩后的节点,那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。

    综上,Kosaraju算法的执行流程主要是以下两步:

    (1)对原图进行深度优先搜索,得到原图的逆后序遍历的顶点顺序。

    (2)以(1)中的顶点顺序作为对转置图进行深度优先搜索的起始顶点选择顺序,对转置图进行遍历,删除(或标记)能够遍历到的顶点,这些顶点构成一个强连通分量。当还有顶点没有删除或标记时回到(1)继续执行,否则结束。

    /*
     
    struct UndirectedGraph
    {
        size_t V, E; //V表示顶点数,E表示边数
        map<int, forward_list<int>> adj;
    };
    
    */
    
    void get_post_dfs(const DirectedGraph &g, vector<int> &visited, vector<int> &post_order, int v)
    {
        visited.at(v) = 1;
        for (const int &i : g.adj.at(v).second)
        {
            if (visited.at(i) == 0)
            {
                dfs(g, visited, post_reverse_order, i);
            }
        }
        post_reverse_order.push_back(v);
    }
    
    void dfs(const DirectedGraph &g, vector<int> &visited, vector<pair<int, int>> &cc, int v)
    {
        if (visited.at(v) == 1)
        {
            continue;
        }
        g.adj.at(v) = 1;
        for (const int &i : g.adj.at(v))
        {
            if (visited.at(i) == 0)
            {
                cc.push_back(make_pair(v, i));
                dfs(g, visited, cc, i);
            }
        }
    }
    
    vector<vector<pair<int, int>>> FindStronglyConnectedComponent(const DirectedGraph &g, const DirectedGraph &gt) //gt是g的转置图
    {
        vector<vector<pair<int, int>>> ans;
        vector<int> visited(g.V);
        vector<int> post_order;
        get_post_dfs(g, visited, post_order, (*g.adj.cbegin()).first); //得到原图的后序遍历序列(反向即为逆后序)
    
        //标记数组初始化
        for (int &i : visited)
        {
            i = 0;
        }
    
        //对转置图DFS得到强连通分量
        for (auto ite = post_order.crbegin(); ite != post_order.crend(); ++ite)
        {
            vector<pair<int, int>> cc;
            dfs(gt, visited, cc, *ite);
            ans.push_back(move(cc));
        }
        return ans;
    }

     该算法需要进行两次DFS,效率并不算高。对于比较庞大的有向图来说,递归调用容易导致栈溢出,可以将DFS部分用非递归代码来实现。

    Tarjan算法

    Tarjan算法基于强连通分量的一个性质:任何一个强连通分量,必定是对原图进行深度优先搜索得到的子树。所以我们只需要找出每个子树(强连通分量)的根,然后从这棵子树的最底层开始一个一个拿出强连通分量的顶点即可。

    现在关键在于如何找出连通分量的根以及找到根后如何拿出强连通分量的顶点。

    根与其所在连通分量不同之处在于它能够到达其所在连通分量的其他顶点,反之也可达,但不在这个连通分量的顶点到达不了这个根。Tarjan算法的思想是维护两个数组来寻找连通分量的根,其中一个数组dfn用来记录深度优先搜索访问顶点的顺序,另一个数组low则记录一个顶点能到达的最大子树的根(即dfn值最小的顶点)。当一个顶点的dfn值与low值相等时即说明它就是一个连通分量的根。因为如果它不是强连通分量的根,那么它一定是属于另一个强连通分量,而且不是根,那么就存在包含当前顶点的到根的回路,可知low一定会被更改为一个比dfn更小的值,而不是相等。

    至于如何拿出强连通分量,如果当前节点为一个强连通分量的根,那么它的强连通分量一定是以该根为根节点的(剩下节点)子树。在深度优先遍历的时候维护一个栈,每次访问一个新节点,就压入栈。这样,由于当前节点是这个强连通分量中最先被压入堆栈的,那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。可以用反证法证明这个做法的正确性:假设一个节点在当前节点压入堆栈以后压入并且还存在,同时它不属于该强连通分量,那么它一定属于另一个强连通分量,但当前节点是它的根的祖宗,那么这个强连通分量应该在此之前已经被拿出。

    综上,Tarjan算法的整体流程如下:

    对图进行深度优先遍历,用序号标记遍历到的顶点的先后顺序(对dfn数组赋值)并将新顶点压入栈中,在回溯过程中维护low数组,标记当前顶点能到达的最大子树的根(即dfn值最小的顶点)。在回溯过程中遇到dfn值与low值相等的即为当前连通分量的根。找到根后,此时栈中元素就是该连通分量的顶点,将其一个个拿出即可。

    
    void Tarjan(DirectedGraph &g, vector<vector<int>> &scc_set, vector<int> &visited, vector<int> &dfn, vector<int> &low, vector<int> &in_stack, stack<int> &st)
    {
        dfn[u] = low[u] = ++cnt;
        st.push(u);
        in_stack[u] = 1;
        for (const auto &v : g.adj.at(u))
        {
            if (!visited[v])
            {
                Tarjan(g, v);
                low[v] = min(low[u], low[v]);
            }
            else if (in_stack[v])
            {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u])
        {
            vector<int> scc;
            do
            {
                v = st.top();
                st.pop();
                scc.push_back(v);
                in_stack[v] = 0;
            } while (u != v);
            scc_set.push_back(move(scc));
        }
    }
    
    vector<vector<int>> FindStronglyConnectedComponent(DirectedGraph &g)
    {
        static int cnt = 0;
        vector<int> dfn(g.V);    //DFS访问顶点的顺序
        vector<int> low(g.V);    //当前顶点能到达的最大子树的根
        vector<int> visited(g.V);    //访问标记
        stack<int> st;    //存放强连通分量顶点的栈
        vector<int> in_stack(g.V);    //判断顶点是否在栈中
        vector<vector<int>> scc_set;
        for (auto ite = g.adj.cbegin(); ite != g.adj.cend(); ++ite)
        {
            Tarjan(g, scc_set, visited, dfn, low, in_stack, st);
        }
        return scc_set;
    }
    

    运行Tarjan算法的过程中,每个顶点都被访问了一次,且只进出了一次栈,每条边也只被访问了一次,所以该算法的时间复杂度为O(V+E)。在大型连通图中,为了避免递归深度过大而导致效率降低和栈溢出,可以将第一个DFS也改为栈来实现。

    同时在分析Tarjan算法的过程中我们也可以发现,这个算法还可以用于求解无向图的割边桥,已经求解最近公共祖先(LCA)。

     

    更多相关内容
  • 实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...
  • 使用Tarjan算法进行快速计算强连通分量,C++语言实现。
  • 为了满足棒材计数在工业生产的实际应用需求,提出了一种基于提取连通分量的算法,以实现目标棒材计数区域的自动定位,并对定位的区域采用提取连通分量算法实现对轮廓的标注,最后提出了一种区域轮廓周长的校正方法,...
  • 在键盘上输入有向图,对任意给定的图(顶点数和边数自定),建立它的邻接表并输出。然后判断该图是否连通。如果是连通图,求出该图的所有强连通分量并输出字符
  • 强连通分量算法

    2015-09-18 09:35:20
    一:无向图的强连通分量算法 向图的连通分量就都是连通分量。无向图的连通分量就是用DFS算法顺序遍历邻接表时顺道干点小动作,写下代码更直观一些: #define maxN 1024 int marked[maxN];//用于记录某个点...

    一:无向图的强连通分量算法

    向图的连通分量就都是强连通分量。无向图的强连通分量就是用DFS算法顺序遍历邻接表时顺道干点小动作,写下代码更直观一些:

    #define maxN 1024
    int marked[maxN];//用于记录某个点是否被访问过,0为没有被临幸过,1为被临幸过
    int id[maxN];//记录每个点所属的连通分量
    int count;//记录连通分量总数目
    void cc(graph *g){
        int i;
        memset(marked,0,sizeof(marked));
        memset(id,0,sizeof(id));
        count=0;
        for(i=0;i<g->V;i++){//之所以这里用循环就是因为g指向的无向图可能不是一个连通图,而是由多个连同分量组成
            if(!marked[i]){dfs(g,i); count++;}
        }
    }
    
    void dfs(graph *g,int v){
        graphNode *t;
        marked[v]=1;
        id[v]=count;
        t=g->adjlist[v].next;//t指向v的邻接点
        while(t){
            if(!marked[t->key]){dfs(g,t->key);}

    这里是重点,就是你发现v到t->key有路径就把它算到跟自己在一个连通分量里了,这里有一个隐性前提,就是你提前知道t->key一定可以到v,所以你发现v可以到t->key的时候,你毫不犹豫把它算为跟自己一伙儿的了。


    二:有向图的强连通分量的三种算法

    Kosaraju Algorithm

    如果不仅需要统计强连通分量的个数,还要将强连通分量缩点,则需要用到今天介绍的Kosaraju Algorithm。它的具体步骤如下:

    • 对原图 G 进行DFS并将出栈顺序进行逆序,得到的顺序就是拓扑序列。
    • 将原图的每一条边反向,得到反图 G
    • 按照第一步生成的拓扑序列的顺序再对反图 G 进行DFS染色,染成同色的就是一个强连通分量。(注意:这个dfs的访问顺序是按照拓扑排序的顺序,想想为啥捏么?因为加入有a--->b--->c,先访问a,此时我们假定a可以到b,当遍历1到n时,如果发现b能到a,则a和b为连通分量)
    该算法具有一个性质:如果我们把求出来的每个强连通分量缩成一个点,并且用求出每个强连通分量的顺序来标记收缩后的结点,那么这个顺序就是强连通分量缩点后所形成的有向无环图的拓扑序列

    #include <iostream>
    #include <cstring>
    #include <stack>
     
    using namespace std;
     
    const int MAX = 10240;
     
    int N, M, nCnt = 0;
    int pMap[MAX][MAX], pColor[MAX];
    stack<int> S;	// 储存拓扑序列
     
    void dfs1(int x);	// 原图DFS
    void dfs2(int x);	// 反图DFS
    void Kosaraju();
     
    int main()
    {
    	cin >> N >> M;
    	memset(pMap, 0, sizeof(pMap));
    	for(int i = 1; i <= M; i++)
    	{
    		int s, e;
    		cin >> s >> e;
    		pMap[s][e] = 1;		// 有向图
    	}
    	Kosaraju();
    	return 0;
    }
     
    void Kosaraju()
    {
    	memset(pColor, 0, sizeof(pColor));
    	for(int i = 1; i <= N; i++)	// DFS原图求出拓扑序列
    	{
    		if(!pColor[i])
    		{ dfs1(i); }
    	}
     
    	memset(pColor, 0, sizeof(pColor));
    	while(!S.empty())	// 按照拓扑序列DFS反图
    	{
    		int x = S.top(); S.pop();
    		if(!pColor[x])
    		{
    			nCnt++;		// 找到一个强连通分量
    			dfs2(x);
    		}
    	}
    	cout << "The number of SCC is " << nCnt << endl;
    }
     
    void dfs1(int x)
    {
    	pColor[x] = 1;	// 染色
    	for(int i = 1; i <= N; i++)
    	{
    		if(pMap[x][i] == 1 && !pColor[i])
    		{ dfs1(i); }
    	}
    	S.push(x);	// 加入拓扑序列
    }
     
    void dfs2(int x)
    {
    	pColor[x] = nCnt;	// 属于第几个强连通分量
    	for(int i = 1; i <= N; i++)
    	{
    		if(pMap[i][x] == 1 && !pColor[i])	// 原邻接矩阵的对称矩阵为反图
    		{ dfs2(i); }
    	}
    }

    Tarjan算法

    此算法以一个有向图作为输入,并按照所在的强连通分量给出其顶点集的一个划分。图中的每个结点只在一个强连通分量中出现,即使是在有些结点单独构成一个强连通分量的情况下(比如图中出现了树形结构或孤立结点)。

    算法的基本思想如下:任选一结点开始进行深度优先搜索(若深度优先搜索结束后仍有未访问的结点,则再从中任选一点再次进行)。搜索过程中已访问的结点不再访问。搜索树的若干子树构成了图的强连通分量。

    结点按照被访问的顺序存入中。从搜索树的子树返回至一个结点时,检查该结点是否是某一强连通分量的根结点(见下)并将其从栈中删除。如果某结点是强连通分量的根,则在它之前出栈且还不属于其他强连通分量的结点构成了该结点所在的强连通分量。

    根结点的性质[编辑]

    算法的关键在于如何判定某结点是否是强连通分量的根。注意“强连通分量的根”这一说法仅针对此算法,事实上强连通分量是没有特定的“根”的。在这里根结点指深度优先搜索时强连通分量中首个被访问的结点。

    为找到根结点,我们给每个结点v一个深度优先搜索标号v.index,表示它是第几个被访问的结点。此外,每个结点v还有一个值v.lowlink,表示从v出发经有向边可到达的所有结点中最小的index,v.lowlink为v或v的子树能够追溯到的最早的栈中节点的次序号。显然v.lowlink总是不大于v.index,且当从v出发经有向边不能到达其他结点时,这两个值相等。v.lowlink在深度优先搜索的过程中求得,v是强连通分量的根当且仅当v.lowlink = v.index

    algorithm tarjan is
      input: 图 G = (V, E)
      output: 以所在的强连通分量划分的顶点集
    
      index := 0
      S := empty    // 置栈为空
      for each v in V do
        if (v.index is undefined)
          strongconnect(v)
        end if
    
      function strongconnect(v)
        // 将未使用的最小index值作为结点v的index
        v.index := index
        v.lowlink := index
        index := index + 1
        S.push(v)
    
        // 考虑v的后继结点
        for each (v, w) in E do
          if (w.index is undefined) then
            // 后继结点w未访问,递归调用
            strongconnect(w)
            v.lowlink := min(v.lowlink, w.lowlink)
          else if (w is in S) then
            // w已在栈S中,亦即在当前强连通分量中
            v.lowlink := min(v.lowlink, w.index)
          end if
    
        // 若v是根则出栈,并求得一个强连通分量
        if (v.lowlink = v.index) then
          start a new strongly connected component
          repeat
            w := S.pop()
            add w to current strongly connected component
          until (w = v)
          output the current strongly connected component
        end if
      end function


    第三种方法待续。。。。。


    展开全文
  • 强连通分量(scc):图 G G G 不是一个连通图,但其子图 G ′ G^\prime G′ 是 G G G 的最大连通子图,则称 G ′ G^\prime G′ 为一个强连通分量 tarjan算法就是一个可以找出图中所有强连通分量的方法。...

    强连通分量(Tarjan算法)

    • 前言

      第一件事:没事不要while(m–),会带来不幸
      第二件事:看博客先看看评论,如果博主他写错了的话…

    • 简介

      先讲几个定义

      • 强连通:两个顶点 u u u v v v 可以相互到达

      • 强连通图:图中的任意两个顶点可以相互到达(就是图中有一块边缠在一起)

      • 强连通分量(scc):图 G G G 不是一个强连通图,但其子图 G ′ G^\prime G G G G 的最大强连通子图,则称 G ′ G^\prime G 为一个强连通分量

      tarjan算法就是一个可以找出图中所有强连通分量的方法。

    • 原理

      维护两个数组:
      dfn[] : 时间戳。深搜这个图,dfn[i] 表示 第 i 个点是什么时候被搜到的
      low[] : 深搜的这个图里正常的话肯定有环,low[i] 就表示第 i 个点属于哪个时间戳节点的环里
      (表达很抽象自己悟233,或者看后面图解过程)
      同时手打一个栈,把搜过的点压进栈

    在这里插入图片描述

    如图,从点1开始深搜,给搜过的点打上时间戳dfn,初始化low,stack = 1 3 2

    在这里插入图片描述

    当搜到点2时,下一个搜到了1,1已经被搜过了(已经被搜过了看 dfn[] != 0 ),且1在栈内
    修改 low[2] = min(low[2], dfn[1]); (注意绕回根节点的时候是将该点的low和根节点的dfn比较)

    在这里插入图片描述

    此时点2搜完了,回溯到点3. 点3是回溯来的修改low肯定是和点2的low比较
    即修改 low[3] = min(low[2], low[3]);

    在这里插入图片描述

    点3继续深搜,给4,5打上时间戳,同时入栈4,5,此时栈内有 stack = 1 3 2 4 5

    在这里插入图片描述

    5继续搜,搜到4,点4已经搜过且在栈内,修改low[5] = min(low[5], dfn[4])
    回溯到点4,点4修改low[4] = min(low[4], low[5])

    在这里插入图片描述

    下一步是关键,此时点4已经搜完,即将退出回溯到点3,而我们发现点4的dfn[4] == low[4]
    也就是说点4就是一块强连通分量的节点!
    此时开始出栈,直到点4出栈为止。即剩下的stack = 1 3 2
    我们给出栈的点全部打上scc标记,即

    在这里插入图片描述

    待出栈结束,回溯到点3
    点3此时修改low[3] = min(low[3], low[4]), 显然low3不变
    继续回溯到点1,发现点1已经搜完,且dfn[1] == low[1]
    同上述点4,出栈打标记

    在这里插入图片描述

    此时栈已经空了,从1开始深搜已经结束,但很明显还有一个6没有被搜过
    可以很明显看出上述算法不一定能走遍整个图,所以需要以每一个点为起点深搜一次,判断标准是是否被搜过(即dfn[] != 0)

    for(int i = 1; i <= n; i++){
    	if(!dfn[i]) tarjan(i);
    }
    

    在坚持一下,马上就要结束了
    此时其实还有最后问题没有解决,就是那个栈有什么用,让我们继续深搜点6
    dfn[6] = 6, low[6] = 6,下一个要搜的点是2
    2已经被搜过,但是和上面都不一样的地方来了!2此时不在栈里
    所以我们不用更新low[6],直接结束搜点6.

    最后,low[6] == dfn[6], 打上scc标记,整个算法就讲完了。

    在这里插入图片描述

    • 代码

      用链式前状星存图,手打栈(当然stl也可以)

      void tarjan(int x) {
          sta[++top] = x;	//手打入栈
          instack[x] = 1;	
          
          dfn[x] = low[x] = ++cnt; //初始化dfn和low
          
          //核心代码,深搜这个点
          for (int i = head[x]; i; i = edge[i].next) {
              int to = edge[i].to;
              if(!dfn[to]){	//如果下一个点没有被搜过,
                  tarjan(to);	//继续深搜
                  low[x] = min(low[x], low[to]); //更新low
              }
              else if(instack[to]){ //如果下一个点已经被搜过,看他在不在栈里
                  low[x] = min(low[x], dfn[to]); //更新low
              }
          }
          //如果dfn==low,即找完了一整块强连通分量,出栈+标记
          if(dfn[x] == low[x]){
              tot++;//计数器++,第几个强连通分量
              while(sta[top+1]!=x){ 		//不加1的话x这个点不会被出栈
                  scc[sta[top]] = tot;	//打标记
                  instack[sta[top--]] = 0;//出栈
              }
          }
      }
      
    • 例题:P3387 【模板】缩点

      #define _CRT_SECURE_NO_WARNINGS
      #include <bits/stdc++.h>
      using namespace std;
      #define ll long long
      
      const int N = 1e4 + 5;
      const int M = 1e5 + 5;
      int read() {
          int x = 0, f = 1; char ch = getchar();
          while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
          while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
          return x * f;
      }
      ///
      struct Edge {
          int to;
          int from;
          int next;
      }edge[M], edge2[M];
      int head[N], head2[N];
      int cnt;
      void add_edge(int u, int v) {
          edge[++cnt].to = v;
          edge[cnt].from = u;
          edge[cnt].next = head[u];
          head[u] = cnt;
      }
      void add_edge2(int u, int v) {
          edge2[++cnt].to = v;
          edge2[cnt].from = u;
          edge2[cnt].next = head2[u];
          head2[u] = cnt;
      }
      
      int w[N];
      int low[N];
      int dfn[N];
      int scc[N];
      int sum[N];
      int tot;//计数有几个强连通分量
      
      //手打栈
      bool instack[N];
      int sta[N];
      int top;
      
      void tarjan(int x) {
          sta[++top] = x;
          instack[x] = 1;
          dfn[x] = low[x] = ++cnt;
          for (int i = head[x]; i; i = edge[i].next) {
              int to = edge[i].to;
              if(!dfn[to]){
                  tarjan(to);
                  low[x] = min(low[x], low[to]);   
              }
              else if(instack[to]){
                  low[x] = min(low[x], dfn[to]);
              }
          }
          if(dfn[x] == low[x]){
              tot++;
              while(sta[top+1]!=x){
                  scc[sta[top]] = tot;
                  sum[tot] += w[sta[top]];
                  instack[sta[top--]] = 0;
              }
          }
      }
      
      
      int dp[N];
      void dfs(int x) {
          if (dp[x]) return;
          dp[x] = sum[x];
          int sum = 0;
          for (int i = head2[x]; i; i = edge2[i].next) {
              int to = edge2[i].to;
              if (!dp[to]) 
                  dfs(to);
              sum = max(sum, dp[to]);
          }
          dp[x] += sum;
      }
      
      int main()
      {
          int n, m;
          scanf("%d%d", &n, &m);
          for (int i = 1; i <= n; i++) {
              w[i] = read();
          }
      
          for(int i = 0; i < m; i++){
              int a = read();
              int b = read();
              add_edge(a, b);
          }
          cnt = 0;//偷懒给tarjan复用
      
          for (int i = 1; i <= n; i++) {
              if (!dfn[i]) 
                  tarjan(i);
          }
      
          //建新的图edge2,新图是DAG有向无环图
          cnt = 0;//偷懒x2
          for (int i = 1; i <= m; i++) {
              int u = edge[i].from;
              int v = edge[i].to;
              if(scc[u] != scc[v])
                  add_edge2(scc[u], scc[v]);
          }
      
          //深搜这个edge2
          int ans = 0;
          for (int i = 1; i <= tot; i++) {
              if (!dp[i]) {
                  dfs(i);
                  ans = max(ans, dp[i]);
              }
          }
          
          printf("%d\n", ans);
          system("pause");
          return 0;
      }
      
    • 尾声

      感觉这个应该是最详细的tarjan博客了23333
      最后提醒两点:看博客注意看评论会有大牛指出错误,不要对着错博客研究半天怎么都写不对2333
      第二个,上面的代码94行画图的时候,老老实实for(int i = 0;i < m; i++),别嫌那么一点点麻烦来个while(m--),108行第二次画图的时候就啥都没干了

    展开全文
  • 算法导论-证明强连通分量算法

    千次阅读 2017-11-28 11:21:10
    强连通分量:有向图G=(V,E)G=(V,E)的强连通分量是一个最大结点集合C⊆VC\subseteq V,∀u,v∈C\forall u,v\in C,u和v是可以相互到达的。 算法伪代码 STRONGLY-CONNECTED-COMPONENTS(G) call DFS(G) to compute ...
    • 概念
      强连通分量:有向图 G=(V,E) 的强连通分量是一个最大结点集合 CV u,vC ,u和v是可以相互到达的。
    • 算法伪代码
      STRONGLY-CONNECTED-COMPONENTS(G)
    call DFS(G) to compute finishing times u.f for each vertex u
    compute GT
    call DFS(GT),but in the main loop of DFS,consider the vertices in order of decreasing u.f(as computed in line 1)
    output the vertices of each tree in the depth-first forest formed in line 3 as a separate strongly connected component
    • 证明

      引理1:设 C,C 为有向图 G=(V,E) 的两不同连通分量。
      uvC,uvCuuvv

      证明:(反证法)
      vvuuvvvu

      因此, uv 可相互到达,与 C,C 是不同的连通分量的假设矛盾。

      概念:
      1 u.du.f 分别是STRONGLY-CONNECTED-COMPONENTS的第一行算出的每个结点的发现时间和完成时间。
      2 对于结点集 UG.V ,定义 d(U)=minuU{u.d},f(U)=maxuU{u.f}
      引理2:设 C,C 为有向图 G=(V,E) 的两不同连通分量。
      (u,v)G.EuC,vCf(C)>f(C)

      证明:(分类讨论)
      根据深度优先搜索算法中最早发现的结点在哪个强连通分量里分类。
      第一种情况: d(C)<d(C)
      设x为C中最早被发现的结点。 x.d pCC ,p是白色的。 记为I。
      I pC 都有一条全部由白色结点组成的路径 xp 。记为II。
      由I和 (u,v)G.EpG 都有一条全部由白色结点组成的路径 xuvp 。记为III.
      由II和III pCC 都有一条全部由白色结点组成的路径 xp p是x的后代 22.8x.f>p.fx.f=f(C)>f(C)
      其中的推论22.8是:在有向或无向图G的深度优先森林中,
      结点v是结点u的后代 u.d<v.d<v.f<u.f
      第二种情况: d(C)>d(C)
      设y为 C 中最早被发现的结点。 C 中所有结点都是白色的。 pC 存在一条白色路径 yp p是y的后代 22.8y.f>p.fy.f=f(C)
      (u,v)G.E1 不可能存在一条从 CC 的路径。
      y.d 时刻连通分量C中的所有结点都是白色,所以 pC,p.f>y.ff(C)>f(C)

      由引理2可以得到推论1
      CC 为有向图 G=(V,E) 的两个不同的强连通分量,
      (u,v)GT.EuC,vCf(C)<f(C)

    要证明算法STRONGLY-CONNECTED-COMPONENTS能够正确计算出有向图的的连通分量,可以通过对算法第3行对图 GT 进行深度优先搜索时所发现的深度优先树的棵树进行归纳。
    k=0时,归纳假设成立。
    假设算法第3行所生成的前面k棵树都是强连通分量。
    设结点u为第(k+1)棵树的根节点, C 为u所在的强连通分量,C为除C以外尚未被访问的强连通分量。
    在u.d时刻C中的所有结点都是白色的,由白色定理知C中其他结点都是u在深度优先搜索树中的后代。
    由推论1知,假如转置图 GT 中有从 C 发出到其他强连通分量的边,那么只能指向已经访问过的强连通分量C′′,才能有 f(C)<f(C′′) 。因此除了 C 以外的强连通分量中的结点不可能在对GT进行深度优先搜索时成为结点u的后代。综上,当且仅当C中的其他结点是结点u的后代,所以第(k+1)棵树也是一个强连通分量。而由归纳假设知算法第3行所生成的前k棵树都是强连通分量,因此由算法第3行所生成的前(k+1)树都是强连通分量。(证毕)

    • 总结
      强连通分量算法的证明过程使用了反证法,分类讨论和数学归纳法等重要数学方法和思想。简单来说,因为推论1的正确性可以证明了除了C强连通分量的结点外的结点都不可能成为u结点的后代,以及进行深度优先搜索时C中其他结点与u的关系,从而得出连通分量与深度优先树的一一对应关系。而推论1由引理2得出,引理2又由引理1以及推论22.8得到。
    展开全文
  • C++Kosaraju找有向图的强连通分量算法C++Kosaraju找有向图的强连通分量算法完整源码(定义,实现,main函数测试) C++Kosaraju找有向图的强连通分量算法完整源码(定义,实现,main函数测试) #include <iostream...
  • 本文从多个角度去讨论了强连通分量算法的设计思路,并重点分析了算法中的图转置操作的意义。 本文的内容是基于算法导论22.5节的深度分析,编写日期2019/1/22,20日掌握算法导论day13   【为什么要转置图G?】 ...
  • 图论——强连通分量(Tarjan算法)

    万次阅读 多人点赞 2019-03-10 23:30:05
    文章目录 强连通分量 利用Tarjan算法强连通分量 来一道例题练手(USACO08DEC) 图论文章汇总 强连通分量 什么是连通图? 如果一个有向图中,存在一条回路,所有的结点至少被经过一次,这样的图为连通图。 什么...
  • 强连通分量(Tarjan算法)

    千次阅读 2019-02-22 16:28:26
    强连通分量 有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的... Tarjan 算法是基于对图优先搜素的算法 , 每个强连通分量为搜索树中的一棵子树...
  • 理解强连通分量Kosaraju算法的正确性

    千次阅读 多人点赞 2018-03-26 21:03:55
    1.基本概念 在看《算法... Kosaraju算法是计算有向图中强连通分量的经典算法。下面简要补充几个基本概念:1.1 有向图 在有向图中,边是单向的:每条边所连接的两个顶点都是一个有序对。如下图所示: 有向图的数...
  • 这里介绍求解强连通分量的Tarjan算法。Tarjan算法是基于dfs的,对一张图进行dfs后,我们会得到一颗搜索树。 有向图的搜索树可以分为四种 树边(实线):每找到一个还未访问过的节点就形成一条树边。 回边(长虚线...
  • 对于一个非连通图,可以通过深度优先搜索或广度优先搜索来获取它的连通分量:从一个未访问过的节点开始进行深度优先或者广度优先搜索,其能到达的所有顶点及其相关的边构成的子图就是一个连通分量;直到访问完全部的...
  • tarjian算法 新的改变 我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,帮助你用它写博客: 全新的界面设计 ,将会带来全新的写作体验; 在创作中心...
  • 算法提供了理解、建模和预测复杂动态的手段,例如资源或信息流、传染或网络故障传播的途径,以及对群体的影响和弹性。本博文系列旨在帮助读者更好地利用图分析和图算法,以便能够使用 Neo4j 等图数据库更快地有效...
  • 求用连接表存储的有向图的强连通分量算法
  • Kosaraju算法(强连通分量分解)

    千次阅读 多人点赞 2018-08-12 21:44:39
    如果在连通的顶点集合S中加入其他任意顶点集合后,它都不再是连通的,那么就称S是原图的一个强连通分量(SCC:strongly connected component)。任意有向图都可以分解成若不相干的强连通分量,这就是强连通分量分解...
  • 对于Tarjan强连通分量算法的理解

    千次阅读 2017-02-22 12:39:17
    对于Tarjan强连通分量算法的理解
  • 全网最详细tarjan算法讲解,我不敢说别的。反正其他tarjan算法讲解,我看了半天才看懂。我写的这个,读完一遍,发现原来tarjan这么简单! tarjan算法,一个关于 图的联通性的神奇算法。基于DFS(迪法师)算法,深度...
  • 强连通分量的三种算法分析

    千次阅读 2016-07-28 21:51:31
    本文将介绍什么是强连通分量,求解强连通分量的三种算法Kosaraju算法、Tarjan算法、Garbow算法。因为算法的过程很容易理解,真正难的是如何理解算法的思想,写主这个的时候我也不定完全明白算法为什么这样,为什么...
  • Tarjan算法--有向图强连通分量算法

    千次阅读 2015-03-14 10:39:29
    正如标题所介绍的那样,Tarjan算法的目标就是找出图中的连通图的,其实前提条件是这样的,在一个有向图中,有时必然会出现节点成环的情况,而在图内部的这些形成环的节点所构成的图就是我们所要找
  • Python算法教程:强连通分量

    千次阅读 2019-08-23 00:43:21
    连通分量(strongly connected components, SCCs)是一个能让有...Kosaraju的查找强连通分量算法 def strongly_connected_components(graph): transpose_graph = get_transpose_graph(graph) scc, seen = [], set...
  • 联通分量 1.概念 在有向图G中,如果两点互相可达,则称这两个点连通,如果G中任意两点互相可... 2、非连通有向图的极大连通子图,称为强连通分量(SCC即Strongly Connected Componenet)。 任意有向图都...
  • 强连通分量:极大连通子图。 白色路径定理:请自行百度(不是重点) 引理:a,b相互可达,则属于同一连通分量。(若a在C上,所以b与C上任意顶点可通过a互达,因此b在C上) 1.首先从一般的算法开始 一个有向图...
  • 课 程 设 计 报 告 课程设计名称数据结构课程设计 课程设计题目实现求有向图强连通分量算法 院系 专 班 学 姓 业 级 号 名 指导教师 沈阳航空航天大学课程设计报告 目 录 系 统 分 析 .1 1.1 题 目 介 绍 .1 1.2 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,609
精华内容 9,043
关键字:

强连通分量算法

友情链接: 2262_zixuexi.rar