1樓:匿名使用者
廣度優先copy用佇列,深度優先用棧。簡單說明bai如下:
廣度優先:當一du個節點zhi被加入佇列時,要標記為已遍歷,遍歷過
dao程中,對於佇列第一個元素,遍歷其所有能夠能一步達到的節點,如果是標記未遍歷的,將其加入佇列,從第一個元素出發所有能一步直接達到的節點遍歷結束後將這個元素出列。
深度優先:當遍歷到某個節點a時,如果是標記未遍歷,將其入棧,遍歷它能夠一步直接達到的節點,如果是標記未遍歷,將其入棧且標記為已遍歷,然後對其進行類似a的操作,否則找能夠一步直接達到的節點進行類似操作。直到所有能夠一步直接達到的節點都已遍歷,將a出棧。
這裡使用「能夠能一步達到的節點」而非「與其相鄰的節點」是考慮到有向圖因素。
具體可以找個圖,然後使用廣度和深度演算法搜尋一遍,每步自己手工修改佇列和棧就明白怎麼回事了。
農夫過河 資料結構程式設計 50
2樓:匿名使用者
**如下
#include
using namespace std;
#define vertexnum 16//最大頂點數
typedef struct // 圖的頂點
vertex;
typedef struct
adjgraph; // 定義圖的鄰接矩陣儲存結構
bool visited[vertexnum] = ; // 對已訪問的頂點進行標記(圖的遍歷)
int retpath[vertexnum] = ; // 儲存dfs搜尋到的路徑,即與某頂點到下一頂點的路徑
// 查詢頂點(f,w,s,v)在頂點向量中的位置
int locate(adjgraph *graph, int farmer, int wolf, int sheep, int veget)
}return -1; //沒有找到此頂點
} // 判斷目前的(f,w,s,v)是否安全
bool issafe(int farmer, int wolf, int sheep, int veget)
else
} // 判斷狀態i與狀態j之間是否可轉換
bool isconnect(adjgraph *graph, int i, int j)
if (graph->vertex[i].sheep != graph->vertex[j].sheep)
if (graph->vertex[i].veget != graph->vertex[j].veget)
// 以上三個條件不同時滿足兩個且農夫狀態改變時,返回真, 也即農夫每次只能帶一件東西過橋
if (graph->vertex[i].farmer != graph->vertex[j].farmer && k <= 1)
else
} // 建立連線圖
void createg(adjgraph *graph)
}}}}// 鄰接矩陣初始化即建立鄰接矩陣
graph->vertexnum = i;
for (i = 0; i < graph->vertexnum; i++)
else }}
return;
} // 判斷在河的那一邊
char* judgement(int state)
// 輸出從u到v的簡單路徑,即頂點序列中不重複出現的路徑
void printpath(adjgraph *graph, int start, int end)
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
} // 深度優先搜尋從u到v的簡單路徑 //dfs--depth first search
void dfspath(adjgraph *graph, int start, int end)
for (i = 0; i < graph->vertexnum; i++)
}}int main()
return -1;}
深度優先搜尋遍歷和廣度優先搜尋的遍歷序列及具體步驟和原因
1 2 3 4 表示1可達到2,達到3,達到4 2 1 3 5 3 1 2 4 5 6 4 1 3 6 5 2 3 6 6 3 4 5 廣度優先搜尋就是把每一行按照順序輸出,去掉重複的,即先看1,有1,2,3,4,然後看2,因為有3,4了,所以只要5,然後看3,以此類推。一行行來。深度優先搜尋,是先...
怎麼才能算實現自我的價值了,如何實現自我價值?
以下16點,缺一不可 1.敏銳的洞察力。2.認可自己與他人 如何實現自我價值?1.敢於冒險,敢於嘗試新鮮事物 2.能夠在逆境中堅持不懈 奮鬥不止,有極大的韌性,能承受較大的壓力 3.善於學習,悟性極高,有方法 有思路 有創意 4.對專案有極高的敏感性,善於辨識並快速抓住機會 5.有優秀的領導力,能夠...
C語言中和到底先算哪個在C語言中,,和的優先順序哪個高?
這裡出現三個運算子,所以先算 a a 2,為真,後面就不算了,前面是0時,符號後面的不計算.前面不是0時,號後面的不計算.所以x 1,a 2,b 1,c 1 逗號運算在c語言中是最後的。是同級,看哪個在前就先算哪個。不過要注意的是 都有不完全運送。對於 運送則從左到右進行判斷,如果左邊為0,則右邊不...