精华内容
下载资源
问答
  • 一、各个概念的定义 1.完全图:  也称简单完全图。假设一个图有n个顶点,那么如果任意两个顶点之间都有边的话,该图就称为完全图。...极大连通子图是无向图的连通分量。(暗指极大连通子图也指无向.

    一、各个概念的定义

    1.完全图
     也称简单完全图。假设一个图有n个顶点,那么如果任意两个顶点之间都有边的话,该图就称为完全图。
    2.连通图(一般都是指无向图):
     从顶点v到w有路径,就称顶点v和m连通。(路径是由顶点和相邻顶点序偶构成的边所形成的序列,其实就是一堆相连的顶点及其边)
     如果图中任意俩顶点都连通,则该图为连通图。
    3.连通分量:
     与连通图对应,一般书上说的都是特指无向图!!
     极大连通子图是无向图的连通分量。(暗指极大连通子图也指无向图!!)
    4.极大连通分量:
     极大是要求该连通子图包含其所有的边(暗指无向图)
    5.极小连通分量:
     极小是在保持连通的情况下使边数最少的子图(暗指无向图)
    6.强连通图(特指有向图):
     在有向图中,若从顶点v到m有路径,则称这俩顶点时强连通的。若任意一对顶点都是强连通的,称此图为强连通图。
     和无向图其实一毛一样,就换个名字以便和无向图区分。
    7.强连通分量:
     有向图中的极大强连通子图称为有向图的强连通分量。
    8.极大强连通分量:
     这里的极大和无向图完全一致
    9.极小强连通分量:
     这里的极小和无向图完全一致
    10.生成树:
     连通图的生成树是包含图中全部顶点的一个极小连通子图
    11.生成森林:
     在非连通图中,连通分量的生成树构成了非连通图的生成森林。

    二、深入理解各个概念

     上面各个概念的基本定义讲完了,看完可能很多人还是一脸懵逼,我当初看那么多概念都懒得去看,更别说去理解了,所以我打算谈谈自己的理解,举例子和画图来帮助大家理解。概念中的序号对应深入的序号,忘记概念网上翻看,可以双开对比看。

    1.完全图:
     对于完全图,他的顶点数是固定的,因此我们如果要研究他的性质,必然要从边上下手。
     对于有向图,考虑一个顶点,如果我们为得到所有不重复的边,那么应该怎么做呢?只考虑从该顶点出去的边或者只考虑射入该顶点的边。如果你不太理解的话,你可以考虑反证法。看下图:
    在这里插入图片描述
    如果上面的证明你看懂了,那么下面的就好做了,如果我们只考虑出去的边,对任一个顶点,与之相关的出边有n-1条总共有n个顶点,所以有向完全图有n*(n-1)条边。
     而对于无向图,任意一条无向图的边应该是有向图对应位置边的一半,所以总边数为n*(n-1)/2.
    2.连通图
    在这里插入图片描述
    3.连通分量:
     首先要知道分量,分量其实就是子图,只不过说的高大尚罢了。但连通分量不是简单的子图连通,他还除了要求子图连通,还要求该连通子图极大。说白了,无向图极大连通子图就是连通分量。到这里先往下看极大连通子图再回来看。
    4.极大连通分量:
     从3我们知道他首先是连通子图,并且该连通子图是极大的,主要是这里的极大很不好理解。这里我画图举例在这里插入图片描述
    5.极小连通分量在这里插入图片描述
    6.强连通图、强连通分量、极大强连通分量、极小连通分量就不用多说了,和无向图一毛一样,只不过他是针对有向图的。
    7.生成树:
     理解了极小连通子图,相信生成树也很容易理解了。
     连通图的生成树是包含图中全部顶点的一个极小连通子图。在这里插入图片描述
    8.生成森林
    在这里插入图片描述

    这就是本文章所有内容了,考研时间宝贵,抽出点时间写博客实属不易,希望对大家能有点帮助,有带佬补充的欢迎评论,有错误欢迎指出,最后,真希望我能考上南邮啊~

    展开全文
  • tarjan求极大连通分量

    2016-02-29 08:14:07
    而如果一个强连通分量已经没有被其它强通分量完全包含的话,那么这个强连通分量就是极大连通分量。 【算法思想】 用dfs遍历G中的每个顶点,通dfn[i]表示dfs时达到顶点i的时间,low[i]表示i所能直接或间接达到...
    下面大概说说tarjan算法吧:
    【功能】
    Tarjan算法的用途之一是,求一个有向图G=(V,E)里极大强连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话,那么这个强连通分量就是极大强连通分量。
    【算法思想】
    用dfs遍历G中的每个顶点,通dfn[i]表示dfs时达到顶点i的时间,low[i]表示i所能直接或间接达到时间最小的顶点。(实际操作中low[i]不一定最小,但不会影响程序的最终结果)
    程序开始时,time初始化为0,在dfs遍历到v时,low[v]=dfn[v]=time++,
    v入栈(这里的栈不是dfs的递归时系统弄出来的栈)扫描一遍v所能直接达到的顶点k,如果 k没有被访问过那么先dfs遍历k,low[v]=min(low[v],low[k]);如果k在栈里,那么low[v]=min(low[v],dfn[k])(就是这里使得low[v]不一定最小,但不会影响到这里的low[v]会小于dfn[v])。扫描完所有的k以后,如果low[v]=dfn[v]时,栈里v以及v以上的顶点全部出栈,且刚刚出栈的就是一个极大强连通分量。


       Tarjan算法的操作原理如下:


    Tarjan算法基于定理:在任何深度优先搜索中,同一强连通分量内的所有顶点均在同一棵深度优先搜索树中。也就是说,强连通分量一定是有向图的某个深搜树子树。可以证明,当一个点既是强连通子图Ⅰ中的点,又是强连通子图Ⅱ中的点,则它是强连通子图Ⅰ∪Ⅱ中的点。这样,我们用low值记录该点所在强连通子图对应的搜索子树的根节点的Dfn值。注意,该子树中的元素在栈中一定是相邻的,且根节点在栈中一定位于所有子树元素的最下方。强连通分量是由若干个环组成的。所以,当有环形成时(也就是搜索的下一个点已在栈中),我们将这一条路径的low值统一,即这条路径上的点属于同一个强连通分量。如果遍历完整个搜索树后某个点的dfn值等于low值,则它是该搜索子树的根。这时,它以上(包括它自己)一直到栈顶的所有元素组成一个强连通分量。


    参考链接
    http://www.cnblogs.com/saltless/archive/2010/11/08/1871430.html


    http://blog.sina.cn/dpool/blog/s/blog_69a101130100k1cm.html?vt=4
    展开全文
  • 这是一道,求极大连通分量的模板题,楼主第一次写,网上搜到的模板全部都是用数组存的,竟然没有找到用STL写的模板,于是楼主自己照着板子打了一遍。本题的思路其实很简单,找整个图里面的极大强连通分量,然后找到...

                   这是一道,求极大连通分量的模板题,楼主第一次写,网上搜到的模板全部都是用数组存的,竟然没有找到用STL写的模板,于是楼主自己照着板子打了一遍。本题的思路其实很简单,找整个图里面的极大强连通分量,然后找到每个分量里面的最小代价,如果有多个就用数组存起来。当然了,要是不会求强连通分量的算法的话这道题自己构造一个dfs的算法就比较复杂了,基础还是要巩固滴<( ̄ˇ ̄)/,以下是AC代码:

    #include<bits/stdc++.h>//强连通分量Tarjan算法模板题目 
    using namespace std;
    typedef long long ll;
    typedef struct Node{
    	int w;
    	vector<int>e;
    }Node;
    Node node[100010];
    int mod = 1e9+7; 
    int index = 0;//记录访问的节点的顺序序号 
    int num = 0; //记录现在出现的极大强连通分量的序号 
    int dfn[100010];//记录是否访问的数组 
    int low[100010];//记录某一个节点在dfs的时间戳 
    int instack[100010];//记录一个节点是否在栈中
    int belong[100010];//记录某一个节点所在的强连通分量的序号
    int cost[100010];//记录每一个极大强连通分量的最小代价 
    int cnt[100010];//记录每一个极大强连通分量最小代价的可选择数 
    stack<int>sta;//栈 
    void init()
    {
    	memset(dfn, 0, sizeof(dfn));
    	memset(low, 0, sizeof(low));
    	memset(instack, 0, sizeof(instack));
    	memset(belong, 0, sizeof(belong));
    	memset(cnt, 0, sizeof(cnt));
    	memset(cost, 0x3f3f3f3f, sizeof(cost));
    }
    void Tarjan(int u)
    {
    	dfn[u] = low[u] = ++index;
    	instack[u] = 1;//虽然已经进栈但还是要标记一下 
    	sta.push(u);
    	for(int i = 0; i < node[u].e.size(); i++)
    	{
    		int t = node[u].e[i];
    		if(!dfn[t])
    		{
    			Tarjan(t);
    			low[u] = min(low[u], low[t]);
    		}
    	    else if(instack[t])
    	    {
    	    	low[u] = min(low[u], dfn[t]);
    	    }
    	}
    	if(dfn[u] == low[u]) //如果节点u是强连通分量的根
    	{
    		num++; 
    		while(1) //一个个出栈,这里不要写错啦 
    		{
    			int v = sta.top();
    			instack[v] = 0;
    			belong[v] = num;
    			//printf("%d %d\n", v, belong[v]);
    			sta.pop();
    			if(v == u)
    			   break;
    		}
    	} 
    }
    int main()
    {
    	int n, m;
    	init(); 
    	scanf("%d", &n);
    	for(int i = 1; i <= n; i++)
    	   scanf("%d", &node[i].w);
    	scanf("%d", &m);
    	for(int i = 1; i <= m; i++)
    	{
    		int a, b;
    		scanf("%d%d", &a, &b);
    		node[a].e.push_back(b);
    	} 
    	for(int i = 1; i <= n; i++)
    	{
    		if(!dfn[i])//如果没有访问过该节点则进行搜索 
    		   Tarjan(i);
    	}
    	for(int i = 1; i <= n; i++)
    	{
    		//printf("%d\n", belong[i]);
    		if(cost[belong[i]] > node[i].w)
    		{
    			cost[belong[i]] = node[i].w;
    			cnt[belong[i]] = 1;
    		}
    		else if(cost[belong[i]] == node[i].w)
    		{
    			cnt[belong[i]]++;
    		}
    	} 
    	ll ans1 = 0, ans2 = 1; 
    	for(int i = 1; i <= num; i++)
    	{
    		ans1 += (ll)cost[i];
    		ans2 = (ans2*(ll)cnt[i])%mod;
    	}
    	printf("%I64d %I64d\n", ans1, ans2);
    	return 0;
    }


    展开全文
  • (连通、连通分量 = 极大连通子图)∈ 无向图        (强连通、强连通分量 = 极大强连通子图)∈ 有向图 连通、强连通        连通:无向图中,顶点v可以到达顶点w,称v和...

    首先,明确概念间的关系

           (连通、连通分量 = 极大连通子图)∈ 无向图
           (强连通、强连通分量 = 极大强连通子图)∈ 有向图

    连通、强连通

           连通:无向图中,顶点v可以到达顶点w,称v和w是连通的。
           强连通:有向图中,顶点v可以到达顶点w且顶点w可以到达顶点v,称v和w是强连通的。

    展开全文
  • 连通图:在无向图中,从任意一个结点出发都能到达任意一个结点,那么称该无向图为连通图。 强连通图:在有向图中,从任意一个结点出发...极大连通子图:如果无向图的连通子图包含它的原图中所有与它自身有关的边,那么
  • 无向图 连通 在无向图中,若从顶点v到顶点w有路径存在,则称v和w是连通的。(连通是两个顶点之间存在路径,注意是路径...连通分量(也就是极大连通子图) 无向图中极大连通子图称为连通分量。 无向图分为连通图...
  • 1、极大连通子图(即连通分量)、极小连通子图都为图的连通子图,极大即包含边最多,极小即包含边最少; 2、对于连通图 极大连通子图(包含边最多的连通子图)即本身(包含所有边)。 极小连通子图为某一顶点子集...
  • 极大连通子图 + 极小连通子图 + 连通分量

    万次阅读 多人点赞 2017-08-09 18:53:49
    基于很多初学者被数据结构图中很多概念晕头转向,这里小编手写了一份三个概念的大致情况,希望对大家有所帮助O(∩_∩)O
  • 感谢:https://blog.csdn.net/qq_38262266/article/details/77010230
  • 感谢:https://blog.csdn.net/qq_38262266/article/details/77010230 这个可以说总结的很到位了!
  • 极大连通分量的Tarjan算法 首先,在有向图G中,如果两个顶点vi,vj间(vi<>vj)都有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每...
  • 本文是《刘汝佳算法竞赛》的双连通分量... 极大连通子图:对于一个连通图,极大连通子图就是其连通分量也就是 其本身,非连通图有多个连通分量则就有多个极大连通子图。主要理解的是极大,极大指的是这个连通子图不...
  • (1)极大连通子图是连通图的一个连通分量连通分量本身是一个连通图。 (2)连通图的极大连通子图只有一个就是其本身,是唯一的。 (3)非连通的极大连通子图有多个,每一个都是一个连通图。 为什么称为极大?如果...
  • 连通分量(biconnected component, 简称bcc) ...一个无向图中的每一个极大点(边)双连通子图称作此无向图的点(边)双连通分量。求双连通分量可用Tarjan算法。--百度百科 Tip:先学一下tarjan算法...
  • Tarjan三算法之双连通分量(双连通分量

    万次阅读 多人点赞 2016-05-03 16:18:43
    定义: 对于一个连通图,如果任意两点至少存在两条点不重复路径,则称...对一个无向图,点双连通的极大子图称为点双连通分量(简称双连通分量),边双连通的极大子图称为边双连通分量。这篇博客就是总结一下求解无向图
  • 极大连通分量. 如果连通分量加上任何一个点之后, 都不是连通分量了, 那么称这个连通分量为极大连通分量(强连通分量) 强连通分量的用途 可以把任意一个有向图, 转化称一个有向无环图. 有向图 —>缩点(将所有连通...
  • 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<stack> 5 #include<algorithm> 6 #include<queue> 7 #include<... 8 u...
  • 极大连通子图与极小连通子图

    千次阅读 2020-10-04 09:38:25
    (非连通图的极大连通子图叫做连通分量,每个分量都是一个连通图) 3.称为极大是因为如果此时加入任何一个不在图的点集中的点都会导致它不再连通。 下图为非连通图,图中有两个极大连通子图(连通分量)。极小连通...
  • 连通分量

    2019-10-06 16:39:55
    连通分量是指有向图的一个极大子图使得其中每个点都可以到达其他所有点。 双连通分量是指无向图中的一个极大子图,分为两种: 点双连通分量:至少删去两个点才能使子图不连通 边双连通分量:至少删去两条边才能使...
  • POJ2186-Popular Cows ...【Tarjan+极大连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
  • 一个极大连通子图=一个团=一个连通分量。 生成森林=所有连通分量的极小连通子图的集合。 对于一个连通图B: 极大连通子图就是本身。 极小连通子图=生成树=去掉所有多余边后的B (保持B的连通性前提下,去掉所有...
  • 定义: 对于一个连通图,如果任意两点至少存在两条点不重复路径,则称...对一个无向图,点双连通的极大子图称为点双连通分量(简称双连通分量),边双连通的极大子图称为边双连通分量。这篇博客就是总结一下求解无向...
  • /*极大连通分量的tarjan算法模板题。*/ #include #include #include using namespace std; struct EDGE { int to,next; } e[100005]; //边结点数组 int head[10010],stack[10010],DFN[10010],Low[10010],...
  • 连通分量与双连通分量

    千次阅读 2011-09-08 17:51:56
    对于有向连通图,如果任意两点之间都...极大的强连通子图称为强连通分量。一个有向图可以有多个强连通分量,一个点也算是强连通分量。强连通分量的术语是strongly connnected components,简称SCC   对于无
  • 有向图的极大连通分量

    千次阅读 2008-12-19 23:04:00
    1. 对有向图G进行DFS,记录时间戳Ai,形成森林W12. 将G中所有边反向形成G3.按时间戳由大到小对G进行DFS,形成新森林W2.由此,形成的每棵树都是一个极大连通子图。
  • 1.对于无向图而言,如果图中的某两个点,例如:存在W到V的路径,那么我们说w和v是连通的;进一步如果图中任意两点之间都是存在路径的,那么我们说这个是连通的,即可称为连通图。...3.极大连通子图
  • 极大连通子图跟极小连通子图

    千次阅读 多人点赞 2018-11-12 11:12:05
    作业帮 转载说明   首先先明确两个概念,无向图和有向图;其次,明确一个概念,极大连通子图可以存在于无向图中,也可以存在于有向图中(下面进行分析);...无向图中的极大连通子图也叫连通分量.无向图可以...

空空如也

空空如也

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

极大连通分量