Shortest path in complement graph

问题描述

      Shortest path in complement graph.:Given a graph G, design an algorithm to find the shortest path (number of edges) between s and every other vertex in the complement graph G'. The complement graph contains the same vertices as G but includes an edge v-w if and only if the edge v-w is not in G. Can you do any better than explicitly computing the complement graph G' and running BFS in G'?

问题分析

　　这是一个 比较有意思的问题，它不是一个简单的BFS应用。里面还有一些稍微的变换。

　　首先一个，对于一个图的complement graph来说，它是针对每个节点取所有原来和它不相邻的节点建立直接连接。比如说对如下的图来说：

　　它对应的complement graph如下：

 

 

　　所以这种转换就是针对每个节点将它原来的邻接边换成以前没有邻接的节点。不过，问题里要求计算这个complement graph的最短路径。所以一种办法就是我们根据一个图，先计算它的complement graph。然后再用BFS的方式来计算它的最短路径。这里假定图里的所有边都是一样的，没有特定的权值差别。 可是以这种办法计算的效率如何呢？对于每个节点，我们要对它的边重新计算一遍，所以每个节点的边构造时间就有V，所以光遍历这所有的V个节点它的总体时间复杂度就为V * V了。这里就超出了前面的期望结果。

　　所以，这里需要做一个调整。我们可以继续利用BFS的方法，不过这里需要做一点调整。每次我们碰到一个节点的时候，要取它的非当前邻接节点作为后续的候选遍历节点，然后将这个节点加入到队列里。按照这个思路，我们可以得到如下的代码实现：

 

public class ComplementGraph {
	
	private boolean[] marked;
	private int[] distTo;
	private Set<Integer> set;
	public ComplementGraph(Graph g) {
		marked = new boolean[g.vertices()];
		distTo = new int[g.vertices()];
		for(int i = 0; i < g.vertices() i++) {
			distTo[i] = Integer.MAX_VALUE;
		}
	}

	public bfs(Graph g, int s) {
		Queue<Integer> queue = new LinkedList<>();
		marked[s] = true;
		distTo[s] = 0;
		queue.add(s);
		while(!queue.isEmpty()) {
			int e = queue.remove();
			List<Integer> list = makeComplement(set, g.adj(e));
			for(int i : list) {
				if(!marked[i]) {
					marked[i] = true;
					distTo[i] = distTo[e] + 1;
					queue.add(i);
				}
			}
		}
	}

	private List<Integer> makeComplement(Set<Integer> set, List<Integer> adj) {
		// make a complement list which is in set but not in adj
	}

}

　　这里就是稍微增加了一个方法在每次遍历一个节点的时候先计算它的complement vertices。这样问题就解决了。 

 

 

参考材料

http://stackoverflow.com/questions/24476027/shortest-path-in-a-complement-graph-algorithm

 http://algs4.cs.princeton.edu/41graph/BreadthFirstPaths.java.html