有向图(2)--深度优先搜索&&广度优先搜索

旧城等待， 2022-08-18 02:21 117阅读 0赞

\-DepthFirstDirectedPaths 深度优先搜索

解决单点有向路径。给定一幅有向图和一个起点s，回答“从s到给定目的顶点v是否存在一条有向路径?如果有，请找出这条路径”等类似问题。

#ifndef __DEPTH_FIRST_PATHS_H__
    #define __DEPTH_FIRST_PATHS_H__
    
    #include "Digraph.h"
    #include <stack>
    
    class DepthFirstDirectedPaths {
    private:
    	bool* marked;	// 是否标记过
    	int* edgeTo;	// 指向索引的点
    	int start;		// 起点
    
    public:
    	DepthFirstDirectedPaths(const Digraph& G, int s);
    	~DepthFirstDirectedPaths() { delete[] marked; delete[] edgeTo; }
    
    	bool hasPathTo(int v)const { return marked[v]; }
    	std::stack<int> pathTo(int v)const;
    
    private:
    	void dfs(const Digraph& G, int v);
    };
    
    // constructor
    DepthFirstDirectedPaths::DepthFirstDirectedPaths(const Digraph& G, int s) {
    	start = s;
    	marked = new bool[G.getV()];
    	edgeTo = new int[G.getV()];
    	for (int i = 0; i < G.getV(); ++i) {
    		marked[i] = false;
    		edgeTo[i] = i;
    	}
    	dfs(G, s);
    }
    
    void DepthFirstDirectedPaths::dfs(const Digraph& G, int v) {
    	marked[v] = true;
    	for (int w : G.getAdj(v)) {
    		if (!marked[w]) {
    			edgeTo[w] = v;
    			dfs(G, w);
    		}
    	}
    }
    
    // return the path in a stack
    std::stack<int> DepthFirstDirectedPaths::pathTo(int v)const {
    	std::stack<int> stk;
    	while (v != start) {
    		stk.push(v);
    		v = edgeTo[v];
    	}
    	stk.push(start);
    	return stk;
    }
    
    
    #endif

结合上一篇博客的Digraph.h

测试-main,cpp

#include "Digraph.h"
    #include "DirectedDFS.h"
    #include "DepthFirstDirectedPaths.h"
    #include <iostream>
    using namespace std;
    
    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);
    	}
    
    	DepthFirstDirectedPaths dfp(G, 0);
    
    	for (int i = 0; i < vNum; ++i) {
    		cout << 0 << " to " << i << ": ";
    		if (dfp.hasPathTo(i)) {
    			stack<int> stk = dfp.pathTo(i);
    			while (!stk.empty()) {
    				cout << stk.top() << " ";
    				stk.pop();
    			}
    		}
    		cout << endl;
    	}
    
    	return 0;
    }

![SouthEast][]

\-BreadthFirstDirectedPaths.h 广度优先搜索

单点最短有向路径。给定一幅有向图和一个起点s，回答“从s到给定目的顶点v是否存在一条有向路径？”如果有，找出其中最短的那条（所含边数最少）。等类似问题

#ifndef __BREADTH_FIRST_DIRECTED_PATHS_H__
    #define __BREADTH_FIRST_DIRECTED_PATHS_H__
    
    #include "Digraph.h"
    #include <stack>
    #include <queue>
    
    class BreadthFirstDirectedPaths {
    private:
    	bool* marked;
    	int* edgeTo;
    	int start;
    
    public:
    	BreadthFirstDirectedPaths(const Digraph& G, int s);
    	~BreadthFirstDirectedPaths() { delete[] marked; delete[] edgeTo; }
    
    	bool hasPathTo(int v)const { return marked[v]; }
    	std::stack<int> pathTo(int v)const;
    
    private:
    	void bfs(const Digraph& G, int v);
    
    };
    
    // constructor
    BreadthFirstDirectedPaths::BreadthFirstDirectedPaths(const Digraph& G, int s) {
    	start = s;
    	marked = new bool[G.getV()];
    	edgeTo = new int[G.getV()];
    	for (int i = 0; i < G.getV(); ++i) {
    		marked[i] = false;
    		edgeTo[i] = i;
    	}
    	bfs(G, s);
    }
    
    void BreadthFirstDirectedPaths::bfs(const Digraph& G, int v) {
    	marked[start] = true;	// 初始化标记起点
    	std::queue<int> q;
    	q.push(start);
    	int tmp;
    	while (!q.empty()) {
    		tmp = q.front();
    		marked[tmp] = true;
    		q.pop();
    		for (int w : G.getAdj(tmp)) {
    			if (!marked[w]) {
    				edgeTo[w] = tmp;
    				q.push(w);
    			}
    		}
    	}
    }
    
    // pathTo
    std::stack<int> BreadthFirstDirectedPaths::pathTo(int v)const {
    	std::stack<int> stk;
    	while (v != start) {
    		stk.push(v);
    		v = edgeTo[v];
    	}
    	stk.push(start);
    	return stk;
    }
    
    
    #endif

测试-main.cpp

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);
    	}
    
    	BreadthFirstDirectedPaths bfp(G, 0);
    
    	for (int i = 0; i < vNum; ++i) {
    		cout << 0 << " to " << i << ": ";
    		if (bfp.hasPathTo(i)) {
    			stack<int> stk = bfp.pathTo(i);
    			while (!stk.empty()) {
    				cout << stk.top() << " ";
    				stk.pop();
    			}
    		}
    		cout << endl;
    	}
    
    	return 0;
    }

![SouthEast 1][]

![SouthEast 2][]

这是示例的有向图

[SouthEast]: /images/20220731/ecaf879c392e4ed58266b49adc0d119b.png
[SouthEast 1]: /images/20220731/45d49c16f53247ed8091fe056b9a32ba.png
[SouthEast 2]: /images/20220731/1da8984057d24e239d9a4b960f053918.png