[C++知识库]有向图的拓扑排序，c/c++描述

??谢谢bilibili懒猫老师的讲解。她一讲我就能听懂。看别的纸质书实在看不懂。这过了《数据结构》这门课，没了这位老师的讲解，咋整？
??有向图的拓扑排序，是这么个意思：对图的顶点进行排序，从左到右输出。对于图里任意一条边，边的起点都在终点的左面。对于排序中的任意两个顶点，这俩顶点要么没有边相连，要么左边的顶点一定是起点，右边的点是终点。带有这种要求的排序就叫拓扑排序。
??拓扑排序要求有向图里没有环。例如不允许点ABC构成环，A——>B——>C——>A。这样的环，如果对其进行拓扑排序的话，谁又能放在谁的左面呢？结果是这个环里的顶点一个也输出不了。如果拓扑排序的输出，顶点数少于总的顶点数，那么图里一定存在环。
??可以进行拓扑排序的有向图，又叫做AOV网，active on vertex network 。其不存在环。
??AOV网可以对应一些工程，顶点对应完成工程的步骤，有向边对应这些步骤之间的制约关系，先后关系。
??实现拓扑排序的步骤是：
??（1）输出入度为 0 的顶点，从图里删掉该点，并删除掉以它为起点的所有边；
??（2）重复以上步骤，直至图里没有顶点，或者剩下了环。
??只有作为弧的终点，入度为0的顶点才可能在队列里被输出，所以环里的顶点，虽然属于图，但永远不会进入队列，也不会被输出。

??程序实现时的一些关键点的处理：
??（1）根据拓扑排序的理论步骤，图的存储采用出边邻接表形式。
??（2）图里表头数组（该数组存储所有的表头顶点）的每个元素，也是结构体变量，为其加一个域，入度，表头顶点的入度。当一个顶点的入度为0，其可以进入队列存储，以待输出。该结构体的具体结构如下：

struct AdjListHead {
	int inDegree;
	char vertex;
	AdjaListNode* pt;
};

??（3）如何输出该拓扑序列：转换成程序的话，我们可以采用队列，队尾插入元素，队头弹出元素。从队头依次输出所有入度为0的顶点。每输出一个顶点，就修改其出边邻接表所有顶点的入度值，其值减1，若减后为0 ，则插入队列，表示可以输出，随后输出。出边邻接表，就是大家所说的邻接表，存储的是以表头顶点为起点的所有出边的终点。
??（4）也有一些地方使用栈进行拓扑排序输出。也是可以的。这里我们解释下，如果采用队列进行排序输出，如何就能保证了有向边的起点一定先输出，终点后输出，或者说序列中所有起点都在终点的前面（序列左面就是前面）？因为终点的度等于0之前，终点是不会进入队列的。只有当其起点进入了队列并且输出后，修改了终点顶点的入度值后，终点才有可能进入队列，所以队列的按头输出，一定可以保证是拓扑排序输出。栈也是一个道理。能插入栈的一定是入度为0的顶点。采用栈和队列对输出序列的影响是，如果图里一开始就有多个入度为 0 的顶点，这些顶点的排序问题。
??各函数功能如下：
??函数createGraphAdjMatrix：建立图的邻接矩阵。
??函数createGraphAdjList：建立图的邻接表。
??函数dispalyGraphAdjMatrix：输出图的邻接矩阵。
??函数displayGrapgAdjList：输出图的邻接表。
??函数topologicalSorting：对图进行拓扑排序输出。
??完整代码如下，先是main函数所在源文件：

#include<iostream>
#include<stdio.h>
using namespace std;
#define NUMVERTEX 6
#define INFINI 65555

struct GraphAdjaMatrix {
	char vertexes[NUMVERTEX];
	int edges[NUMVERTEX][NUMVERTEX];
	int numVertexes;
	int numEdges;
};

struct AdjaListNode {
	int indexOfVertex;
	int weightOfEdge;
	AdjaListNode* pt;
};

struct AdjListHead {
	int inDegree;
	char vertex;
	AdjaListNode* pt;
};

struct GraphAdjaList {
	AdjListHead vertexes[NUMVERTEX];
	int numVertexes;
	int numEdges;
};

extern void createGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix,
			int numVertexes,int numEdges,int edges[][NUMVERTEX],char vertexes[]);
extern void createGraphAdjList(GraphAdjaList &graphAdjList,
			int numVertexes, int numEdges, int edges[][NUMVERTEX], char vertexes[]);
extern void dispalyGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix);
extern void displayGrapgAdjList(GraphAdjaList &graphAdjList);
extern void topologicalSorting(GraphAdjaList& graphAdjList);

int main() {
	GraphAdjaMatrix graphAdjMatrix ;
	GraphAdjaList graphAdjList;
	int  numEdges = 9;
	int edges[][NUMVERTEX] = {	{0,INFINI,INFINI,INFINI,INFINI,INFINI},
								{1,0,INFINI,1,INFINI,INFINI},
								{1,INFINI,0,1,INFINI,INFINI},
								{1,INFINI,INFINI,0,INFINI,1},
								{INFINI,INFINI,1,1,0,1},
								{INFINI,INFINI,INFINI,INFINI,INFINI,0} };
	char vertexes[] = {'A','B','C','D','E','F'};

	createGraphAdjMatrix(graphAdjMatrix,NUMVERTEX,numEdges,edges,vertexes);
	createGraphAdjList(graphAdjList,NUMVERTEX,numEdges,edges,vertexes);

	dispalyGraphAdjMatrix(graphAdjMatrix);
	cout << endl;
	displayGrapgAdjList(graphAdjList);
	cout << endl;	

	cout << "topological sorting : ";
	topologicalSorting(graphAdjList);

	return 0;
}

