算法与数据结构基础10：C++实现――拓扑排序

一定义

拓扑排序是对有向无环图(Directed Acyclic Graph简称DAG)顶点的一种排序，
它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。

二先决条件

能够进行拓扑排序图有两个先决条件：有向、无环，即有向无环图。

三偏序全序

连通图：任意两点之间都存在至少一条边
偏序：非连通图（有向无环图满足偏序关系）
全序：单连通图

四结果唯一性

对于仅满足偏序关系的有向无环图中，因为有两个点之间的关系是不确定的，所以导致排序的结果是不唯一的。
满足全序关系的有向无环图，两个点之间存在有向边的，因此排序结果唯一。

五入度排序

该方法的每一步总是输出当前无前趋(即入度为零)的顶点，输出“拓扑次序”。
其抽象算法可描述为：
NonPreFirstTopSort(G){//优先输出无前趋的顶点
while(G中有入度为0的顶点)do{
　　　　从G中选择一个入度为0的顶点v且输出之；
　　　　从G中删去v及其所有出边；
　　}
　　if(输出的顶点数目<|V(G)|)//若此条件不成立，则表示所有顶点均已输出，排序成功。
Error("G中存在有向环，排序失败！")；
}
注意：
无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的入度，可保存各顶点当前的入度。
为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点：
在开始排序前，扫描对应的存储空间，将入度为零的顶点均入栈(队)。以后每次选入度为0的顶点时，只需做出栈(队)操作即可。

六出度排序

该方法的每一步均是输出当前无后继(即出度为0)的顶点，输出“逆拓扑次序”。
算法的抽象描述为：
NonSuccFirstTopSort(G){//优先输出无后继的顶点
while(G中有出度为0的顶点)do {
从G中选一出度为0的顶点v且输出v；
从G中删去v及v的所有入边
}
if(输出的顶点数目<|V(G)|)
Error("G中存在有向环，排序失败!")；
}

七深度优先

当从某顶点v出发的DFS搜索完成时，v的所有后继必定均已被访问过(想像它们均已被删除)，
此时的v相当于是无后继的顶点，因此在DFS算法返回之前输出顶点v即可得到 DAG的逆拓扑序列。
其中第一个输出的顶点必是无后继(出度为0)的顶点，它应是拓扑序列的最后一个顶点。
若希望得到的不是逆拓扑序列，可增加T来保存输出的顶点。若假设T是栈，并在DFSTraverse算法的开始处将T初始化，
利用DFS求拓扑序列的抽象算法可描述为：
void DFSTopSort(G，i，T){
//在DisTraverse中调用此算法，i是搜索的出发点，T是栈
int j；
visited[i]=TRUE； //访问i
for(所有i的邻接点j)//即 ∈E(G)
if(!visited[j])
DFSTopSort(G，j，T)；
//以上语句完全类似于DFS算法
Push(&T，i)； //从i出发的搜索已完成，输出i

}

八代码

只实现了出度的，另外两种差不多，没有写。

// GraphList.h（在此文的代码基础上修改算法与数据结构基础8：C++实现有向图――邻接表存储）

