一,拓扑排序的思想
拓扑排序是利用深度优先搜索对有向无环图进行线性排序,即对于一个图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); }
}
最后是DFS_VISIT,每次将结点涂黑(代码中是正方形)时将结点放到队列最前面
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);
}
更多推荐
拓扑,导论,算法
发布评论