我有一个无向图,完全图,并希望将它转换成一个有向无圈图,在每个节点之间有一个(单向)路径。为了开始,我想添加随机边和停止一旦所有节点连接。需要研究的是一个算法(使用Python,但任何语言都可以)。
因此,例如,这个图不再被进一步连接:
A ---- B A ---> B
\ / => /
\ / v
C C
,但在这种情况下,所有无向边都会变成有向边。
A ---- B A ---> B
\
我的意思是有向图可以有一个自循环,所以我不明白为什么一个无向图不能有它(CLRS说如果没有一个有效的理由它是被禁止的)。
Example:
G_directed = (V,E) is a directed graph
Say this graph has the vertex set V = {1,2,3,4,5,6}
With edges E = {(1,2),(2,2),(2,4),(2,5),(4,1),(4,5),(5,4),(6,3)}
-----------------------------------------------------------------
Say