LintCode 176: Route Between Two Nodes in Graph (BFSDFS经典题)

Route Between Two Nodes in Graph 中文English Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Example Given graph:

A----->B----->C \ | \ | \ | \ v ->D----->E

Example 1: Input:s = B and t = E, Output:true

Example 2: Input:s = D and t = C, Output:false

解法1：BFS 代码如下：

/** * Definition for Directed graph. * struct DirectedGraphNode { * int label; * vector<DirectedGraphNode *> neighbors; * DirectedGraphNode(int x) : label(x) {}; * }; * */ 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) { if (s->neighbors.size() == 0) return false; if (s == t) return true; queue<DirectedGraphNode *> q; q.push(s); while(q.size() > 0) { DirectedGraphNode * currNode = q.front(); q.pop(); for (int i = 0; i < currNode->neighbors.size(); ++i) { if (currNode->neighbors[i] == t) { return true; } else { q.push(currNode->neighbors[i]); } } } return false; } };

解法2：BFS+Visited //memorization版本 代码如下:

/** * Definition for Directed graph. * struct DirectedGraphNode { * int label; * vector<DirectedGraphNode *> neighbors; * DirectedGraphNode(int x) : label(x) {}; * }; * */ 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) { if (s->neighbors.size() == 0) return false; if (s == t) return true; queue<DirectedGraphNode *> q; unordered_set<DirectedGraphNode *> visited; q.push(s); visited.insert(s); while(q.size() > 0) { DirectedGraphNode * currNode = q.front(); q.pop(); for (int i = 0; i < currNode->neighbors.size(); ++i) { if (visited.find(currNode->neighbors[i]) != visited.end()) { continue; } if (currNode->neighbors[i] == t) { return true; } else { q.push(currNode->neighbors[i]); visited.insert(currNode->neighbors[i]); } } } return false; } };

解法3：DFS 注意：不用visited也可以，但是速度会慢些。

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) { if (graph.size() == 0) return false; if (s == t) return true;

int N = graph.size(); for (int i = 0; i < graph.size(); ++i) { visited[graph[i]] = 0; } return dfs(s, t); }

private: bool dfs(DirectedGraphNode * source, DirectedGraphNode * target) { if (source == target) return true;

if (visited[source] == 1) return false; visited[source] = 1; for (int i = 0; i < source->neighbors.size(); ++i) { if (dfs(source->neighbors[i], target)) return true; } return false; } map<DirectedGraphNode *, int> visited;

};