有向路径检查_

张佃鹏

题目分析：

这个题目考察的其实是有向图的遍历，图的遍历分为深度优先遍历和广度优先遍历，深度优先遍历用堆栈实现，广度优先遍历用队列实现，在该题目中给出了每个节点的子节点，所以最好用广度优先遍历。

图的广度优先遍历和树的层次遍历类似，但是不是完全相同，因为图是连通的，所以我们必须去标志那个节点被访问过，那个节点没有被访问过，最后如果全部访问完以后，还没有找到a到b的路径，则返回false。

注意知识点：

（1）图中有环，记得标记是否被访问

（2）要分别检测两个方向（a->b，b->a）

《程序员面试金典》--代码详细分析：

http://blog.csdn.net/zdplife/article/category/5799903

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;
    }
};

发表于 2015-10-21 11:36:49 回复(5)

Ron

	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;
	}

发表于 2016-04-28 17:34:40 回复(2)

Java

绝对凌度

先说说题目的问题：

1、题目指出是有向图，但命名时却用UndirectedGraphNode，不理解。

2、UndirectedGraphNode定义中个left和right实际上在解题时并不会用到，这会误导一部分人。

再说一下解题时需要注意的地方：

1、图会有环，需要标记被访问。

2、因为是有向图，需分别检测两个方向，即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;
    }

发表于 2017-05-11 17:37:51 回复(3)

Java

风之少年/fw

    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;
    }

编辑于 2016-11-19 14:19:42 回复(0)

Julius

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;//找不到
    }
};

发表于 2015-10-01 01:37:38 回复(3)

C/C++

🔍搜索offer中

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;
    }
};

编辑于 2016-10-23 22:48:13 回复(0)

C/C++

全论坛最菜

/*
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;
    }
};

编辑于 2019-08-23 01:24:29 回复(0)

C/C++

nbgao

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);
    }
};

发表于 2019-02-24 02:23:14 回复(0)

木然猫猫

注意审题：一条路径(a到b或b到a)

为了简单起见，可以使用检查单向路径的子函数。检查单向路径可以使用BFS。由于是图，所以要记录已访问节点，用set就行。

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

发表于 2018-12-26 11:42:56 回复(0)

uiereafd

dfs，存取已访问的点，提早结束

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);
    }
}

发表于 2017-06-01 21:20:59 回复(0)

阿狸不是猫

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;
    }
      
}

发表于 2017-05-18 11:30:26 回复(0)

xzy114

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;
        
    }
}

发表于 2017-04-05 22:58:50 回复(0)

Aurora1

class Path:
    def checkPath(self, a, b):
        v1, v2 = set(), set()
        return dfs(v1, a, b) or dfs(v2, b, a)

def dfs(v, t, end):
    if t == end:
        return True
    if t in v:
        return False
    v.add(t)
    for x in t.neighbors:
        if dfs(v, x, end):
            return True
    return False

发表于 2017-03-24 18:00:49 回复(0)

李0810

class Path {

public:

bool havePath(UndirectedGraphNode* a,UndirectedGraphNode*b){

for(int i=0;i<a->neighbors.size();i++)

if((a->neighbors)[i]->label==b->label)

return true;

else

return checkPath(a->neighbors[i],b);

return false;

}

bool checkPath(UndirectedGraphNode* a,UndirectedGraphNode*b){

if(havePath(a,b)||havePath(b,a))

return true;

return false;

}

};

发表于 2017-03-14 15:06:33 回复(0)

Lan.Bing#ZiYi

#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);
    }
};

发表于 2017-03-10 20:59:58 回复(1)

夜小楼Dream

#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

发表于 2017-01-24 11:42:47 回复(0)

yuexiang_fudan

只是觉得自己写的简单点。

/*
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;
    }
};

编辑于 2016-12-27 21:47:04 回复(0)

C/C++

周星星_

从起点遍历整个图，如果到了终点就返回true，否则false

这里采用DFS

和书上不同。这里graphNode没有isVisit属性，无法标记是否访问，所以用map辅助

结构体好好的干嘛起UndirectedGraphNode这个名字！！搞的看错题目没考虑正向逆向

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;
    }
};

编辑于 2016-08-13 14:00:29 回复(0)

AKG

最佳答案的java版。天啊，我居然翻译过来了。还挺顺。

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;
    }
}

编辑于 2016-08-13 12:18:25 回复(0)

Python

Yannyezixin

其实就是有向图的遍历问题，

可以使用深度优先遍历，实现起来比较简单。递归加判断结点结点是否已遍历

也可以使用广度优先遍历，利用队列

下面是两种解法

# -*- 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

编辑于 2016-08-08 10:35:37 回复(0)

有向路径检查

说明：本题目包含复杂数据结构UndirectedGraphNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题