我将CLRS第三版ch.22练习22.3-13中的算法简介中的单连通图定义称为A directed graph G = (V,E) is singly connected if G contains at most one simple path from u to v for all vertices u, v belongs to V。我注意到,图中的圈并不一定意味着图不是单连接的,因为涉及圈的路径不被视为简单路径。有向图中的一个简单圈可以由一组对应的边唯一地表示。让我们考虑一个满足以下两个性质的有向图:
(1)它在其DFS森林中只有树和背边,以及(2)表示图中每个简单循环的所有集合都是不
我写了一个算法来判断“一个无向图是否为树”。
Assumptions : graph G is represented as adjacency list, where we already know the number of vertices which is n
Is_graph_a_tree(G,1,n) /* using BFS */
{
-->Q={1} //is a Queue
-->An array M[1:n], such that for all i, M[i]=0 /* to mark visited vertices*/
问题详细信息:
拉什夫是EMLand的市长。EMLand由交叉口和街道组成。从每个交叉口到其他任何一个交叉口都有一条路径。交叉口用正整数1.n表示。一家建筑公司提供拉什夫来重建EMLand的所有街道,但拉什夫可以选择at most k of them to be rebuilt.。建筑公司为每条街道提供了一个新的长度,这意味着在重建街道后,街道的长度发生了变化。现在,拉什夫作为这座城市的市长,必须做出明智的选择,以便将所有交叉路口之间的路径长度之和降到最低。救救拉什夫!
算法:
标注:旧边长度为L,新长度为L',边集为E。
长度将减少的edges(E')的计数(edges(
我有一个无向图,完全图,并希望将它转换成一个有向无圈图,在每个节点之间有一个(单向)路径。为了开始,我想添加随机边和停止一旦所有节点连接。需要研究的是一个算法(使用Python,但任何语言都可以)。
因此,例如,这个图不再被进一步连接:
A ---- B A ---> B
\ / => /
\ / v
C C
,但在这种情况下,所有无向边都会变成有向边。
A ---- B A ---> B
\
下面是DFS的通用代码,带有标记后边缘和树边缘的逻辑。我的疑问是,顶点的背边会返回并指向祖先,而指向父节点的不是背边(假设是无向图)。在一个无向图中,我们在两个顶点x和y之间有一条来回的边,所以在我处理y时访问x之后,y将x作为相邻的顶点,但因为它已经被访问过了,所以代码会将它标记为后边。
我这么说对吗?在我的假设成立的情况下,我们是否应该添加任何额外的逻辑来避免这种情况?
DFS(G)
for v in vertices[G] do
color[v] = white
parent[v]= nil
time = 0
for v in verti
设G=(V,E)是一个无向图。如何使用以下DFS精确地计算长度为3的周期:
DFS(G,s):
foreach v in V do
color[v] <- white; p[v] <- nil
DFS-Visit(s)
DFS-Visit(u)
color[u] <- grey
foreach v in Adj[u] do
if color[v] = white then
p[v] = u; DFS-Visit(v)
color[u] <- black
每当我们发现一个已