精华内容
下载资源
问答
  • 连通图、强连通图、弱连通图

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

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

    展开全文
  • 在有向图中, 若对于每一对顶点v1和v2, 都存在一条从v1到v2和从v2到v1的路径,则称此图是强连通图。 弱连通图: 将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有...

    图论的起源

    关于图的第一篇论文是瑞士数学家欧拉(E. Euler)在1736年发表的解决“哥尼斯堡"七桥难题的论文:
    在这里插入图片描述

    德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,河的两岸和岛屿之间有七座桥相互连接,当地的居民热衷于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地。尽管试验者很多,但是都没有成功。
    为了寻找答案,1736年欧拉将这个问题抽象或图所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形,最终回到原点。欧拉在他的论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论中的第一个著名问题。

    图的基本概念

    图:图论中的图是由点和点与点之间的线所组成的。通常,我们把点与点之间不带箭头的线叫做,带箭头的线叫做

    无向图:如果一个图是由所构成的,那么,称为无向图,记作G=(V, E),其中V表示图G的点集合,E表示图G的边集合。连接点vi,vj的边记作[vi, vj],或者[vj, vi]。

    有向图:如果一个图是由所构成的,那么称为它为有向图,记作D=(V, A),其中V表示有向图D的点集合,A表示有向图D的弧集合。一条方向从vi指向vj的弧,记作(vi, vj)。

    简单图:一个无环,无多重边的图称为简单图
    在这里插入图片描述

    多重图:一个无环,有多重边的图称为多重图
    在这里插入图片描述
    链:由两两相邻的点及其相关联的边构成的点边序列。如v0,e1,v1,…,vn-1,en,vn。
    简单链:链中所含的边均不相同
    初等链:链中所含的点均不相同,也称通路

    连通图:

    连通图:图中任意两点之间均至少有一条通路,否则称为不连通图
    连通图:在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。

    在这里插入图片描述

    强连通和弱连通的概念只在有向图中存在

    强连通图:在有向图中, 若对于每一对顶点v1和v2, 都存在一条从v1到v2和从v2到v1的路径,则称此图是强连通图。

    弱连通图:将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。

    在这里插入图片描述

    生成树:一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n - 1条边

    在这里插入图片描述

    最小生成树:一个连通图的生成树可能有多个。边的权值之和最小的生成树是最小生成树

    在这里插入图片描述

    完全图:

    有向完全图:在n个顶点的无向图中,若有n(n-1)/2条边,即任意两个顶点之间有且仅有一条边,则称此图为无向完全图
    有向完全图:在n个顶点的有向图中,若有n(n-1)条边,即任意两个顶点之间有且仅有方向相反的边,则称此图为有向完全图
    在这里插入图片描述

    展开全文
  • 判断一个图是否为强连通图、单向连通图、弱连通图。输入为有向图的邻接矩阵。 输入 输入有若干行 第一行为正整数N(0 接下来N行,每行有N个数据,每个数据以空格分隔,代表邻接矩阵。 注意:输入的都是连通图。 输出...

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

    输入
    输入有若干行
    第一行为正整数N(0<N<=300),代表图中点的个数
    接下来N行,每行有N个数据,每个数据以空格分隔,代表邻接矩阵。

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

    输出
    输出有一行,数字1,2,3
    1代表强连通图
    2代表单向连通图
    3代表弱连通图


    测试输入

    3
    1 1 1
    1 1 1
    1 1 1


    测试输出

    1


    源代码

    #include<stdio.h>  
    #define N 305  
    int main()  
    {  
        int a[N][N];  
        int i,j,k,n;  
        scanf("%d\n",&n);  
        for(i=0;i<n;i++)  
          for(j=0;j<n;j++)  
            scanf("%d",&a[i][j]);  
        for(i=0;i<n;i++)  
          for(k=0;k<n;k++)  
            for(j=0;j<n;j++){  
                if((a[i][k]!=0)&&(a[k][j]!=0))  
                a[i][j]=1;}  
        for(i=0;i<n;i++)  
          for(j=0;j<n;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");       
     } 



    展开全文
  • 强连通图

    千次阅读 2012-06-18 16:04:18
  • 如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。 求解有向图的强连通分量算法有很多,例如Kosaraju,Gabow和Tarjan算法...
  • 强连通图:在有向图中,从任意一个结点出发都能到达任意一个结点,那么称该有向图为强连通图。 连通子图:在无向图中,如果删除这个图的一些边(删除的边数>=0),剩下的部分仍然是连通的,那么称这个图是原图的...
  • 超弧强连通图的充分条件
  • java实现强连通图

    2008-06-22 15:03:30
    java实现强连通图
  • 强连通图上的共识的广播八卦算法
  • 判断强连通图

    万次阅读 2016-10-27 15:24:39
     任取有向图G的某结点S,从S开始进行深度优先搜索,若可以遍历G的所有结点,则将G的所有边反向,再次从S开始进行深度优先搜索,如果再次能够遍历G的所有结点,则G是强连通图,两次搜索有一次无法遍历所
  • 强连通图(Strongly Connected Graph)是指在有向图G中,如果对于每一对vi、vj,vi≠vj,从vi到vj和从vj到vi都存在路径,则称G是强连通图。 二、判断是不是强连通图的算法: 下面是Kosaraju基于DFS的简单算法,这...
  • 强连通图的介绍

    2021-01-06 18:31:44
    问题一:强连通图任意两个顶点存在一条有向路径还是a到b到a都得互相有路径? 解:互相有路径,也就是顺着箭头的方向走, 既可以从a走到b,也可以从b走到a 问题二:啥是极大强连通子图? 解:1.为什么叫做极大...
  • dfs判断强连通图

    2019-09-06 17:28:20
    判断单向图是否为强连通图,除了用tarjan算法计算强连通分量外,还有一种比较好懂的算法,用dfs正向遍历,记录节点个数,并且记录每一次的尾节点,在反向从最后一次的尾节点dfs确定强连通图。 代码如下(以邻接表为...
  • 强连通图和双连通图

    千次阅读 2017-09-15 19:59:10
    刚刚弄明白了强连通和双连通,我好菜啊。...强连通中任意两个节点可以相互通达 双连通:中任意两个节点之间都有两条路 POJ-3177 跑一遍Tarjan 所有的双连通块看做一个点,将整个看做一棵树,把整棵树的叶子节
  • Java实现迷宫城堡(强连通图的判定).pdf
  • hdu1269 迷宫城堡(强连通图

    千次阅读 2017-04-22 16:13:35
    强连通模版题~ tarjan算法,通过计算强连通分量的个数来判断此图是否为强连通图 #include #include #include #include #include using namespace std; #define N 10005 vector<int>link[N];//邻接表建
  • 如何判断一个图是强连通图强连通图(strongly connected):在一个图中,任意两点x,y,都可以互相到达(可以借助其他点作为中转); 1 简单方法 对每个结点进行DFS或者BFS搜索,如果每次搜索的结果,使得每个...
  • 强连通图的算法

    2014-06-08 12:55:04
    有向图强连通分量的Tarjan算法 [有向图强连通分量] ...非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。 下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1
  • 用栈实现强连通图遍历
  • 由于上一道题涉及了环,所以我当时就在纠结一个问题,强连通图是否一定可以是环形的?(就是说强连通图是否一定是欧拉图?= 是否一定有欧拉回路?= 是否一定有一笔画的环形路线?) 现在,我给出答案,不一定。下面...
  • 本文主要讨论了m= n+ 1时的极小强连通图D的具体图形,得到了它的充要条件.
  • 分析: 由已经学过的知识和编程基础知识分析该题: 第一获取用户输入的邻接...第四,输出可达矩阵,观察:若除了对角线元素外不存在0,则该图为强连通图,否则不是强连通图。 对于第一个问题,可以利用数组来存。...
  • 给你一个图,判断是不是强连通图强连通图的强连通分量就是1.套了下kuangbin的模板。 单向边,注意init#include using namespace std; typedef long long LL; const int MAXN = 10010;//点数 const int MAXM = ...
  • 题目大意:给一个n个点的简单有向图,问最多能加多少条边使得该图仍然是简单有向图,且不是强连通图。简单有向图定义:没有重边,无自环。如果一开始就是一个强连通图,则输出-1。 思路:边最多应该是完全图,有向图...
  • 强连通图:最短路径就是形成闭环。 一个有向无环图的拓扑序列不是唯一的: 注意: 1)只有有向无环图才存在拓扑序列; 2)对于一个DAG(Directed Acyclic Graph,有向无环图),可能存在多个拓扑序列; 进行拓扑排序...
  • 2.连通图(一般都是指无向图):  从顶点v到w有路径,就称顶点v和m连通。(路径是由顶点和相邻顶点序偶构成的边所形成的序列,其实就是一堆相连的顶点及其边)  如果图中任意俩顶点都连通,则该图为连通图...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,118
精华内容 15,647
关键字:

强连通图