有向图(4)--基于深度优先的拓扑排序

约定不等于承诺〃 2022-08-18 02:36 6阅读 0赞

前序：在递归调用之前将顶点加入队列

后序：在递归调用之后将顶点加入队列

逆后序：在递归调用之后将顶点压入栈

\-DepthFirstOrder.h

#ifndef __DEPTH_FIRST_ORDER_H__
    #define __DEPTH_FIRST_ORDER_H__
    
    #include "Digraph.h"
    #include <queue>
    #include <stack>
    
    // 基于深度优先的拓扑排序
    class DepthFirstOrder {
    private:
    	bool* marked;
    	std::queue<int> pre;			// 所有顶点的前序排列
    	std::queue<int> post;			// 所有顶点的后序排列 
    	std::stack<int> reversePost;	// 所有顶点的逆后序排列
    
    public:
    	DepthFirstOrder(const Digraph& G);
    <span style="white-space:pre">	</span>~DepthFirstOrder() { delete[] marked; }
    	std::queue<int> getPre()const { return pre; }
    	std::queue<int> getPost()const { return post; }
    	std::stack<int> getReversePost()const { return reversePost; }
    	
    private:
    	void dfs(const Digraph& G, int v);
    };
    
    DepthFirstOrder::DepthFirstOrder(const Digraph& G) {
    	marked = new bool[G.getV()];
    	for (int i = 0; i < G.getV(); ++i)
    		marked[i] = false;
    	for (int v = 0; v < G.getV(); ++v) {
    		if (!marked[v])
    			dfs(G, v);
    	}
    }
    
    void DepthFirstOrder::dfs(const Digraph& G, int v) {
    	pre.push(v);
    	marked[v] = true;
    	for (int w : G.getAdj(v)) {
    		if (!marked[w])
    			dfs(G, w);
    	}
    	post.push(v);
    	reversePost.push(v);
    }
    
    
    #endif

\-main.cpp 测试用例（如图）

![SouthEast][]

int main()
    {
    	int vNum, eNum;
    	cin >> vNum >> eNum;
    	Digraph G(vNum);
    
    	int v, w;
    	for (int i = 0; i < eNum; ++i) {
    		cin >> v >> w;
    		G.addEdge(v, w);
    	}
    
    	DepthFirstOrder dpo(G);
    
    	queue<int> pre = dpo.getPre();
    	queue<int> post = dpo.getPost();
    	stack<int> reversePost = dpo.getReversePost();
    
    	cout << "pre:" << endl;
    	while (!pre.empty()) { cout << pre.front() << " "; pre.pop(); }
    	cout << endl;
    
    	cout << "post:" << endl;
    	while (!post.empty()) { cout << post.front() << " "; post.pop(); }
    	cout << endl;
    
    	cout << "reversePost" << endl;
    	while (!reversePost.empty()) { cout << reversePost.top() << " "; reversePost.pop(); }
    	cout << endl;
    
    	return 0;
    }

![SouthEast 1][]

[SouthEast]: /images/20220731/1e67676150d44e44a37fb5077b0d41d0.png
[SouthEast 1]: /images/20220731/26867b98f61c404093606a0993e58c49.png