算法导论 22.4 拓扑排序

一，拓扑排序的思想

        拓扑排序是利用深度优先搜索对有向无环图进行线性排序，即对于一个图G进行拓扑排序后，所有结点按线性排放，凡是在图G中u在v前面，拓扑排序后u也一定在v前面。

        常见的拓扑排序的应用比如早上穿衣的顺序，袜子必须在穿鞋前穿好，领带必须在衬衫穿好后才能戴。

二，拓扑排序算法介绍

        我们对有向无环图进行DFS操作，并将结点按结束时间逆序线性排列

三，拓扑排序伪代码

TOPLOGICAL_SORT(G)

1. call DFS(G) to pute finishing times v.f for each vertex v

2. as each vertex is finished,insert it onto the front of a linked list

3. return the linked list of vertices

总共就三步，先对图G进行DFS，然后每当一个结点被访问完毕（标为黑色），将他放到一个队列的最前端，即先访问完的结点一个在队列最后，最后返回这个队列

四，拓扑排序的复杂度

时间复杂度：

        拓扑排序的时间复杂度就是DFS的时间复杂度，即O(V+E)

五，拓扑排序的代码

首先是拓扑排序，创建了一个队列，将他传给DFS，最后返回该队列

deque<Node *> TOPOLOGICAL_SORT(Graph * graph)//拓扑排序
{deque<Node *> topoNodes;DFS(graph，topNodes);return topoNodes;
}

然后是DFS，调用DFS_VISIT时把topNodes传过去

void DFS(Graph * graph, Node * startNode,deque<Node *> &topoNodes)  
{  for (int i = 0; i < graph->getNodeList().size(); i++) {  graph->getNodeList()[i]->setShape(CIRCLE);  graph->getNodeList()[i]->setPrevNode(NULL);  }  int time = 0;  int id = startNode->getId();  for (int i = 0; i < id; i++) {  if (graph->getNodeList()[i]->getShape() == CIRCLE)  DFS_VISIT(graph->getNodeList()[i], time,topoNodes);  }  for (int i =id; i < graph->getNodeList().size(); i++) {  if (graph->getNodeList()[i]->getShape() == CIRCLE)  DFS_VISIT(graph->getNodeList()[i], time,topoNodes);  }  
} 

void DFS_VISIT(Node * node, deque<Node *> &topoNodes)
{node->setShape(TRIANGLE);for (int i = 0; i < node->getAdjNodeList().size(); i++){Node *v = node->getAdjNodeList()[i];if (v->getShape() == CIRCLE){v->setPrevNode(node);DFS_VISIT(v, topoNodes);}}node->setShape(SQUARE);topoNodes.push_front(node);
}