#include 
   
    
#include 
    
      #include 
     
       #include 
      
        using namespace std; // 边 struct Edge{ int vName; int weight;// 权值 struct Edge* next; }; // 顶点(链表头) struct Vertex{ int vName; int in;// 入度 int out; // 初度 struct Edge* next; }; // 有向图 class GraphList { public: ~GraphList(); void createGraph(); void printGraph(); bool topsortInDegree(); bool topsortOutDegree(); private: // 1. 输入定点数 void inputVertexCount(); // 2. 生成定点数组 void makeVertexArray(); // 3. 输入边数 void inputEdgeCount(); // 4. 输入边的起始点 void inputEdgeInfo(); // 5. 添加边节点至对应的链表中 void addEdgeToList(int vFrom, int weight, int vTo); private: int m_vCount; int m_eCount; Vertex* m_vVertex; }; GraphList::~GraphList(){ for (int i = 0; i < m_vCount; ++i){ Edge* tmp = m_vVertex[i].next; Edge* edge = NULL; while(tmp){ edge = tmp; tmp = tmp->next; delete edge; edge = NULL; } } delete[] m_vVertex; } void GraphList::inputVertexCount() { cout << "please input count of vertex:"; cin >> m_vCount; } void GraphList::makeVertexArray() { m_vVertex = new Vertex[m_vCount]; // 初始化 for (int i = 0; i < m_vCount; ++i){ m_vVertex[i].vName = i; m_vVertex[i].next = NULL; m_vVertex[i].in = 0; m_vVertex[i].out = 0; } } void GraphList::inputEdgeCount() { cout << "please input count of edge:"; cin >> m_eCount; } void GraphList::inputEdgeInfo() { cout << "please input edge information:" << endl; for (int i = 0; i < m_eCount; ++i){ cout << "the edge " << i << ":" << endl; // 起点 int from = 0; cout << "From: "; cin >> from; // 权值 int weight = 0; cout << "Weight:"; cin >> weight; // 终点 int to = 0; cout << "To: "; cin >> to; cout << endl; addEdgeToList(from, weight, to); } } void GraphList::addEdgeToList(int vFrom, int weight, int vTo) { Edge* edge = new Edge(); edge->vName = vTo; edge->weight = weight; edge->next = NULL; Edge* tmp = m_vVertex[vFrom].next; if (tmp){ while(tmp->next){ tmp = tmp->next; } tmp->next = edge; }else{ m_vVertex[vFrom].next = edge; } ++m_vVertex[vTo].in; // 终点入度加1 ++m_vVertex[vFrom].out; // 起点初度加1 } void GraphList::printGraph() { for (int i = 0; i < m_vCount; ++i){ Edge* tmp = m_vVertex[i].next; cout << "list:" << m_vVertex[i].vName << "(in:" << m_vVertex[i].in << ")"<< "->"; while(tmp){ cout << "(weight:" << tmp->weight << ")"; cout << tmp->vName << "->"; tmp = tmp->next; } cout << "NULL" << endl; } } bool GraphList::topsortInDegree() { stack
       
         vertexStack; queue
        
          vertexQueue; int* degree = new int[m_vCount];// 声明一个临时变量，保存入度值，作操作，避免影响原始节点中的数据 // 1 统计入度为0的点 for(int i = 0; i < m_vCount; ++i){ degree[i] = m_vVertex[i].in; if(!degree[i]){ vertexStack.push(&m_vVertex[i]); } } int count = 0; while(!vertexStack.empty()){ // 保存入度为0的点 Vertex* tmp = vertexStack.top(); vertexStack.pop(); vertexQueue.push(tmp); ++count; // 2 从图中删除该结点以及它的所有出边（即与之相邻点入度减1） Edge* edge = tmp->next; while(edge){ Vertex* vertex = &m_vVertex[edge->vName]; --degree[edge->vName]; if (!degree[edge->vName]){ vertexStack.push(vertex); } edge = edge->next; } } // 判断是否有环 if (count < m_vCount) { return false; } // 输出排序结果 while(!vertexQueue.empty()){ Vertex* tmp = vertexQueue.front(); vertexQueue.pop(); cout << tmp->vName << " "; } cout << endl; delete[] degree; return true; } // ************************************************************************** // 流程控制 // ************************************************************************** void GraphList::createGraph() { inputVertexCount(); makeVertexArray(); inputEdgeCount(); inputEdgeInfo(); }

// main.cpp

// test for GraphList
#include "GraphList.h"
#include 
   
    

int main()
{
	GraphList graph;
	graph.createGraph();
	graph.printGraph();
	graph.topsort();

	system("pause");

	return 0;
}

假如有图如下：（就是用的前面两节的图）

结果：

一 定义

二 先决条件

三 偏序全序

四 结果唯一性

五 入度排序

六 出度排序

七 深度优先

八 代码

一定义