精华内容
下载资源
问答
  • 4.python蓝桥杯模拟题 一包含有2019结点的有向图最多包含多少条边?(不允许有重边) 1.用n表示图中顶点的数目,e表示边或者弧的数目,则对于无向图来说,e的取值范围为0-(1/2)n(n-1);对于有向图来说,e的...

    4.python蓝桥杯模拟题 一个包含有2019个结点的有向图,最多包含多少条边?(不允许有重边)

    1.用n表示图中顶点的数目,e表示边或者弧的数目,则对于无向图来说,e的取值范围为0-(1/2)n(n-1);对于有向图来说,e的取值范围为0-n(n-1)

    2.完全图:有(1/2 )n(n-1)条边的无向图称为完全图

    3.有向完全图:有n(n-1)条弧的有向图称为有向完全图

    4.(无向)连通图:对于图中的任意两个顶点之间都是联通的,则称该图是连通图,n个节点的无向连通图最少包含(n-1)条边

    所以答案为2019*2018=4074342

    image-20210309194348458

    展开全文
  • 数学归纳法: 1个顶点为0 2个顶点为1 满足1=2*1/2 3个顶点以上时 假如n=k-1 k>=3时结论成立 也就是k-1个顶点有 (k-1)*(k-2)/2=k^2/2-3k/2+1个边 加入第k个顶点时 与前k-1个...因此一个具有N个顶点的无向...
    数学归纳法:
    1个顶点为0 2个顶点为1 满足1=2*1/2
    3个顶点以上时 假如n=k-1 k>=3时结论成立
    也就是k-1个顶点有 (k-1)*(k-2)/2=k^2/2-3k/2+1个边
    加入第k个顶点时 与前k-1个顶点产生k-1条边
    则边数一共为k^2/2-3k/2+1+k-1=k^2/2-k/2=k*(k-1)/2
    即当n=k时也满足条件
    因此一个具有N个顶点的无向完全图的边数为n*(n-1)/2 
    展开全文
  • 最近,我们已经表明,当且仅当它具有唯一的初始强分量D1并且D1对扩展的(k + 1)周期不是同构的时,具有k≥4的k-拟传递有向图具有k-king。 在本文中,我们将研究k-拟传递有向图中有k-king的k-king的数量。 的确,...
  • 题目描述现实版: ...他也不是一计划狂,随性的他希望游完第一城市之后再决定下一步去哪里,而他又希望美好的开始,不至于像去了三亚的天涯海角之后无路可走,所以他打算将他的第一

    题目描述

    现实版:
    计算机系的小雷同学是个背包客,他打算暑假有时间去环游中国。
    他的想法得到了家里的支持,爸爸决定赞助他一张机票送他前往他的第一个目的地。
    小雷并不是一个贪小便宜的人,所以他自然不会买最贵的机票前往乌鲁木齐(躺枪)。
    他也不是一个计划狂,随性的他希望游完第一个城市之后再决定下一步去哪里,而他又希望有一个美好的开始,不至于像去了三亚的天涯海角之后无路可走,所以他打算将他的第一个目的地定为有航线能通往最多城市的国内机场所在地。
    小雷的叔叔告诉他,如果这样的话那么他只能选择飞往北京了。但是小雷并不相信这个结论,于是他搜集了国内各个城市之间的航线图,自己尝试用专业知识对这个问题进行建模。
    他把每一个城市定义为图内的一个顶点,城市之间的航线采用有向边来表示。例如,城市A有飞往城市B的航班,那么在图中就存在一条从A指向B的有向边。
    建模完成之后问题来了,如何利用小雷的模型,计算出哪一个城市是他的第一个最佳旅行目的地呢?

    抽象版:
    给定一个有向图G,一个点 v 的影响力定义为图G中可以从 v 可达的顶点的个数(不包括自身)。

    问题:找出图G中影响力最大的顶点。

    注:结果不一定唯一。

    输入
    图G,以邻接表的形式。
    点的标号从0到n-1,总共n个点,于是有n行输入。
    第 i 行的输入为与编号 i-1 这个点相邻的点们的标号,以空格隔开,行尾无空格。如样例输入中第2行为“2 3”,表示点1到点2有一条边,点1到点3有一条边。
    注:本次输入处理不会告诉你总共有多少个点,每一行也不会告诉你该点有多少个邻居,请发挥你的聪明才智,运用种种编程技巧处理这样的输入。

    输出
    第一行:图G中影响力最大的点的影响力。
    第二行:图G中影响力最大的点的标号。如果结果不唯一,依照标号从小到大输出,中间以空格隔开。

    样例输入

    1
    2 3
    0
    4
    5
    3

    样例输出

    5
    0 1 2

    提示

    一个点的影响力,不包括自身。

    解题思路

    有向图G,一个点 v 的影响力定义为图G中可以从 v 可达的顶点的个数(不包括自身)。题目要求找出图G中影响力最大的顶点。首先求解原有向图的SCC,然后对压缩图中入度为0的顶点进行DFS,并计算这些顶点的影响力。

    数据结构

    使用邻接表对图结构进行存储。
    采用Kosaraju算法,首先对原图进行DFS遍历,然后求出原图的逆图,按照对原图进行DFS遍历的search tree的所有节点的后序将所有顶点入栈,再将栈中元素逐一出栈,如果没有访问过,就将其作为根节点进行访问,每一棵树都是一个连通分量。
    然后处理收缩图,注意对当前搜索树已访问过的结点的判断。

    实现要点

    在唐神的悉心指导和几乎手把手的教学下,经过了一天多的浴火淬炼,完成了目前版本的代码。

    输入操作处理

    输入时有没有换行都应该不影响才对,因为OJ用重定向输入,自己测试可以使用文件重定向,显式使用eof的时候注意会不会多循环一次,之前的输入部分被批评写得很复杂,效率比不上stringstream,直接贴代码,

    修改前

    while (cin.getline(buf, MAX)) {
            char *r = strtok(buf, " ");
            if (r) {
                int head = atoi(r);
                //cout << head << endl;
                pMap[n][head] = 1;
            }
            else {
                continue;
            }
            char *s = strtok(NULL, " ");
            char tmp_str[MAX];
            if (s) {
                strcpy(tmp_str, s);
            }
            else {
                n++;
                continue;
            }
            int tmp;
            while (tmp_str) {
                tmp = atoi(tmp_str);
                //cout << tmp << endl;
                pMap[n][tmp] = 1;
                char *t = strtok(NULL, " ");
                if (t) {
                    strcpy(tmp_str, t);
                }
                else {
                    break;
                }
            }
            n++;
        }

    修改后

     string str;
        while (getline(cin, str)) {
            Vertex vertex;
            vertex.neighbor.empty();
            istringstream iss(str);
            int num;
            while (iss >> num) {
                vertex.neighbor.push_back(num);
            }
            graph.push_back(vertex);
            n++;
        }

    数据结构优化

    问题描述

    我一开始用的是邻接矩阵存储了图结构,而且用了全局变量,静态分配内存空间(一个很大很大的n,压缩图的空间和原图一样大)。初始化的过程使用memset函数的时间开销很大,导致时间超限

    解决方案

    “不要用固定的大小,用c语言的函数malloc,发现更大的数就realloc。realloc效率应该比较高,是用remap实现的,如果有足够的空间会在后面直接扩展而不会复制已有的元素。把一个点的基本信息放在结构体里面,并提供相应的默认构造函数,写的时候就会少很多麻烦。”
    “邻接矩阵的时间和空间开销太大,空间的开销可能让程序初始化有巨大的时间开销。邻接表的形式也比较好存,一次不能做完就不要一次做了。利用分治的思想,先把图存好,按序输入的,可以放到vector里面,动态增长,也不用管邻居现在的大小和存不存在,也就是说图和逆图最好分开。这些数据如果只是把图存起来的话用vector都是很好处理的。”
    “已经有图了,知道了大小,求逆图再一个循环也很容易,但是两个要是想一起做,就很麻烦,要固定的大小或者遇到更大的重新resize。”
    
    //一个点
    struct point {
        vector<int> neighbor_vec;
    }
    
    //点集构成图
    vector<point> vertexes;
    vector<point> reverse_vertexes;
     另外,定义一个构造函数就不需要手动初始化了。
    
     point(): color(WHITE) {}

    OJ要结合C和C++的优点
    C语言太麻烦就用C++的方法
    C++效率低就用相应的C语言函数

    算法设计逻辑

    寻找压缩图顶点之间的关系

    压缩图各个点之间的邻居关系可以在对原图的逆图进行DFS的过程中进行。当发现不是tree edge的时候,说明被访问过;如果着色不是和自己的相同,那么就一定是另一个强连通分量的,说明这两个连通分量有关系,就需要在压缩图之间加一条边。
    如果在对逆图进行DFS的过程判断压缩图顶点之间的关系,用邻接表存储,那么遇到重复的关系判断一下是否已经加进去了比较繁杂,可以用STL中的set存储边之间的关系

    SCC的重复计数问题

    考虑如下有向图,

    0->1
    0->2
    1->2

    在访问0,1,2之后还会再对顶点2进行访问,我的解决方案是添加了cur_mark标志位,用当前访问的根顶点对遍历过程中的所有顶点进行标记。
    然后,考虑如下输入:

    1 2
    2

    1 2

    在一个入度为0的顶点进行dfs不会有问题,但是由于total_impact的改变,其他入度为0的顶点的dfs就是累加的,相当于是重复的,最简单的方法是只保存那个入度为0的顶点的结果,然后把total_impact恢复回来。

    然而我又发现不能通过如下样例测试,

    1 2
    3
    3
    4 5
    6
    6

    2

    真相竟然是……

    在恢复时缺少了如下语句,

    SCCgraph[j].is_visited = false;

    这里写图片描述

    这里写图片描述

    展开全文
  • [图] 有向图的强连通分量-原理

    千次阅读 2018-08-14 14:44:51
    有向图G上,从某个顶点出发沿以【该顶点】为【尾的弧】进行DFS 并按其【所有邻接点】的【搜索都完成(即退出DFS函数)】的顺序将顶点排列起来 实现 对DFS做以下修改 在进入DFSTraverse时首先进行...

    相关链接

    1. Kosaraju算法:https://blog.csdn.net/summer_dew/article/details/83047190

    背景

    【无向图】如果从s到t存在一条路径,那么我们知道从t到s也存在一条路径
    【有向无环图(DAG)】如果从s到t存在一条路径,那么我们知道从t到s不存在有向路径
    【问题】但是,对于一般的有向图,知道t由s可达并没有给出s是否由t可达的信息
    【强连通分量的提出】为了理解有向图的结构,我们考虑强连通性(strong connectivity),它具有我们寻求的对称性。如果s和t是强连通的(顶点相互可达)–>那么根据定义,t和s也是强连通的
    【如何判断有向图是不是强连通】暴力判断:判断任意两个顶点s,t,看从s是否可以到t,从t是否可以到s。这个算法易于描述和实现,但需要代价很大
    【现代算法设计的胜利】现代算法设计能在线性时间内找出任何图的强分量,它要比蛮力算法快V倍。对于100个顶点,这些算法将比蛮力算法快100倍;对于1000个顶点,这些算法比蛮力算法块1000倍;对于设计数十亿顶点的问题也可以解决。

    有向图的强连通分量

    【强连通(strongly connected)】在有向图中,从我这可以走到你那,从你那能够走到我这–>我们俩强连通
    【强连通图】有向图G,任意两个顶点都强连通–>G是强连通图
    【非强连通图】有向图G,存在两个顶点不能够互相走通–>非强连通图
    【强连通分量】在非强连通图中,顶点最多最大的强连通图–>极大强连通子图–>强连通分量

    【举例】
    在这里插入图片描述
    连通分量

    1. {1,2,3,4}
    2. {5}
    3. {6}

    【求强连通分量】

    1. Kosaraju算法:O(N+M)
    2. Tarjan算法:O(N+M)
    3. Gabow算法
    展开全文
  • 程序允许输入一向图,或从文件读入一图,然后求出图的所有简单圈。 ******************************************************************************* package test; import java.util.ArrayList; import ...
  • 为了对该问题进行求解,提出了贪婪搜索算法(GP,greedy path),该算法先将一个有向无环转化为一棵深度为k+1的网树,然后计算每网树节点的树根叶子路径数,并以此计算中每个顶点的总路径数,之后从网树的第k+1层...
  • #include #include #include //该结构体用来表示从某个顶点可以到达的其他顶点 struct ENode {  int secPoint;//顶点号  int weight;  ENode *next;//指
  • 没有找到原文出处,请参考一下链接: http://www.cnblogs.com/hiside/archive/2010/12/01/1893878.html ... 一、无向图: 方法1: 如果存在回路,则必存在一子图
  • 关于结点无向图边数最多最少问题---深入剖析!

    千次阅读 多人点赞 2021-01-25 17:47:46
    其实这里公式:一向图(没有自环和重边),最多包含n(n-1)/2***条边,最少包含n-1条边。 解析: 那具体来说,这公式是咋来的呢?我来给大家深入解释一下。 假如说,如果你点,你会咋样连呢? 那...
  • 给定一个图,和一顶点src,找到从src到其它所有所有顶点的最短路径,中可能含有负权值的边。 Dijksra的算法是一贪婪算法,时间复杂度是O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在负权值边的中不适用,...
  • 判断一图是否有环 无向图 有向图

    千次阅读 2017-10-24 16:29:34
    一、无向图: 方法1: 如果存在回路,则必存在一子图,是一环路。环路中所有顶点的度>=2。  n算法:   第一步:删除所有度  第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶点重复...
  • 向图: 法1: 如果存在回路,则必存在一子图,是一环路。环路中所有顶点的度>=2。 n算法: 中 第一步:删除所有度 第... n算法分析: 由于m条边,n个顶点。如果m>=n,则根据图论知识可直接判断存在环路。
  • 图(有向图、无向图)

    万次阅读 2013-12-03 17:02:06
    ⑶均为 (Graph),它若干不同的点 v 1, v 2, …, v n,在其中一些点之间用直线或曲线连接。中的这些点被称为顶点 (vertex)或结点,连接顶点的曲线或直线称为边 (edge)。通常将这种由若干个顶点...
  • 有向图的强连通分量

    千次阅读 2015-04-03 11:10:25
     有向图强连通分量在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一...
  • 有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一...
  • 判断无向图中是否回路

    万次阅读 多人点赞 2014-12-15 17:05:10
     在有向图中,先找出入度为0的顶点,删除与这个顶点相关联的边(出边),将与这些边相关的其它顶点的入度减1,循环直到没有入度为0的定点。如果此时还有未被删除顶点,则必存在环路,否则不存在环路。
  • 问题描述: 有n个长为m+1的字符串,如果某个字符串的最后m字符与某个字符串的前m...相当于判断一个有向图是否存在环以及求该有向图的最长路径。 可用图的深度优先遍历算法来求解,图用邻接表表示。   1. 求解有
  • 【问题描述】一包含有2019结点的有向图最多包含多少条边?(不允许有重边)【答案提交】这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一整数,在提交答案时只填写这整数,填写多余的...
  • 概论

    2017-05-25 16:58:28
    n个顶点有向图n(n-1) 条边 G=(V,E) vertex edge E=(u,v)图算法的时间空间性能,都与图结构的具体实现方式紧密相关,假定图的顶点数为n,边数为e邻接矩阵:是图ADT最基本的实现方式,使用方阵A[n][n]表示由n个...
  •  printf("/n请输入有向图顶点数:");  scanf("%d",&g.vexnum);  }  i=g.vexnum*(g.vexnum-1);  printf("请输入有向图的边数:");  scanf("%d",&g.arcnum);   while(g.arcnum>i){  printf("/n输入有误,边数...
  • 有向图: 图必须是连通的,而且最多只能有两点入度不等于出度,而且这两点其中一点的入度+1=出度,另一点的出度+1=入度,如果有的点出度!=入度&amp;&amp;出度与入度的绝对值差还不等于1,则这图...
  • 基础知识: 欧拉道路:形象成为“一笔画”,即一笔可以经过所有的边,除了起点和终点外,其他点必定是入度=出度,即为偶点 ...有向图: 连通且最多只有两个顶点入度不等于出度,并且一点入...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,149
精华内容 5,659
关键字:

具有n个顶点的有向图最多有