有向路径检查

[编程题]有向路径检查

热度指数：18787 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知图中的两个结点的指针DirectedGraphNode* a和DirectedGraphNode* b(请不要在意数据类型，图是有向图),判断两点间是否存在一条路径并返回bool值，代表是否存在(a到b或b到a)。

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

算法知识视频讲解

Python

Pig-footed_Bandicoot

# write code here
    def helper(a,b):
        queue = [a]
        visited = set()
        while queue:
            pop  = queue.pop(0)
            if pop==b: return True

            if pop not in visited:visited.add(pop)

            for i in pop.neighbors:
                if i not in visited:
                    queue.append(i)
        return False
    return helper(a,b) or helper(b,a)

编辑于 2017-04-02 20:04:21 回复(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)