广度遍历算法探测两个节点之间的联通性并打印路径

19次阅读

共计 339 个字符,预计需要花费 1 分钟才能阅读完成。

有这么一堆有方向的图,
好比说有向图是这样子的:

A,B
B,C
A,D
E,F
G,Z
X,A
X,Y
A,E
E,R
C,E
E,F
E,B

现在需求是:输入起始节点和最终节点,可以返回一下连通性结果,如果是通的,并输出连通的路径(无需最短,如果有多条就输出多条)。根据网络搜索发现大致上应该是图的广度优先遍历算法,但在网上找了很多 Python 代码示例,都是输入一个起始节点,输出可能的最终节点,使用的还是现成包,改不动。

  1. 好比说最终调用函数 FindLine(A, C)
    就会尝试查找 A 开始 B 结果的这种路径。
    最终会输出
    A->B->C
    A->E->C

例外:
A->E->C->E->C(这种环一下子的就不必了吧。。)

  1. 好比说最终调用函数 FindLine(A, Z)
    那就是到不了,不通的

希望大神能给个 Demo,指点一二。

正文完
 0