一些和图论有关的算法
1. 拓扑排序
?
算法：首先对每个顶点计算它的入度。然后，将所有入度为0的顶点放到一个初始为空的队列（或栈）中。当队列不空时，删除一个顶点v，并将与v邻接的所有顶点的入度均减1。只要一个顶点的入度降为0，就把该顶点放入队列中。此时，拓扑排序就是顶点出队的顺序。使用邻接表的情况下，该算法时间复杂度为O(|E|+|V|)。
??
4. 具有负边值的图
负边权最短路径：首先，将s放到队列中。然后，在每一个阶段让一个顶点v出队。找到所有与v邻接的顶点w，使得dw?>?dv+cv,w。然后更新dw和路径，并在w不在队列中的时候把它放到队列中。可以为每个顶点设置一个比特位以指示它在队列中出现的情况。重复该过程直到队列为空。该算法复杂度为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);}}}
