Route Between Two Nodes in Graph

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

http://www.lintcode.com/en/problem/route-between-two-nodes-in-graph/

Discussion

典型的图的遍历问题。DFS BFS秒写。

Solution

DFS recersion

class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @param s: the starting Directed graph node
     * @param t: the terminal Directed graph node
     * @return: a boolean value
     */
    bool hasRoute(vector<DirectedGraphNode*> graph,
                  DirectedGraphNode* s, DirectedGraphNode* t) {
        unordered_set<DirectedGraphNode*> visited;
        if(s == t) return true;
        visited.emplace(s);
        for(auto const& node : s->neighbors) {
            if(hasRouteHelper(node, t, visited)) 
                return true;
        }
        return false;
    }
    bool hasRouteHelper(DirectedGraphNode *node, DirectedGraphNode *target, 
    unordered_set<DirectedGraphNode*> &visited) {
        if(node == target) return true;
        visited.emplace(node);
        for(auto const& n : node->neighbors) {
            if(visited.find(n) == visited.end()) {
                visited.emplace(n);
                if(hasRouteHelper(n, target, visited)) return true;
            }
        }
        return false;
    }
};

DFS iteration

bool hasRoute(vector<DirectedGraphNode*> graph,
                  DirectedGraphNode* s, DirectedGraphNode* t) {
        unordered_set<DirectedGraphNode*> visited;
        if(s == t) return true;
        visited.emplace(s);
        stack<DirectedGraphNode*> stk;
        stk.emplace(s);
        while(!stk.empty()) {
            DirectedGraphNode *cur = stk.top();
            bool all = true;
            for(auto const& node: cur->neighbors) {
                if(visited.find(node) == visited.end()) {
                    if(node == t) return true;
                    visited.emplace(node);
                    stk.emplace(node);
                    all = false;
                    break;
                }
            }
            if(all)
                stk.pop();
        }
        return false;
    }

BFS

bool hasRoute(vector<DirectedGraphNode*> graph,
                  DirectedGraphNode* s, DirectedGraphNode* t) {
        unordered_set<DirectedGraphNode*> visited;
        if(s == t) return true;
        visited.emplace(s);
        queue<DirectedGraphNode*> que;
        que.emplace(s);
        while(!que.empty()) {
            DirectedGraphNode *cur = que.front();
            que.pop();
            if(cur == t) return true;
            for(auto const& node: cur->neighbors) {
                if(visited.find(node) == visited.end()) {
                    visited.emplace(node);
                    que.emplace(node);
                }
            }
        }
        return false;
    }

Follow up

还可以扩展以下问题：

• 两个node之间的所有路径/路径个数
• 两个node之间的最短路长度/最短路径个数/所有最短路径
• 参考Word Ladder I II