已知图中的两个结点的指针DirectedGraphNode* a和DirectedGraphNode* b(请不要在意数据类型,图是有向图),判断两点间是否存在一条路径并返回bool值,代表是否存在(a到b或b到a)。
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; }
public class Path { public HashSet<UndirectedGraphNode> getNeighbors(UndirectedGraphNode a){ HashSet<UndirectedGraphNode> res=new HashSet<UndirectedGraphNode>(); Queue<UndirectedGraphNode> q=new LinkedList<UndirectedGraphNode>(); q.add(a); while(!q.isEmpty()){ UndirectedGraphNode node=q.poll(); if(!res.contains(node)){ res.add(node); q.addAll(node.neighbors); } } return res; } public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) { HashSet<UndirectedGraphNode> n_a=getNeighbors(a); HashSet<UndirectedGraphNode> n_b=getNeighbors(b); return n_a.contains(b)||n_b.contains(a); } }
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; }
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 for(int i=0;i<a.neighbors.size();i++) { if(a.neighbors.get(i).label==b.label)return true; else return checkPath(a.neighbors.get(i),b); } for(int i=0;i<b.neighbors.size();i++) { if(b.neighbors.get(i).label==a.label)return true; else return checkPath(b.neighbors.get(i),a); } return false; } }