注意,在复制图时必须得用一个栈将邻接表的顺序逆置,这样保存到新的图里面时邻接表的顺序才能和原来一样。代码如下:
public Graph(Graph G)
{
this(G.V());
this.E = G.E();
for(int v = 0; v < G.V(); v++)
{
Stack<Integer> reverse = new Stack<Integer>();
for(int w : G.adj(v))
reverse.push(w);
for(int w : reverse)
adj[v].add(w);
}
}
如果要时间为常数则可以在类中增加一个数组distTo[]
,其中每个元素代表该顶点到起点的距离。初始化时将数组初始化为无穷大,然后在bfs
中更新数组中的值。代码如下:
private void bfs(Graph G, int s)
{
Queue<Integer> q = new Queue<Integer>();
for (int v = 0; v < G.V(); v++)
distTo[v] = INFINITY;
distTo[s] = 0;
marked[s] = true;
q.enqueue(s);
while (!q.isEmpty())
{
int v = q.dequeue();
for (int w : G.adj(v))
{
if (!marked[w])
{
edgeTo[w] = v;
distTo[w] = distTo[v] + 1;
marked[w] = true;
q.enqueue(w);
}
}
}
}
参考这里。注意,题目中要求的是演员的Kevin Bacon
数,所以最后输出的时候要输出偶数下标的直方图。
代码见这里。很简单的代码,只要把书上的DegreesOfSeparation
中的BFS
换成DFS
就可以了。
官方给出的答案是56+40V+128E。但是我死活算不出这个结果...
一开始我的想法是对每个顶点维护一个布尔数组,在添加边时将数组对应的位置置位true
,例如,数组名为hasEdge
,插入2和3之间的一条边,那么就要将hasEdge[2][3]
和hasEdge[3][2]
都设为true。如果在插入边时返现对应位置已经为true
,则表明产生一条平行边,平行边数量加1。假设顶点数量为V
,边的数量为E
很明显可以看到,虽然这种算法的时间复杂度为O(1)
,但是空间复杂度为O(V^2)
,对于顶点数比较大的图来说这种算法是完全行不通的。
然后想到,对于用邻接表表示的图来说,如果3和2之间存在平行边,那么在3的邻接表中2一定出现了不止一次,那么通过遍历邻接表就能找到平行边。具体可以这样操作,对每一条邻接表,维护一个和顶点大小一样的数组,在遍历链表的过程中,数组每个位置的值就是该顶点在邻接表中出现的次数,那么当遍历完之后,如果数组中某处的值大于一,那么就出现了该值减一条平行边;对每个顶点都进行这样的遍历,并在遍历开始时将数组的值初始化为0,最后将统计出的平行边的条数除以2就是真正的平行边的条数。可以看到,这种算法的空间复杂度为O(V)
,时间复杂度为O(E)
。代码如下:
public class ParallelEdge
{
public static void initializeArray(int[] hasEdge)
{
for(int i = 0; i < hasEdge.length; i++)
hasEdge[i] = 0;
}
public static void main(String[] args)
{
Graph G = new Graph(new In(args[0]));
StdOut.println(G);
int[] hasEdge = new int[G.V()];
int parallelEdge = 0;
for(int v = 0; v < G.V(); v++)
{
initializeArray(hasEdge);
for(int w : G.adj(v))
{
hasEdge[w] += 1;
if(hasEdge[w] != 1)
parallelEdge += 1;
}
}
StdOut.println("Parallel Edge Numbers: " + parallelEdge / 2);
}
}
和无向图的一样。
False.
到了图论的习题开始不会做了QAQ。。。