已知无向图g,写一个算法判断是否存在一条从v0出发 - 已解决

已知无向图g,写一个算法判断是否存在一条从v0出发,包含所有节点的简单路径

收藏：

点赞数：

评论数：

1个回答

核心思想就是对图进行遍历,至于选择DFS(深度优先搜索)还是BFS(广度优先搜索)要根据情况考虑,如果不光需要知道能否有路径到达,还要知道有多少条路径,可以考虑采用DFS.如果只是判断是否存在路径,则只需广度优先搜索即可.从一个点,向外扩展到其它的点,再从这些点又开始向开扩展,直到没有节点可以被扩展即可判断是否存在路径.再打个比方,好比在一个点倒水,这些水会通过有向边流到其它的点,再在这些上一步流到的点继续倒水,它又会继续向周边通过有向边流到其他的点,一直重复,直到没有新的点有水流到.

PS:在不统计路径数量的前提下,选择BFS时间复杂度远低于DFS,速度更快.

点赞数：

评论数：

相关问题

求算法：欧拉路Description定义：图G的欧拉回路是包含图G所有边的一个简单回路,而欧拉路径则是包含所有边的一个简

点赞数：
0
回答数：
1
一个有多个顶点的带权无向图,从中选取部分点,设计一个从起点出发经过这些顶点并回到顶点的最短路径的算法

点赞数：
0
回答数：
1
离散数学欧拉路径和欧拉回路问题无向连通图G具有一条欧拉路径当且仅当G具有零个或两个奇数次数的顶点与一个无向连通图是欧

点赞数：
0
回答数：
1
G是n阶简单无向图,如果图G中任意两点的度数之和大于等于n-1,证明图G是连通图

点赞数：
0
回答数：
1
设G是6阶无向简单图(6阶指顶点共6个),证明G或它的补图中存在3个顶点彼此相邻

点赞数：
0
回答数：
1
已知n个顶点的有向图,用邻接矩阵表示,编写算法计算每对顶点的最短路径

点赞数：
0
回答数：
1
1．证明在具有n个顶点的简单无向图G中,至少有两个顶点的度数相同.

点赞数：
0
回答数：
1
以无向连通图G是一颗无向树当且仅当G中?

点赞数：
0
回答数：
1
无向图g有7个顶点若不存在由奇数条边构成的简单回路则它至多有条边

点赞数：
0
回答数：
2
试证明：对于一个无向图G = (V, E)，若G中各顶点的度均大于或等于2，则G中必有回路。

点赞数：
0
回答数：
1

关注公众号

一起学习，一起涨知识