【正文】 w。 i = 0。 if (isOK == true)return。 if (level+1 Level)return。//大于搜索層次時(shí)不再深入 level++。 visited[v] = 1。//訪問(wèn)該節(jié)點(diǎn) count++。 (v, graph)。 if (v == end || () = MaxWeight) { w = 1。 if (v == endamp。amp。() = MaxWeight) { cout 深度優(yōu)先遍歷路徑為：。 (graph)。 /*if (MaxWeight()) MaxWeight = ()。*/ cout 路徑長(zhǎng)度為： () endl 訪問(wèn)節(jié)點(diǎn)數(shù)為： count endl 搜索層次：levelendl。 isOK = true。 } } else { w = (v)。//取當(dāng)前節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn) } while (w != 1) { if (!visited[w]) DepthFirstSearch(graph, w, stack)。//遞歸訪問(wèn) w = (v, w)。//取當(dāng)前節(jié)點(diǎn)的下一個(gè)子節(jié)點(diǎn) } visited[v] = 0。//返回時(shí)置該節(jié)點(diǎn)為未訪問(wèn) ( graph)。//將該節(jié)點(diǎn)彈出棧，并根據(jù)graph 中weight 的值更改當(dāng)前棧值 level。}//貪婪算法void Romania_Trip::Greedy_Algorithms(Graph amp。graph, int v){ int u, w。 SeqCQuene queue。//隊(duì)列存儲(chǔ)圖節(jié)點(diǎn)在圖中的索引值,優(yōu)先隊(duì)列，value小的在隊(duì)頭 visited[v] = 1。 if (v == end){ return。 } ( v, graph)。//圖節(jié)點(diǎn)按優(yōu)先順序入隊(duì)列 count++。 //訪問(wèn)節(jié)點(diǎn)數(shù)+1 while (())//寬度優(yōu)先，循環(huán) { ( amp。u)。//刪除隊(duì)列頭元素并返回刪除的數(shù)值 //cout u= u 。 w = (u)。 while (w != 1) { if (!visited[w]) { Visit(w, u)。//訪問(wèn)w節(jié)點(diǎn)，將way b 的指向更新 if (w == end) { //cout w==end。 count++。 return。 } ( w, graph)。 //圖節(jié)點(diǎn)按優(yōu)先順序入隊(duì)列 count++。 } w = (u, w)。 } }}//A*算法void Romania_Trip::AStar_Algorithms(Graph amp。graph, int v){ //i = 0。 count = 0。 int u, w。 SeqCQuene queue。 if (v == end) return。//到達(dá)終點(diǎn) (v, graph)。 count++。 while (()) { ( amp。u)。 if (u == end) { cout 路徑長(zhǎng)度為： (u) + (u) endl 訪問(wèn)節(jié)點(diǎn)數(shù)為： count endl。 return。 } w = ( u)。 while (w != 1) { int cost=(u) + (w,u)。 (w, cost)。//設(shè)置當(dāng)前節(jié)點(diǎn)移動(dòng)到目標(biāo)節(jié)點(diǎn)的預(yù)估費(fèi)用 ( w, graph)。//按預(yù)估費(fèi)用優(yōu)先入隊(duì)列 count++。 w = (u, w)。 } }}int Romania_Trip::GetCount(){ return count。}int Romania_Trip::GetMaxWeight(){ return MaxWeight。}int Romania_Trip::GetEnd(){ return end。}way *Romania_Trip::GetB(){ return b。}///*On holiday in Romania。 currently in AradFlight leaves tomorrow from BucharestFormulate goal：Be in BucharestFormulate problemStates: various citiesActions: drive between citiesFind solutionSequence of cities。 . Arad, Sibiu, Fagaras,Bucharest,*/includeincludeincludeincludeincludeiostreamincludectimeusing namespace std。int main(){ long int time1, time2。 cout endl 寬度優(yōu)先算法 endl。 Graph graphForBFS。 ()。 ()。 Romania_Trip trip。 time1 = clock()。 (graphForBFS, 0)。 time2 = clock()。 cout 耗時(shí)： time2 time1 ms endl。 cout endl 深度優(yōu)先算法 endl。 ()。 Stack stack。 Graph graphForDFS。//要重新取得原始的始地圖數(shù)據(jù)， ()。 ()。 time1 = clock()。 (graphForDFS, 0, stack)。 time2 = clock()。 cout 耗時(shí)： time2 time1 ms endl。 cout endl 貪婪算法 endl。 ()。 Graph graphForGreedy。//要重新取得原始的始地圖數(shù)據(jù)， ()。 ()。 time1 = clock()。 (graphForGreedy, 0)。 (graphForGreedy, (), (), 0)。 time2 = clock()。 cout 耗時(shí)： time2 time1 ms endl。 cout endl。 cout endl A星算法 endl。 ()。 Graph graphForAStar。//要重新取得原始的始地圖數(shù)據(jù)， ()。 ()。 time1 = clock()。 (graphForAStar, 0)。 time2 = clock()。 cout 耗時(shí)： time2 time1 ms endl。 cout endl。 return 0。}//includeincludeiostreamusing namespace std。Stack::Stack(){ top1 = 0。 weight = 0。}Stack::~Stack(){}bool Stack::StackNotFull(){ if (top1100) return true。 else return false。}bool Stack::StakNotEmpty(){ if (top10) return true。 else return false。}void Stack::StackPop(Graph amp。G){ int x。 if (StakNotEmpty()) { top1。 x = a[top1]。 if (top10) weight = [a [top1 1] ][x]。//彈出節(jié)點(diǎn)是weight的值要減少相應(yīng)的數(shù)值 } else cout 棧已空！ endl。}//將x入棧void Stack::StackPush(int x, Graph amp。G){ if (StackNotFull()) { a[top1] = x。 if (top10) weight = weight + [a[top1 1]][a[top1]]。 top1++。 } else cout 棧已滿！ endl。}void Stack::PrintStack(Graph amp。G){ int x= 0,nWeight=0。 while (xtop1) { cout [a[x]].cityname 。 if (x top1 1)cout 。 nWeight += weight。 x++。 }ifdef MY_DEBUG coutendl路徑長(zhǎng)度為：nWeightendl。endif cout endl。}int Stack::GetWeight(){ return weight。