精华内容
下载资源
问答
  • 强连通图
    千次阅读
    2021-02-12 02:25:21

    判断一个图是否为强连通图、单向连通图、弱连通图。输入为有向图的邻接矩阵。

    输入

    输入有若干行

    第一行为正整数N(0

    接下来N行,每行有N个数据,每个数据以空格分隔,代表邻接矩阵。

    注意:输入的都是连通图。

    输出

    输出有一行,数字1,2,3

    1代表强连通图

    2代表单向连通图

    3代表弱连通图

    测试输入

    3

    1 1 1

    1 1 1

    1 1 1

    测试输出

    1

    源代码

    #include

    #define N 305

    int main()

    {

    int a[N][N];

    int i,j,k,n;

    scanf("%d\n",&n);

    for(i=0;i

    for(j=0;j

    scanf("%d",&a[i][j]);

    for(i=0;i

    for(k=0;k

    for(j=0;j

    if((a[i][k]!=0)&&(a[k][j]!=0))

    a[i][j]=1;}

    for(i=0;i

    for(j=0;j

    {

    if((a[i][j]==0)&&(a[j][i]==0)){

    printf("3\n");return 0;}

    if(a[i][j]+a[j][i]==1){

    printf("2\n");return 0;}

    }

    printf("1\n");

    }

    更多相关内容
  • 如果 G 是有向图,那么连接 i 和 j 的路径中所有的边都必须同向。...如果此图是有向图,则称为强连通图(注意:需要双向都有路径)。今天叶子为大家分享的是【连通图、连通分量与强连通图、强连通分量】...

    目录

    什么是连通图?

    什么是连通分量?

    那什么是极大连通子图呢?联想到的极小连通子图又是什么呢?

    强连通图

    强连通分量

    ”强强“在那里—连通图和强连通图的区别?

    创作不易,不妨点赞💚评论❤️收藏💙一下

    想要了解更多吗?没时间解释了,快来点一点!


    💟作者简介:大家好呀!我是路遥叶子,大家可以叫我叶子哦!❣️    
    📝个人主页:【路遥叶子的博客】
    🏆博主信息:四季轮换叶,一路招摇胜!

                   专栏

            【安利Java零基础】

            【数据结构-Java语言描述】

    🐋希望大家多多支持😘一起进步呀!~❤️
    🌈若有帮助,还请【关注点赞收藏】,不行的话我再努力努力呀!💪
    ————————————————
    🍁想寻找共同成长的小伙伴,请点击【Java全栈开发社区】


    前言

    对连通图的理解

    图论中,连通图基于连通的概念。

    在一个 无向图G 中,若从顶点 i 到顶点 j 有路径相连(当然从j到i也一定有路径),则称i和j是连通的。

    如果 G 是有向图,那么连接 i j 的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果此图是有向图,则称为强连通图(注意:需要双向都有路径)。图连通性的是图的基本性质。


    一、什么是连通图?

    连通:在无向图中,若从顶点u到顶点v有路径,则称u和v是连通的。

    图中从⼀个顶点到达另⼀顶点,若存在⾄少⼀条路径,则称这两个顶点是连通着的。例如图 1 中,虽然 V1 和 V3 没有直接关联,但从 V1 到 V3 存在两条路径,分别是 V1-V2-V3 和 V1-V4-V3,因此称 V1 和 V3 之间是连通的。

      二、什么是连通分量?

    若⽆向图不是连通图,但图中存储某个⼦图符合连通图的性质,则称该⼦图为连通分量
    图中部分顶点和边构成的图为该图的⼀个⼦图,但这⾥的⼦图指的是图中"最⼤"的连通⼦图(也称"极⼤连通⼦图")。

    若无向图为非连通图,则图中各个极大连通子图称为此图的连通分量。

    2.1 、那什么是极大连通子图呢?联想到的极小连通子图又是什么呢?

    1. 首先先明确两个概念,无向图和有向图;其次,明确一个概念极大连通子图,可以存在于无向图中,也可以存在于有向图中;

    2. 但要知道,极小连通子图只存在于连通的无向图中,不存在于不连通的无向图和有向图中

    •  也就是说,极大连通子图和极小连通子图适用条件是不一样的,尽管它们看起来貌似很接近。

    无向图中的极大连通子图

    无向图中的极大连通子图也叫连通分量

    无向图可以分成两种类型:连通的无向图、不连通的无向图

    •  连通的无向图只有一个极大连通子图,即它本身,因为不存在另一个连通的子图包含的点和边比它本身还要多,所以叫作极大连通子图。
    • 不 连通的无向图可以拆分为若干个连通的无向图,如果我们在拆分时注意把能连通的点边都放在一个连通子图中,使这个连通子图足够大,以至于再多包含一个点或边它就变成不连通的了,我们称这个连通子图为极大连通子图,也叫连通分量。

    极小连通子图

    极小连通子图只存在于连通的无向图中,也就是说该图中只有一个连通分量(极大连通子图),之所以说它极小,是因为极小连通子图只要求包含图中所有顶点及其比顶点数量少一个的边(且不能成环),也就是说如果给极小连通子图任意两个顶点间加入一条边,则必有环。

    这里的极大和极小不是指一个意思,不要弄混了,极大连通子图是讨论连通分量的,极小连通子图是讨论生成树的。


    下面举几个图例,让大家看看,深入了解一下连通分量:

    如图 3 所⽰,虽然图 a 中的⽆向图不是连通图,但可以将其分解为 3 个"最⼤⼦图"(图 b ),它们都满⾜连通图的性质,因此都是连通分量。

    看了这么多图例,你学会了吗?能在图中找出连通分量了吗?

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


    三、强连通图

    1.  如果一个有向图G,对于其中任意两个顶点v,u,都存在从v到u以及从u到v的有向路径,则称G为强连通图。而在一个不是强连通图的有向图G中,若其中两个顶点u、v在两个方向上都存在有向路径,则称u和v强连通。

    2.  强连通图:在有向图中,若任意两个顶点 均连通(一条有向路径),则称该图是强连通图。

    3.  有向图中,若任意两个顶点 Vi 和 Vj,满⾜从 Vi 到 Vj 以及从 Vj 到 Vi 都连通,也就是都含有⾄少⼀条通路,则称此有向图为强连通图。如图 4 所⽰就是⼀个强连通图。

    四、强连通分量

    1. 在有向图中,如果从任意一个顶点出发,都能通过图中的边到达图中的每一个顶点,则称之为强连通图。一张有向图的顶点数 极大的强连通子图 称为强连通分量。

    2. 而有向图G的极大强连通子图S,即添加任意顶点都会导致S失去强连通的属性,则称S为G的强连通分量。

    3. 强连通分量:有向图中的极大强连通子图强连通图只有一个强连通分量,即其本身

    4. 与此同时,若有向图本⾝不是强连通图,但其包含的 最⼤连通⼦图具有强连通图的性质,则称该⼦图为强连通分量。整个有向图虽不是强连通图,但其含有两个强连通分量。


    ”强强“在那里—连通图和强连通图的区别?

    • 需求不同:强连通图说的是有向图,连通图说的是无向图。连通图只存在于无向图中,而强连通图通常存在于有向图中。
    • 概念不同:
      •  在一幅无向图中,任何两个顶点之间可以相通,则该图就是连通图。
      • 在一幅有向图中,任意两对顶点都可以相通,那么该图就是强连通图。

     可以这样说,连通图是在⽆向图 的基础上对图中顶点之间的连通做了更⾼的要求,⽽强连通图是在有向图 的基础上对图中顶点的连通做了更⾼的要求。


    写到最后

    ❣️四季轮换,已经数不清凋零了多少叶

    ❣️愿我们往后能向心而行,一路招摇胜!

    🐋你的支持认可是我创作的动力

    💟创作不易,不妨点赞💚评论❤️收藏💙一下

    😘感谢大佬们的支持,欢迎各位前来不吝赐教

    想要了解更多吗?没时间解释了,快来点一点!

    路遥叶子的博客_CSDN博客-数据结构,安利Java零基础,spring领域博主https://blog.csdn.net/zsy3757486?type=blog

    展开全文
  • cost存放了一个强连通图的边权矩阵,作为一个实例。可在workspace中加载运用此算法要注意多次试验。
  • 完全图与强连通图的那些坑

    千次阅读 2021-11-16 23:48:28
    这个数据结构相比队列、栈、树来说算是复杂多了,关于的问题也多如牛毛,先来看一下常见的问题: 若无向 `G` 中含7个顶点,要想保证 `G` 在任何情况下都是连通的,则需要的边数最少是几条...

    前言

    图这个数据结构相比队列、栈、树来说算是复杂多了,关于图的问题也多如牛毛,先来看一下常见的问题:

    若无向图 G 中含7个顶点,要想保证图 G 在任何情况下都是连通的,则需要的边数最少是几条?

    回答这种问题一定要注意细节,找到关键的点,不然一定会掉到坑里的。这个题关键点有以下几个:

    • 7个顶点
    • 任何条件下连通
    • 最少几条边

    其中第1点和第3点不容易出错,比较容易出现问题的是第2点,要想保证任何条件下连通,意思给定边数以后无论怎么连都能通?

    先说下答案是16,至于为什么,我们后面先复习一下图相关的概念再慢慢解释,因为此刻的我连什么是强联通图都忘了~

    一些概念

    • :是由顶点V集和边E集构成,边表示了与之相连的两点间的关系,因此图可以表示成G = (V, E)
    • 有向图:是指图中的两个顶点从A到B和从B到A的含义是不同的,我们认为两点的关系是有方向的,则称其为有向图
    • 无向图:是指两点间的连接线无方向无关,这种图叫做无向图
    • 连通性:从图中一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的
    • 连通图:在无向图中,如果任意两个顶点之间都能够连通,则称此无向图为连通图
    • 完全图:在无向图中,如果任意两个顶点之间都边直接相连,则称此无向图为完全图
    • 连通分量:若无向图不是连通图,但图中存在某个子图符合连通图的性质,则称该子图为连通分量
    • 强连通图:在有向图中,若任意两个顶点之间包含至少来回两条通路,则称此有向图为强连通图
    • 有向完全图:在有向图中,如果任意两个顶点之间都有相反的两条弧直接相连,则称此有向图为有向完全图
    • 强连通分量:若有向图不是强连通图,但图中存在某个子图符合强连通图的性质,则称该子图为强连通分量

    关于题目的解释

    这是一个无向图,要想在任何情况下都连通,那考虑极端情况就是孤立一个顶点,让尽可能多的边连接剩余的顶点,那会构成一个 n-1 个顶点的完全图,然后再考虑加一条边把剩下的孤立顶点连起来,这样得到的边数是 N = 5+4+3+2+1 + 1 = 16,用组合数表示就是

    C n − 1 2 + 1 = ( n − 1 ) ∗ ( n − 2 ) / 2 + 1 C^2_{n-1} + 1= (n-1) * (n-2) / 2 + 1 Cn12+1=(n1)(n2)/2+1

    题目变型

    • 若无向图 G 中含7个顶点,要想保证图 G 在是连通的,至少需要几条边?

      答案6条,即 (n-1)

    • 一个包含7个顶点的无向图 G 为完全图,那么它共有几条边?

      答案21条,即 n * (n-1) / 2

    • 若有向图 G 中含7个顶点,要想保证图 G 在是强连通的,至少需要几条弧?

      答案7条,即 n,也就是形成一个环

    • 一个包含7个顶点的有向图 G 为完全图,那么它共有几条弧?

      答案42条,即 n * (n-1)

    补充两个图例

    • 完全图,特点是任何两个顶点都有直接的边相连
    A
    B
    C
    D
    E
    • 强连通图,任意两点间都有路径可达
    A
    B
    C
    D
    E
    F

    总结

    • 解答关于图的问题可以从概念入手,更要注意题目中至多、至少、任何等字眼
    • 弄清楚连通图、完全图、连通分量、强联通图、强连通分量等概念,迷糊的时候可以画一画
    • 使用mermaid语法画的图确实不怎么好看,不过它强在了描述性的语言

    ==>> 反爬链接,请勿点击,原地爆炸,概不负责!<<==

    那些看似漫不经心的成功,其实都是蓄谋已久;那些你以为的驾轻就熟,其实都是有备而来。一个人越活越好的样子应该是不沮当下,不弃未来。你要相信,所有的事与愿违或许都是惊喜的铺垫,所有的坚持不懈终将得到岁月的奖赏~

    展开全文
  • 连通图、强连通图、弱连通图

    万次阅读 多人点赞 2021-03-12 09:28:40
    考研复试复习到离散数学的时候一道选择题判断给出的图是连通图还是强弱连通图,虽然在数据结构中学习过这方面的知识,不过当时感觉知识点...2、强连通图 这里我们直接看百度百科怎么解释的强连通图 3、弱连通图 ...

    考研复试复习到离散数学的时候一道选择题判断给出的图是连通图还是强弱连通图,虽然在数据结构中学习过这方面的知识,不过当时感觉知识点太小,就没有太注意,所以今天回看王道的数据结构的资料,进行如下总结,一下资料来自王道。
    1、有向图和无向图(很好判断)
    在这里插入图片描述
    2、强连通图在这里插入图片描述
    这里我们直接看百度百科怎么解释的强连通图
    在这里插入图片描述
    3、弱连通图
    在这里插入图片描述

    展开全文
  • 在有向图中, 若对于每一对顶点v1和v2, 都存在一条从v1到v2和从v2到v1的路径,则称此图是强连通图。 弱连通图: 将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有...
  • 若一个有向图中的顶点不能排成一个拓扑序列...是个强连通图 C.含有多个入度为0的顶点 D.含有顶点数目大于1的强连通分量 这题选D 但是B为啥不对,难道单独一个顶点算是强连通图?</p>
  • 完全图、连通图、非连通图、连通分量、强连通图、生成树的概念
  • 对路径、连通、连通图,强连通图、连通分量、极大连通子图以及割点、割边等定义的回顾
  • 有向图连通性(强连通图)1.1有向图1.2有向图连通性2.tarjan算法简述3.实现过程3.1 例题-刻录光盘3.1.1 输入&&初始化3.1.2 tarjan(类似深搜)3.1.3 缩点3.2 完整答案 1.有向图连通性(强连通图) 1.1有向图...
  • 强连通图的介绍

    千次阅读 2021-01-06 18:31:44
    问题一:强连通图任意两个顶点存在一条有向路径还是a到b到a都得互相有路径? 解:互相有路径,也就是顺着箭头的方向走, 既可以从a走到b,也可以从b走到a 问题二:啥是极大强连通子图? 解:1.为什么叫做极大...
  • 7. 连通图、强连通图 8. 研究图的局部–子图 9. 连通分量 10. 强连通分量 11. 生成树 12. 生成森林 13 边的权、带权图/网 14. 几种特殊形态的图 15. 知识回顾 1. 知识总览 2. 图的定义 3. 图逻辑结构的应用 4....
  • Tarjan算法按照百度百科的播报应该是读成【'ta:rdʒən】?看过了几篇网络上的解释虽然都讲得比较具体但刚开始都难以理解,所以打算写一个更直观的理解方式。... Tarjan算法是求有向中的强连通分量的算法。
  • 2.连通图(一般都是指无向图):  从顶点v到w有路径,就称顶点v和m连通。(路径是由顶点和相邻顶点序偶构成的边所形成的序列,其实就是一堆相连的顶点及其边)  如果图中任意俩顶点都连通,则该图为连通图...
  • 如果有向图G的两两都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两可达。{5},{6}也...
  • 强连通图上的共识的广播八卦算法
  • 最近看了看类的相关题,感觉简单的题很简单,但是难题的转化如果对概念不清楚,很难写,我怕我...(1) 有向联通分量 (2) 无向的双联通分量(求割点,桥) (3) 最近公共祖先 这里前两类问题比较相似,而...
  • 总结性话语: 有向完全图一定是强连通图,但强连通图不一定是有向完全图 定义: 强连通:图中任何两个顶点都有 路径 存在 有向完全图:图中任意两个顶点都有 方向相反的两条边 存在 解释 路径,同上 方向相反的两条...
  • ●连通分量:图的极大连通子图 ●强连通图:有向图中任意两个顶点都存在路径 ●强连通图的连通分量是其本身 ●非强连通图的连通分量不止一个 下面求一个非强连通图的所有连通分量 方法: (1)随便找一个有向环 (2...
  • 【算法】图 (5) 强连通图

    千次阅读 2020-05-18 13:46:45
    如何判断一个图是强连通图强连通图(strongly connected):在一个图中,任意两点x,y,都可以互相到达(可以借助其他点作为中转); 1 简单方法 对每个结点进行DFS或者BFS搜索,如果每次搜索的结果,使得每个...
  • 非递归遍历强连通图 G解答:分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.int visi
  • 强连通图(Strongly Connected Graph)是指在有向图G中,如果对于每一对vi、vj,vi≠vj,从vi到vj和从vj到vi都存在路径,则称G是强连通图。 二、判断是不是强连通图的算法: 下面是Kosaraju基于DFS的简单算法,这...
  • 强连通图 240、2(2) 十字链表 208
  • dfs判断强连通图

    2019-09-06 17:28:20
    判断单向图是否为强连通图,除了用tarjan算法计算强连通分量外,还有一种比较好懂的算法,用dfs正向遍历,记录节点个数,并且记录每一次的尾节点,在反向从最后一次的尾节点dfs确定强连通图。 代码如下(以邻接表为...
  • 强连通图:在有向图中,从任意一个结点出发都能到达任意一个结点,那么称该有向图为强连通图。 连通子图:在无向图中,如果删除这个图的一些边(删除的边数>=0),剩下的部分仍然是连通的,那么称这个图是原图的...
  • 分析: 由已经学过的知识和编程基础知识分析该题: 第一获取用户输入的邻接...第四,输出可达矩阵,观察:若除了对角线元素外不存在0,则该图为强连通图,否则不是强连通图。 对于第一个问题,可以利用数组来存。...
  • 如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。 求解有向图的强连通分量算法有很多,例如Kosaraju,Gabow和Tarjan算法...
  • 2、最少需要多少条边才能使得图变成强连通图 首先我们先使用tarjan算法求出图中的强连通分量,对于一个强连通分量,可以当做一个点来考虑,所以我们可以缩点,然后得到DAG图。 那么对于第一个问,即是入度为0的点有...
  • 超弧强连通图的充分条件

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,933
精华内容 17,573
关键字:

强连通图

友情链接: matlab测试.rar