请教一个图论算法

wangyanping · 发表于 2020-3-4 19:00:01

在一个无向图中，给出两个点u和v，并且u和v间没有边，求出这两个点间最多的不相交的简单路径数目？

aog777ys · 发表于 2020-5-21 00:15:01

网络流吧

菜鸟级高手 · 发表于 2020-5-21 12:15:01

我觉得用广度搜索是很容易实现的

wangyanping · 发表于 2020-5-21 16:30:01

菜鸟级高手：我也考虑过广度搜索，但是没有一个比较好的方式来解决“不相交”以及最优化这两个限制？你能够说的具体点吗？

菜鸟级高手 · 发表于 2020-5-24 15:30:01

每遍历一个元素就打上标记，标记清除之前不再被访问，可以避免“相交”
你说的最优化指什么啊？

wangyanping · 发表于 2020-5-27 19:30:01

最优化指：最后的不相交路径的数目最多。

如果按照你的方法，那算法的复杂度很高

cocosex · 发表于 2020-8-11 17:15:01

最大流

dommionr · 发表于 2020-8-13 11:00:01

如果这个题很好的解决了，那么
google那一道题目就简单了

请问 u，v之间是否存在一条经过K-1个节点的路径（可以重复）。

dommionr · 发表于 2020-8-13 11:15:01

认为用网络流的朋友们，说说，你们怎么想的？

wangyanping · 发表于 2020-8-14 14:00:01

bigc： u，v之间是否存在一条经过K-1个节点的路径： google的题可以用矩阵运算来求，用求传递闭包的方法来求

		自动登录	找回密码
密码			立即注册