PROBLEM SET
图论
按知识点筛选题目，系统巩固该考点。
题目列表
共 207 题
A61303
如图所示，图中每条边上的数字表示该边的长度，则从 A 到 E 的最短距离是_________。
2014年
--
--
A61336
6 个顶点的连通图的最小生成树，其边数为（ ）
2015年
--
--
A61363
设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有（ ）个顶点。
2016年
--
--
A61360
Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则是：如果某人 A 向他（她）的朋友 B 分享了某张照片，那么 B 就可以对该照片进行评论；如果 B 评论了该照片，那么他（她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论（除非 A 也向他（她）分享了该照…
2016年
--
--
A61452
由四个没有区别的点构成的简单无向连通图的个数是( )。
2018年
--
--
A61610
对于有 n个顶点、m条边的无向连通图 (m>n)，需要删掉（ ）条边才能使其成为一棵树。
2021年
--
--
A61602
以 a为起点，对右边的无向图进行深度优先遍历，则 b、c、d、e四个点中有可能作为最后一个遍历到的点的个数为（ ）。
2021年
--
--
A63549
游乐场的各区域之间都有路相连，相邻两个游乐区域的距离如下图所示。乐乐想从“秋千”区，到“跷跷板”区，请问最短距离是多少?( )
计算思维组
--
--
A61248
无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图 G 有 7 个顶点，则它 共有( )条边。
2011年
--
--
A61161
有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为_____。
2008年
--
--
A61591
G是一个非连通简单无向图（没有自环和重边），共有 36条边，则该图至少有（ ）个点。
2021年
--
--
A61583
有如下的有向图，节点为 A, B, … , J, 其中每条边的长度都标在图中。则节点 A到节点 J的最短路径长度为（ ）。
2021年
--
--
A61517
具有n个顶点，e条边的图釆用邻接表存储结构，进行深度优先遍历运算的 时间复杂度为()
2020年
--
--
A61512
对一个n个顶点、m条边的带权有向简単图用Dijkstra算法计算単源最短 路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为()。
2020年
--
--
A61475
G是一个非连通无向图(没有重边和自环)，共有28条边，则该图至少有( )个顶点
2019年
--
--
A62020
假设n是图的顶点的个数，m是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于m=θ(n)的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小。
2023年
--
--
A62017
以下连通无向图中，( )一定可以用不超过两种颜色进行染色。
2023年
--
--
A62010
在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少，一棵树可能有多个重心，请问下面哪种树一定只有一个重心？（）
2023年
--
--
A61396
设 G 是有 n 个结点、m 条边（n ≤ m）的连通图，必须删去 G 的（ ）条边， 才能使得 G 变成一棵树。
2017年
--
--
A61393
由四个不同的点构成的简单无向连通图的个数是（ ）。
2017年
--
--