首页 > 代码库 > 算法与数据结构基础10:C++实现——拓扑排序

算法与数据结构基础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)//即<i,j>∈E(G)
if(!visited[j])
DFSTopSort(G,j,T);
//以上语句完全类似于DFS算法
Push(&T,i); //从i出发的搜索已完成,输出i

}



八 代码

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

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

#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>

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<Vertex*> vertexStack;
	queue<Vertex*> 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 <cstdlib>

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

	system("pause");

	return 0;
}


假如有图如下:(就是用的前面两节的图)



结果:








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