网站建设中网页代码怎么利用互联网推广

176-图中两个点之间的路线

给出一张有向图，设计一个算法判断两个点 s 与 t 之间是否存在路线。

样例

如下图:

for s = B and t = E, return true
for s = D and t = C, return false

标签

Cracking The Coding Interview 深度优先搜索 宽度优先搜索

思路

从 s 点开始对图进行遍历，若可以遍历到 t ，则 s 与 t 之间是否存在路线
这里使用了图的宽度优先遍历

code

/*** 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) {// write your code hereint size = graph.size(), i = 0;if (size <= 0) {return false;}queue<DirectedGraphNode*> queue;map<DirectedGraphNode*, bool> map;for (i = 0; i < size; i++) {map[graph[i]] = false;if (s == graph[i]) {queue.push(graph[i]);}}while (!queue.empty()) {DirectedGraphNode* node = queue.front();queue.pop();map[node] = true;if (node == t) {return true;}for (i = 0; i < node->neighbors.size(); i++) {if (map[node->neighbors[i]] == false) {queue.push(node->neighbors[i]);}}}return false;}
};