数据结构——有向图（拓扑排序算法）

转自&＃xff1a;http://blog.chinaunix.net/uid-20384806-id-1954187.html

    　对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序&＃xff0c;是将G中所有顶点排成一个线性序列&＃xff0c;使得图中任意一对顶点u和v&＃xff0c;若 ∈E(G)&＃xff0c;则u在线性序列中出现在v之前。

下面是Java实现&＃xff1a;

/*** 有方向图* */
public class DirectedGraph {private final int MAX_VERTS &＃61; 20;private Vertex[] vertexList; // array of verticesprivate int[][] adjMat; // adjacency matrixprivate int nVerts; // current number of verticesprivate char[] sortedArray; // sorted vert labels/*** 默认构造函数 初始化邻接矩阵*/public DirectedGraph() {vertexList &＃61; new Vertex[MAX_VERTS];sortedArray &＃61; new char[MAX_VERTS];// 图的邻接矩阵adjacency matrixadjMat &＃61; new int[MAX_VERTS][MAX_VERTS];nVerts &＃61; 0;for (int j &＃61; 0; j 0) {int delVertex &＃61; getNoSuccessorVertex();if (-1 &＃61;&＃61; delVertex) {System.out.println("Error: This graph has cycles! It cannot be toplogical sorted.");return;}sortedArray[nVerts - 1] &＃61; vertexList[delVertex].label;deleteVertex(delVertex);}System.out.print("Topologically sorted order: ");for (int j &＃61; 0; j 0)// 大于0&＃xff0c;表明有边指向其他点&＃xff0c;说明有后继节点{isEdge &＃61; true;break; // OK&＃xff0c;继续下一个节点}}if (false &＃61;&＃61; isEdge)// 没有边&＃xff0c;表明没有后继节点{return row;}}return -1;}/*** 删除一个节点* * &＃64;param delVertex*/public void deleteVertex(int delVertex) {if (delVertex !&＃61; nVerts - 1)// 如果不是最后一个节点{// 在节点列表中删除这个节点&＃xff0c;所有后面的节点前移一格for (int i &＃61; delVertex; i }