设G= (V,E)是一个有向图,以邻接列表格式给出。定义有向图G‘= (V,E'),其中边(u,v)∈E’当且仅当(v,u)∈E(即G‘反转G中每个边的方向)。描述了一种在O时间内求G‘邻接表表示法的算法。
是否有一种简单的方法来反演邻接表?
说如果是:
a-> b
b-> de
c-> c
d-> ab
e->
to:
a-> d
b-> ad
c-> c
d-> ab
e-> b
我必须反转给定的有向图,以便顶点保持不变,但边在相反的方向上。我的图由一个graph类表示,该类包含一个顶点的ArrayList,每个Vertex对象都有它的编号和相邻顶点的ArrayList。我的代码给出了错误的答案,因为在循环的每次迭代中,顶点的相邻列表的大小都会发生变化。我如何修复我的代码?
public void reverse() {
ArrayList < Vertex > adjacentOfi = new ArrayList < Vertex > ();
int k;
for (int i = 1; i < vertices
算法
For each edge (u, v) in the Adjacency list:
If u and v do not belong to the same set:
Union(u, v)
else:
return true // cycle detected
return false
图
(1)-(2)
邻接表
1个-> 2
2个-> 1
不相交集
{1},{2}}
迭代1
边e= (1,2)
工会(1,2)
不相交集={1,2}
迭代2
边e= (2,1)
2和1都属于同一个集合,因此该算法检测一个循环。很明显,图不包含循环。
该算法对有向图是完美的。请帮
我正在寻找一种有效的方法来实现一个只知道提前边数的加权无向图。
示例输入:
N(边数)
A B x (x是A到B的距离)
。
。
我考虑使用Node*的邻接表(我需要知道邻居)和存储在动态哈希表中的节点(我不知道我将使用多少个节点,所以我需要一个动态搜索/插入容器)。
有没有更好的方法呢?
抱歉,我的英语不好!:D
程序的输入是图中的边集。例如,考虑以下简单的有向图:
a -> b -> c
这个图的边集是
{ (b, c), (a, b) }
因此,给定一个有向图作为一组边,如何确定该有向图是否为树?如果它是一棵树,那么树的根节点是什么?
首先,我想看看如何表示这个图,邻接表/邻接矩阵/其他东西?如何利用您选择的表示法来有效地回答上述问题?
编辑1:
有些人正在指导如何使用DFS进行周期检测,但问题是从哪个节点启动DFS。因为它是一个有向图,所以我们不能从一个随机节点启动DFS,例如,如果我从顶点'c‘启动一个DFS,它将不会继续进行,因为没有后边可以去到任何其他节点。这里的后续问题