一些和图论有关的算法

1. 拓扑排序

 

算法：首先对每个顶点计算它的入度。然后，将所有入度为0的顶点放到一个初始为空的队列（或栈）中。当队列不空时，删除一个顶点v，并将与v邻接的所有顶点的入度均减1。只要一个顶点的入度降为0，就把该顶点放入队列中。此时，拓扑排序就是顶点出队的顺序。使用邻接表的情况下，该算法时间复杂度为O(|E|+|V|)。

public void topsort() throws CycleFoundException {
	Queue<Vertex> q = new Queue<Vertex>();
	int counter = 0;
		
	for each Vertex v
		if (v.indegree == 0)
			q.enqueue(v);
		
	while (!q.isEmpty()) {
		Vertex v = q.dequeue();
		v.topNum = ++counter;
		
		for each Vertex w adjacent to v
			if (--w.indegree == 0) 
				q.enqueue(w);
	}
	
	if (counter != NUM_VERTICES)
		throw new CycleFoundException();
}

 

 

2. 无权最短路径

算法：首先，将开始顶点放入队列中，距离为0。当队列不空时，删除一个顶点v，检查与v邻接的所有顶点w，如果w的距离是INFINITY，那么w的距离加1，路径设为v，并将w放入队列中。使用邻接表的情况下，该算法时间复杂度为O(|E|+|V|)。

public void unweighted(Vertex s) {
	Queue<Vertex> q = new Queue<Vertex>();
	
	for each Vertex v
		v.dist = INFINITY;
	
	s.dist = 0;
	q.enqueue(s);
	
	while (!q.isEmpty()) {
		Vertex v = q.dequeue();
		
		for each Vertex w adjacent to v
			if (w.dist == INFINITY) {
				w.dist = v.dist + 1;
				w.path = v;
				q.enqueue(w);
			}
	}
}

 

 

3. 赋权最短路径

算法：使用Dijkstra算法。在所有unknown顶中选择具有最小dv的顶点v，将其设为known。对于所有与v邻接的顶点，如果d_v+c_v,w比d_w小，则更新d_w为d_v+c_v,w。该算法的时间复杂度为O(|V|²)。如果图是稠密的，该算法是最优的。如果图是稀疏的，可将距离存储在优先队列中，这样复杂度为O(|E|log|V|)。

public void dijkstra(Vertex s) {
	for each Vertex v {
		v.dist = INFINITY;
		v.known = false;
	}
	
	s.dist = 0;
	
	for (; ;) {
		Vertex v = smallest unknown distance vertex;
		if (v == NOT_A_VERTEX)
			break;
		v.known = true;
		
		for each Vertex w adjacent to v
			if (!w.known) {
				if (v.dist + cvm < w.dist) {
					// update w
					decrease(w.dist to v.dist + cvm);
					w.path = v;
				}
			}
	}
}
	
public void printPath(Vertex v) {
	if (v.path != null) {
		printPath(v.path);
		System.out.print(" to ");
	}
	System.out.print(v);
}

 

 

4. 具有负边值的图

负边权最短路径：首先，将s放到队列中。然后，在每一个阶段让一个顶点v出队。找到所有与v邻接的顶点w，使得d_w > d_v+c_v,w。然后更新d_w和路径，并在w不在队列中的时候把它放到队列中。可以为每个顶点设置一个比特位以指示它在队列中出现的情况。重复该过程直到队列为空。该算法复杂度为O(|E|*|V|)。

 

public void weightedNegative(Vertex s) {
	Queue<Vertex> q = new Queue<Vertex>();
	
	for each Vertex v
		v.dist = INFINITY;
	
	s.dist = 0;
	q.enqueue(s);
	
	while (!q.isEmpty()) {
		Vertex v = q.dequeue();
		
		for each Vertex w adjacent to v
			if (v.dist + cvw < w.dist) {
				// update w
				w.dist = v.dist + cvw;
				w.path = v;
				if (w is not already in q)
					q.enqueue(w);
			}
	}
}

 

 

 

5. 无圈图最短路径

算法：使用拓扑顺序选择顶点来改进Dijkstra算法。由于选择和更新可以在拓扑排序的时候进行，因此算法能够一趟完成。因为当一个顶点v被选取之后，按照拓扑排序的法则它没有从unknown顶点发出的进入边，因此它的距离d_v不会再被降低。使用这种算法，不需要优先队列，时间复杂度为O(|E|+|V|)。

 

public void weightedNegative(Vertex s) {
	Queue<Vertex> q = new Queue<Vertex>();
	
	for each Vertex v {
		v.dist = INFINITY;
		if (v.indegree == 0) {
			v.dist = 0;
			q.enqueue(v);		
		}		
	}	
	
	while (!q.isEmpty()) {
		Vertex v = q.dequeue();
		
		for each Vertex w adjacent to v {
			if (v.dist + cvw < w.dist) {
				w.dist = v.dist + cvw;
				w.path = v;
			}
			if (--w.indegree == 0)
				q.enqueue(w);
		}
	}		
}