已知图中的两个结点的指针DirectedGraphNode* a和DirectedGraphNode* b(请不要在意数据类型,图是有向图),判断两点间是否存在一条路径并返回bool值,代表是否存在(a到b或b到a)。
题目分析:
这个题目考察的其实是有向图的遍历,图的遍历分为深度优先遍历和广度优先遍历,深度优先遍历用堆栈实现,广度优先遍历用队列实现,在该题目中给出了每个节点的子节点,所以最好用广度优先遍历。
图的广度优先遍历和树的层次遍历类似,但是不是完全相同,因为图是连通的,所以我们必须去标志那个节点被访问过,那个节点没有被访问过,最后如果全部访问完以后,还没有找到a到b的路径,则返回false。
注意知识点:
(1)图中有环,记得标记是否被访问
class Path { public: bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) { // write code here return check(a,b)||check(b,a); } bool check(UndirectedGraphNode* a, UndirectedGraphNode* b) { // write code here if(a==NULL||b==NULL) return false; if(a==b) return true; map<UndirectedGraphNode*,bool> map1; queue<UndirectedGraphNode*> que; que.push(a); while(!que.empty()) { UndirectedGraphNode* ptr=que.front(); map1[ptr]=true; for(int i=0;i<ptr->neighbors.size();i++) { if((ptr->neighbors)[i]==b) return true; if(ptr->neighbors[i]&&map1[ptr->neighbors[i]]!=true) que.push((ptr->neighbors)[i]); } que.pop(); } return false; } };
public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) { // write code here /* * 这里的left,right好像不太有意义,主要根据邻接矩阵遍历 * 利用栈,首先a自身入栈以及其临街矩阵所有节点入栈,入栈前都进行判断 * 若该点邻居都不是b,则该点出栈,继续上述遍历 * 为了防止环的产生,已经入栈过的点不再入栈,用map管理 */ return check(a,b) || check(b,a); } public boolean check(UndirectedGraphNode a, UndirectedGraphNode b) { // TODO Auto-generated method stub if(a == null || b == null){ return false; } if(a == b){ return true; } Map<UndirectedGraphNode, Boolean> checkedMap = new HashMap<UndirectedGraphNode, Boolean>(); LinkedList<UndirectedGraphNode> searchQueue = new LinkedList<UndirectedGraphNode>(); searchQueue.push(a); checkedMap.put(a, true); while(!searchQueue.isEmpty()){ UndirectedGraphNode currentNode = searchQueue.pop(); if(currentNode.neighbors != null){ for(int i = 0; i < currentNode.neighbors.size(); i++){ UndirectedGraphNode neib = currentNode.neighbors.get(i); if(neib != null){ if(neib == b){ return true; } if(checkedMap.get(neib) == null || !checkedMap.get(neib)){ searchQueue.push(neib); checkedMap.put(neib, true); } } } } } return false; }
public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) { return check(a,b) || check(b,a); } public boolean check(UndirectedGraphNode a, UndirectedGraphNode b){ if(a == null || b == null) return false; if(a == b) return true; if(a.label == -1) return false; a.label = -1; for(int i = 0;i < a.neighbors.size();i++){ if(check(a.neighbors.get(i),b)) return true; } return false; }
Map<UndirectedGraphNode, Boolean> visitedMap = new HashMap<>(); public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) { String method = "BFS"; switch (method) { case "DFS": if (checkDFS(a, b)) { return true; } else { visitedMap.clear(); return checkDFS(b, a); } case "BFS": return checkBFS(a, b) || checkBFS(b, a); default: //错误的选择 return false; } } /** * 深度优先搜索(递归) */ private boolean checkDFS(UndirectedGraphNode a, UndirectedGraphNode b) { if (a == null || b == null) { return false; } if (a == b) { return true; } visitedMap.put(a, true); for (UndirectedGraphNode neighbor : a.neighbors) { //下面的写法是错误的,原因是在这种情况下,如果a先访问邻居c就会最终返回true;如果a先访问到邻居d就会返回false。 // 而访问的顺序与存储的结构和存储的顺序有关,所以可能会存在一定概率出错。简单的说,这种写法的含义是,DFS搜索的到的第一条线路如果是要找到就返回true并不在继续找,如果不是返回false,也不会继续找其他线路了. // ↗ d → e // a // ↘ c → b // if (!visitedMap.containsKey(neighbor)) { // return checkDFS(neighbor, b); // } //没访问过等于:根本没包含 或者 包含了但是为false(其中第二种情况不可能存在,因为从来没赋值过false) //这种写法是正确的,含义是:找到了就直接返回true,并不再寻找下一条线路。如果没找到,继续for的下一个循环就行(也就是继续找其他线路,不会return false) if (!visitedMap.containsKey(neighbor) && checkDFS(neighbor, b)) { return true; } } return false; } /** * 广度优先搜索 */ private boolean checkBFS(UndirectedGraphNode a, UndirectedGraphNode b) { if (a == null || b == null) { return false; } if (a == b) { return true; } Queue<UndirectedGraphNode> queue = new LinkedList<>(); //用来标记是否访问过该节点 HashMap<UndirectedGraphNode, Boolean> visitedMap = new HashMap<>(); visitedMap.put(a, true); queue.offer(a); while (!queue.isEmpty()) { UndirectedGraphNode node = queue.poll();//从队列头部移除 for (UndirectedGraphNode neighbor : node.neighbors) { if (!visitedMap.containsKey(neighbor)) {//如果没访问过 if (neighbor == b) { return true; } visitedMap.put(neighbor, true); queue.offer(neighbor); } } } return false; }
class Path { public: bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) { map<UndirectedGraphNode*, bool> flag;//记录是否已经访问过 if(atob(a,b,flag)) return true;//检查a->b的路径 if(atob(b,a,flag)) return true;//检查b->a的路径 return false; } bool atob(UndirectedGraphNode* a, UndirectedGraphNode* b, map<UndirectedGraphNode*, bool> flag){//广度优先搜索 queue<UndirectedGraphNode*> nodes;//队列保存节点 if(a == b) return true;//最开始检查 nodes.push(a);//入列 while(!nodes.empty()){ UndirectedGraphNode* node = nodes.front(); nodes.pop();//出列 flag[node] = true;//标记访问 for(unsigned int i = 0; i < node->neighbors.size(); ++i){ UndirectedGraphNode* n = node->neighbors[i]//查询邻近节点 if(flag[n]) continue;//跳过已经访问过的 else{ if(n == b) return true;//查询正确 nodes.push(n);//否则入列 } } } return false;//找不到 } };
classPath { public: bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) { // write code here if(!a || !b) returnfalse; returncheckSingle(a, b) || checkSingle(b, a); } private: bool checkSingle(UndirectedGraphNode* a, UndirectedGraphNode* b){ queue<struct UndirectedGraphNode *> que;//BFS工作队列 que.push(a); while(!que.empty()){ //直到队空 UndirectedGraphNode* t = que.front(); que.pop();//出队 if(t == b) returntrue; //t的所有邻接点进队,晴空邻接点 vector<struct UndirectedGraphNode *>::iterator it; for(it = t->neighbors.begin(); it!=t->neighbors.end(); ++it){ //入队 que.push(*it); } t->neighbors.clear(); } returnfalse; } };
/*
struct UndirectedGraphNode {
int label;
vector<struct UndirectedGraphNode *> neighbors;
UndirectedGraphNode(int x) : label(x) {}
};*/
class Path {
public:
bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) {
// write code here
return bfs_helper(a, b) || bfs_helper(b, a);
}
bool bfs_helper(UndirectedGraphNode* a, UndirectedGraphNode* b){
if(a == NULL || b == NULL){
return false;
}
if(a == b){ // 这个条件判断特别重要!!!否则会造成一开始标记了a,导致在后面的判断中直接跳过了a
return true;
}
queue<UndirectedGraphNode*> q;
q.push(a);
set<UndirectedGraphNode*> visited; // 在搜索中需要一个数组用以标记已经访问过的数据
while(!q.empty()){
int q_size = q.size();
for(int i = 0; i < q_size; ++i){ // 并无实际意义,写成这样是为了便于理解BFS思想,i表示BFS搜索到第几层了
UndirectedGraphNode* cur = q.front();
visited.emplace(cur);
for(int j = 0; j < cur->neighbors.size(); ++j){
if(cur->neighbors[j] == NULL || visited.find(cur->neighbors[j]) != visited.end()){
continue;
}
if(cur->neighbors[j] == b){
return true;
}
q.push(cur->neighbors[j]);
}
q.pop();
}
}
return false;
}
};
class Path { public: bool BFS(UndirectedGraphNode *a, UndirectedGraphNode *b){ map<UndirectedGraphNode*, bool> vis; queue<UndirectedGraphNode*> q; if(a==b) return true; if(a && b){ q.push(a); while(!q.empty()){ UndirectedGraphNode *p = q.front(); q.pop(); vis[p] = true; for(int i=0;i<p->neighbors.size();i++){ UndirectedGraphNode *t = p->neighbors[i]; if(t==b) return true; else if(t!=NULL && !vis[t]) q.push(t); } } } return false; } bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) { return BFS(a,b) || BFS(b,a); } };
class Path { public: bool subCheckPath(UndirectedGraphNode* x, UndirectedGraphNode* y) { if (!x || !y) { return false; } queue<UndirectedGraphNode*> Q; set<UndirectedGraphNode*> V; Q.push(x); V.insert(x); while (!Q.empty()) { UndirectedGraphNode* node = Q.front(); if (node == y) { return true; } Q.pop(); V.insert(node); for (auto c : node->neighbors) { if (!V.count(c)) { Q.push(c); } } } return false; } bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) { return subCheckPath(a, b) || subCheckPath(b, a); } };
运行时间:18ms
占用内存:604k
public class Path { boolean isPath = false; HashSet <UndirectedGraphNode> set = new HashSet<>(); public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) { if (a==null || b==null) return false; this.set = new HashSet<>(); dfs(a,b); //a->b this.set =null; this.set = new HashSet<>(); dfs(b,a); //b->a return isPath; } public void dfs(UndirectedGraphNode root,UndirectedGraphNode toFind){ if (this.isPath ||root == null || this.set.contains(root)) return;//提早结束 if (root.label == toFind.label) this.isPath = true; this.set.add(root); for (UndirectedGraphNode node: root.neighbors) dfs(node,toFind); } }
import java.util.*; //通过做题来学习图的知识:邻居节点的遍历是指从neighbours存储中依次取出每一个节点, //查询两点间的路径是指:遍历a的邻居节点,如果邻居节点中存在b(即a.neighbours.get(X) ==b)则ab间存在路径 //还要考虑图是否有向的问题,如果有向需要进行a到b和b到a两次遍历 public class Path { public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) { return check(a,b)||check(b,a); } public boolean check(UndirectedGraphNode a, UndirectedGraphNode b){ if(a ==null||b ==null) return false; if(a ==b) return true; if(a.label ==-1) return false; a.label =-1; for(int i=0;i<a.neighbors.size();i++){ if(check(a.neighbors.get(i),b))return true; } return false; } }
import java.util.*; /* public class UndirectedGraphNode { int label = 0; UndirectedGraphNode left = null; UndirectedGraphNode right = null; ArrayList<UndirectedGraphNode> neighbors = new ArrayList<UndirectedGraphNode>(); public UndirectedGraphNode(int label) { this.label = label; } }*/ public class Path { public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) { // write code here if(a==b){ return true; } return helper(a,b)||helper(b,a); } public boolean helper(UndirectedGraphNode a, UndirectedGraphNode b){ Set<UndirectedGraphNode> set=new HashSet<UndirectedGraphNode>(); Queue<UndirectedGraphNode> queue=new LinkedList<UndirectedGraphNode>(); queue.add(a); set.add(a); UndirectedGraphNode temp=null; while(!queue.isEmpty()){ temp=queue.poll(); Iterator<UndirectedGraphNode> it=temp.neighbors.iterator(); while(it.hasNext()){ temp=it.next(); if(temp==b){ return true; }else if(!set.contains(temp)){ set.add(temp); queue.add(temp); } } } return false; } }
};
#include <vector> class Path { int la = 15151551; bool dfs(UndirectedGraphNode* a, UndirectedGraphNode* b) { a->label = la; bool ret = false; if(a == b )return true; for(int i=0;i<a->neighbors.size();i++) { if(a->neighbors[i]->label != la){ if( dfs(a->neighbors[i],b)) return true; } } return ret; } public: bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) { // write code here return dfs(a,b) || (la = 12312312) && dfs(b,a); } };
#Python版 #两次广搜,注意加个set用来防止重复搜索 # -*- coding:utf-8 -*- class UndirectedGraphNode: def __init__(self, x): self.label = x self.neighbors = [] class Path: def checkPath(self, a, b): # write code here if a ==b : return True queue = [] queue.append(a) hasSet = set() while len(queue) != 0: tmp = queue.pop(0) hasSet.add(tmp) for child in tmp.neighbors: if child == b: return True elif child not in hasSet: queue.append(child) queue = [] queue.append(b) hasSet=set() while len(queue) != 0: tmp = queue.pop(0) hasSet.add(tmp) for ch in tmp.neighbors: if ch == a: return True elif ch not in hasSet: queue.append(ch) return False
只是觉得自己写的简单点。 /* struct UndirectedGraphNode { int label; vector<struct UndirectedGraphNode *> neighbors; UndirectedGraphNode(int x) : label(x) {} };*/ class Path { public: bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) { // write code here if(a == NULL || b == NULL) return false; else return check(a, b) || check(b, a); } bool check(UndirectedGraphNode * a, UndirectedGraphNode * b) { queue<UndirectedGraphNode *> q; q.push(a); set<UndirectedGraphNode *> s; //存放访问过的节点 while(!q.empty()) { UndirectedGraphNode * front = q.front(); q.pop(); if(front == b) { return true; } s.insert(front); for(auto e : front->neighbors) { if(!s.count(e)) { q.push(e); } } } return false; } };
class Path { public: map<UndirectedGraphNode*,bool> nodestate;//default is false, not visited bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) { if(dfs(a,b)) return true;//forward nodestate.clear(); return dfs(b,a);//reverse } bool dfs(UndirectedGraphNode* a, UndirectedGraphNode* b) { if(a==0 || b==0) return false; nodestate[a]=true; if(a->label==b->label) return true; for(int i=0;i<(a->neighbors).size();i++) { UndirectedGraphNode* x=a->neighbors[i]; if(false==nodestate[x] && true==dfs(x,b)) return true; } return false; } };
import java.util.*; public class Path { public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) { // write code here return check(a,b)||check(b,a); } public boolean check(UndirectedGraphNode a, UndirectedGraphNode b){ if(a==null||b==null){ return false; } if(a==b){ return true; } Map<UndirectedGraphNode,Boolean> map = new HashMap<UndirectedGraphNode,Boolean>(); Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); queue.offer(a); while(!queue.isEmpty()){ UndirectedGraphNode u = queue.poll(); map.put(a,true); for(int i=0;i<u.neighbors.size();i++){ UndirectedGraphNode tmp = u.neighbors.get(i); if(tmp!=null&&!map.containsKey(tmp)){ if(tmp==b){ return true; }else{ queue.offer(tmp); map.put(tmp,true); } } } } return false; } }
# -*- coding:utf-8 -*- # class UndirectedGraphNode: # def __init__(self, x): # self.label = x # self.neighbors = [] class Path: # 递归 深度优先遍历 def judge(self, start, end, s): for i in start.neighbors: if i == end: return True if id(i) not in s: s[id(i)] = 1 return self.judge(i, end, s) return False # 栈 广度优先遍历 def judgeStack(self, start, end, s): stack = [] stack.append(start) while stack: node = stack.pop() for i in node.neighbors: if i == end: return True if id(i) not in s: stack.append(i) s[id(i)] = 1 return False # 队列 广度优先遍历 def judgeQueue(self, start, end, s): queue = [] queue.append(start) while queue: node = queue.pop(0) for i in node.neighbors: if i == end: return True if id(i) not in s: queue.append(i) s[id(i)] = 1 return False def checkPath(self, a, b): if a == b: return True visited = dict() visited[id(a)] = 1 if self.judgeStack(a, b, visited): return True visited = dict() visited[id(b)] = 1 if self.judgeStack(b, a, visited): return True return False