给出一张有向图,设计一个算法判断两个点 s 与 t 之间是否存在路线。
这个图的数据结构是vector<DirectedGraphNode> graph;
graph是一个vector,vector里面的每一个元素都是图里面的结点,比如a,b,c,d等
每一个元素的类型都是DirectedGraphNode,通过neighbors可以访问这个结点指向的其他结点。
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
*/
void Push_neighbors(queue<DirectedGraphNode*>& q,DirectedGraphNode * target){
for(int i=0;i<target->neighbors.size();i++){
q.push(target->neighbors[i]);
}
}
bool hasRoute(vector<DirectedGraphNode*> graph,DirectedGraphNode* s, DirectedGraphNode* t) {
// write your code here
//创建一个队列
if(s==t){
return true;
}
queue<DirectedGraphNode*> q;
map<DirectedGraphNode*,bool> visitnode;
//将s的相邻结点加入到队列
for(int i=0;i<s->neighbors.size();i++){
q.push(s->neighbors[i]);
}
while(q.empty()==false){
//获得队列的第一个元素
DirectedGraphNode * target=q.front();
q.pop();
//结点已经访问
if(visitnode[target]==true){
continue;
}
visitnode[target]=true;
if(target==t){
return true;
}
else{
//target 不是t,那么将target的相邻结点加入到队列
Push_neighbors(q,target);
}
}
return false;
}
};