給出一張有向圖，設(shè)計(jì)一個(gè)算法判斷兩個(gè)點(diǎn) s 與 t 之間是否存在路線兜蠕。
這個(gè)圖的數(shù)據(jù)結(jié)構(gòu)是vector<DirectedGraphNode> graph；
graph是一個(gè)vector，vector里面的每一個(gè)元素都是圖里面的結(jié)點(diǎn)，比如a铸鹰，b，c皂岔，d等
每一個(gè)元素的類(lèi)型都是DirectedGraphNode蹋笼，通過(guò)neighbors可以訪問(wèn)這個(gè)結(jié)點(diǎn)指向的其他結(jié)點(diǎn)。
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
//創(chuàng)建一個(gè)隊(duì)列
if(s==t){
return true;
}
queue<DirectedGraphNode*> q;
map<DirectedGraphNode*,bool> visitnode;
//將s的相鄰結(jié)點(diǎn)加入到隊(duì)列
for(int i=0;i<s->neighbors.size();i++){
q.push(s->neighbors[i]);
}
while(q.empty()==false){
//獲得隊(duì)列的第一個(gè)元素
DirectedGraphNode * target=q.front();
q.pop();
//結(jié)點(diǎn)已經(jīng)訪問(wèn)
if(visitnode[target]==true){
continue;
}
visitnode[target]=true;
if(target==t){
return true;
}
else{
//target 不是t躁垛，那么將target的相鄰結(jié)點(diǎn)加入到隊(duì)列
Push_neighbors(q,target);
}
}
return false;
}
};