接着是各函数所在源文件：

#include<iostream>
#include<stdio.h>
using namespace std;
#define NUMVERTEX 6
#define INFINI 65555

struct GraphAdjaMatrix {
	char vertexes[NUMVERTEX];
	int edges[NUMVERTEX][NUMVERTEX];
	int numVertexes;
	int numEdges;
};

struct AdjaListNode {
	int indexOfVertex;
	int weightOfEdge;
	AdjaListNode* pt;
};

struct AdjListHead {
	int inDegree;
	char vertex;
	AdjaListNode* pt;
};

struct GraphAdjaList {
	AdjListHead vertexes[NUMVERTEX];
	int numVertexes;
	int numEdges;
};

void createGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix,
	int numVertexes, int numEdges, int edges[][NUMVERTEX], char vertexes[]) {
	graphAdjMatrix.numVertexes = numVertexes;
	graphAdjMatrix.numEdges = numEdges;
	
	for (int i = 0; i < numVertexes; i++)
		graphAdjMatrix.vertexes[i] = vertexes[i];

	for (int row = 0; row < numVertexes; row++)
		for (int column = 0; column < numVertexes; column++)
			graphAdjMatrix.edges[row][column] = edges[row][column];
}

void createGraphAdjList(GraphAdjaList &graphAdjList,
	int numVertexes, int numEdges, int edges[][NUMVERTEX], char vertexes[]){
	graphAdjList.numEdges = numEdges;
	graphAdjList.numVertexes = numVertexes;

	for (int row = 0; row < numVertexes; row++) {
		graphAdjList.vertexes[row].pt = NULL;
		graphAdjList.vertexes[row].vertex = vertexes[row];
	
		graphAdjList.vertexes[row].inDegree = 0;
		for (int column = 0; column < numVertexes; column++)
			if (edges[column][row] != 0 && edges[column][row] != INFINI)
				graphAdjList.vertexes[row].inDegree++;
	}

	AdjaListNode* ptTail = NULL,*ptNew;
	int i, j;
	for ( i = 0; i < numVertexes; i++) 
		for (j = 0; j < numVertexes; j++) 
			if (edges[i][j] != 0 && edges[i][j] != INFINI) {
				ptNew = new AdjaListNode;

				ptNew->indexOfVertex = j;
				ptNew->weightOfEdge = edges[i][j];
			
				if (graphAdjList.vertexes[i].pt == NULL) {
					ptNew->pt = NULL;
					graphAdjList.vertexes[i].pt = ptNew;
					ptTail = ptNew;
				}
				else {
					ptNew->pt = ptTail->pt;
					ptTail->pt = ptNew;
					ptTail = ptNew;
				}
			}
}

void dispalyGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix) {
	cout << "adjacensy matrix :" << endl;
	int row,column;
	printf("%3c",' ');
	for (row = 0; row < graphAdjMatrix.numVertexes; row++)
		printf("%3c",graphAdjMatrix.vertexes[row]);
	printf("\n");
	for (row = 0; row < graphAdjMatrix.numVertexes; row++) {
		printf("%-3c", graphAdjMatrix.vertexes[row]);
		for (column = 0; column < graphAdjMatrix.numVertexes; column++)
			if (graphAdjMatrix.edges[row][column] == INFINI)
				printf("%3s", "∞");
			else
				printf("%3d",graphAdjMatrix.edges[row][column]);
		cout << endl;
	}
}

void displayGrapgAdjList(GraphAdjaList &graphAdjList) {
	cout << "graph adjacency list : " << endl;
	AdjaListNode* pt;
	int index;
	for (int i = 0; i < graphAdjList.numVertexes; i++) {
		printf("%2c:",graphAdjList.vertexes[i].vertex);
		pt = graphAdjList.vertexes[i].pt;
		while (pt != NULL) {
			index = pt->indexOfVertex;
			printf("%5c(%d)",graphAdjList.vertexes[index].vertex,pt->weightOfEdge);
			pt = pt->pt;
		}

		cout << "    入度为 ：" << graphAdjList.vertexes[i].inDegree;
		cout << endl;
	}
}

void topologicalSorting(GraphAdjaList& graphAdjList) {
	int indexQueue[NUMVERTEX * 2],head = 0,tail = -1 ;  // 定义队列
	
	for(int i = 0 ; i < graphAdjList.numVertexes ; i++)
		if (graphAdjList.vertexes[i].inDegree == 0) {
			tail++;
			indexQueue[tail] = i;
		}

	AdjaListNode* pt;

	while (head <= tail) {
		cout << graphAdjList.vertexes[indexQueue[head]].vertex << " ";
		
		pt = graphAdjList.vertexes[indexQueue[head]].pt;
		while (pt != NULL) {
			graphAdjList.vertexes[pt->indexOfVertex].inDegree--;
			if (graphAdjList.vertexes[pt->indexOfVertex].inDegree == 0) {
				tail++;
				indexQueue[tail] = pt->indexOfVertex;
			}
				
			pt = pt->pt;
		}
		head++;
	}
}

??对应的图和测试结果如下：


谢谢懒猫老师，谢谢阅读。