//深度優(yōu)先找出從頂點u到頂點v的簡單路徑,pre用來存儲路徑
void one_path(adjMatrix *G, int u, int v, int *pre){
int i;
pre = (int *)malloc(G->vexnum * sizeof(int));
for (i = 0; i < G->vexnum; i++) {
pre[i] = -1;
}
pre[u] = u;//不是-1表示被訪問過了
cout<<DFS_path(G, u, v, pre)<<endl;
free(pre);
}
int DFS_path(adjMatrix *G, int u, int v, int *pre){
int j;
for (j = firstadj(G, u); j > 0; j = nextadj(G, u, j)) {
cout<<"j="<<j<<endl;
if (pre[j] == -1 || j==v) {
pre[j] = u;//出發(fā)索引存在到達的點上
if (j == v) {
cout<<"find path is:"<<endl;
return 1;
}else if(DFS_path(G, j, v, pre)){//遞歸調(diào)用碉熄，如果 臨接點->目的地 存在路徑則返回桨武，不再去尋找別的路徑
return 1;
}/*{
DFS_path(G, j, v, pre);//in this case it will always return 0 except there is only one step from start to end. last called will return 1,first called will return 0;
}*/
}
}
return 0;
}
//找到u的第一個鄰接點位置
int firstadj(adjMatrix *G, int u){
for (int i = 0; i < G->vexnum; i++) {
if (G->arcs[u][i].adj < INFINITY) {
return i;
}
}
return 0;
}
//找到當(dāng)前鄰接點的下一個鄰接點
int nextadj(adjMatrix *G, int u, int now){
now++;
for (int i = now; i < G->vexnum; i++) {
if (G->arcs[u][now].adj < INFINITY) {
return i;
}
}
return 0;
}
圖之深度優(yōu)先找到簡單路徑
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來煌往，“玉大人倾哺，你說我怎么就攤上這事」舨保” “怎么了羞海？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長曲管。 經(jīng)常有香客問我却邓，道長，這世上最難降的妖魔是什么院水？ 我笑而不...
- 正文 為了忘掉前任申尤，我火速辦了婚禮癌幕，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘昧穿。我一直安慰自己勺远，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布时鸵。 她就那樣靜靜地躺著胶逢，像睡著了一般。 火紅的嫁衣襯著肌膚如雪饰潜。 梳的紋絲不亂的頭發(fā)上初坠，一...
- 文/蒼蘭香墨 我猛地睜開眼吴菠，長吁一口氣：“原來是場噩夢啊……” “哼者填！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起做葵，我...
- 正文 年R本政府宣布，位于F島的核電站酝枢，受9級特大地震影響恬偷，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜帘睦，卻給世界環(huán)境...
- 文/蒙蒙 一袍患、第九天 我趴在偏房一處隱蔽的房頂上張望坦康。 院中可真熱鬧，春花似錦诡延、人聲如沸滞欠。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽筛璧。三九已至，卻和暖如春惹恃，著一層夾襖步出監(jiān)牢的瞬間夭谤，已是汗流浹背。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 兩種遍歷 圖的遍歷分為深度優(yōu)先搜索(Depth First Search)和廣度優(yōu)先搜索 深度優(yōu)先搜索(DFS) ...
- 說真的，擁有夢想的人太多了姨伤，可在命運閉上眼睛時候哨坪，仍舊苦苦堅守的能有幾個？很多時候乍楚，我們淪落為平庸的人当编，呼應(yīng)了北島...
- 夢境徒溪，是內(nèi)心追求的寄托忿偷，也是現(xiàn)實生活的折射金顿。 浪漫的情懷自古就有，殘缺與遺憾卻是人生常態(tài)鲤桥。疲憊的求與不得之后揍拆，自嘲...
