有向路径检查 牛客网 程序员面试金典 C++ Python
题目描述对于一个有向图，请实现一个算法，找出两点之间是否存在一条路径。给定图中的两个结点的指针DirectedGraphNode* a, DirectedGraphNode* b(请不要在意数据类型，图是有向图),请返回一个bool，代表两点之间是否存在一条路径(a到b或b到a)。C++
class Path { public: bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b){ return check(a,b) || check(b,a); } bool check(UndirectedGraphNode* a, UndirectedGraphNode* b){ if (NULL == a || NULL == b) return false; if (a == b) return true; map<UndirectedGraphNode*, bool> dict; queue<UndirectedGraphNode*> que; que.push(a); while(!que.empty()){ UndirectedGraphNode* ptr = que.front(); dict[ptr] = true; for(int i = 0; i<ptr->neighbors.size();i++){ if((ptr->neighbors)[i] == b) return true; if(ptr->neighbors[i] && dict[ptr->neighbors[i]]!=true) que.push((ptr->neighbors)[i]); } que.pop(); } return false; } };Python
class Path: #run:321ms memory:5860k def checkPath(self, a, b): v1, v2 = set(), set() return self.dfs(v1, a, b) or self.dfs(v2, b, a) def dfs(self,v, t, end): if t == end:return True if t in v:return False v.add(t) for x in t.neighbors: if self.dfs(v, x, end):return True return False
转载于:https://www.cnblogs.com/vercont/p/10210315.html
相关资源：JAVA上百实例源码以及开源项目