有向图(7)--再谈可达性&&有向图总结

今天药忘吃喽~ 2022-08-18 02:59 144阅读 0赞

**顶点对的可达性。**给定一幅有向图，回答“是否存在一条从一个给定的顶点v到另一个给定的顶点w的路径？”等类似问题。

可以使用深度搜索来实现，无论对于稀疏还是稠密的图，它都是理想的解决方案，但它不适用于在实际应用中可能遇到的大型有向图，因为所需的空间和V²成正比，所需时间和V(V+E)成正比。

\-TransitiveClosure.h

#ifndef __TRANSITIVE_CLOSURE_H__
    #define __TRANSITIVE_CLOSURE_H__
    
    #include "Digraph.h"
    #include "DirectedDFS.h"
    
    class TransitiveClosure {
    private:
    	DirectedDFS* all;
    
    public:
    	TransitiveClosure(Digraph G);
    <span style="white-space:pre">	</span>~TransitiveClosure() { delete[] all; }
    	bool reachable(int v, int w) { return all[v].isMarked(w); }
    
    };
    
    TransitiveClosure::TransitiveClosure(Digraph G) {
    	all = new DirectedDFS[G.getV()];
    	for (int v = 0; v < G.getV(); ++v)
    		all[v].createDFS(G, v);
    }
    
    #endif

这里我稍微对之前的DirectedDFS做了修改，还有给Digraph的构造函数添加了默认值，因为new的时候只能调用默认构造函数，所以写了新的函数来重新构造bool\* marked

\-DirectedDFS.h

#ifndef __DIRECTED_DFS_H__
    #define __DIRECTED_DFS_H__
    
    #include "Digraph.h"
    
    // 解决单点可达性或者多点可达性
    class DirectedDFS {
    private:
    	bool* marked;
    
    public:
    	DirectedDFS(const Digraph& G = Digraph(), int s = 0);
    	DirectedDFS(const Digraph& G, std::list<int> ilst);
    	~DirectedDFS() { delete[] marked; }
    
    	bool isMarked(int v)const { return marked[v]; }
    
    	void createDFS(Digraph G, int s);	// 为了在TransitiveClosure中重新构造
    
    private:
    	void dfs(const Digraph& G, int v);
    };
    
    // constructor
    DirectedDFS::DirectedDFS(const Digraph& G, int s) {
    	if (0 == G.getV()) return;
    	marked = new bool[G.getV()];
    	for (int i = 0; i < G.getV(); ++i)
    		marked[i] = false;
    	dfs(G, s);
    }
    
    // constructor
    DirectedDFS::DirectedDFS(const Digraph& G, std::list<int> ilst) {
    	marked = new bool[G.getV()];
    	for (int i = 0; i < G.getV(); ++i)
    		marked[i] = false;
    	for (int v : ilst) {
    		if (!marked[v])
    			dfs(G, v);
    	}
    }
    
    void DirectedDFS::dfs(const Digraph& G, int v) {
    	marked[v] = true;
    	for (int w : G.getAdj(v)) {
    		if (!marked[w])
    			dfs(G, w);
    	}
    }
    
    // 重新构造DirectedDFS，和构造函数差不多了
    void DirectedDFS::createDFS(Digraph G, int s) {
    	if(NULL == marked) delete[] marked;
    	marked = new bool[G.getV()];
    	for (int i = 0; i < G.getV(); ++i)
    		marked[i] = false;
    	dfs(G, s);
    }
    
    
    #endif

测试用例 -main.cpp

![SouthEast][]

#include "TransitiveClosure.h"
    #include "Digraph.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);
    	}
    
    	TransitiveClosure tc(G);
    
    	int a, b;
    	for (;;) {
    		cout << "输入起点：";
    		cin >> a;
    		cout << "输入终点：";
    		cin >> b;
    		cout << "                      " 
    			<< a << " 到 " << b << "是";
    		if (!tc.reachable(a, b)) 
    			cout << "不";
    		cout << "可达的" << endl;
    	}
    
    	return 0;
    }

![Image 1][]

![SouthEast 1][]

有向图总结

![SouthEast 2][]

[SouthEast]: /images/20220731/27ece57992ca4275a6f42bda4532568b.png
[Image 1]: 
[SouthEast 1]: /images/20220731/7cd00fdec54b4aea8782229939f07f6f.png
[SouthEast 2]: /images/20220731/a351298d10e144e5a329513973bf3025.png