7.DFS · APCS進階班

2025-01-27

文章推薦指數： 80 %

投票人數：10人

Graph 與Tree. 在學DFS與BFS前，應該先了解Graph與Tree這些概念，所以我們先來看看以下的教材。

... BFS執行起來的樣子如下，可以用來搜尋迷宮中離自己最近的出口 ... APCS進階班課程介紹 1.Sort 1-1BasicSortAlgorithms 1-1.1InsertionSort 1-1.2SelectionSort 1-1.3BubbleSort 1-1.4CountingSort 1-2AdvancedSortAlgorithms 1-2.1QuickSort 1-2.2MergeSort 1-3TimeComplexity 1-4Problems 1-5STLLibraries 2.二維陣列練習更多範例動態配置貪食蛇遊走地圖 3.DataStructure 3-1Struct 3-2Struct應用題 3-3Stack 3-4Queue 3-5STLLibraries 4.Recursion 4-1DivideandConquer 4-2費式數列、最大公因數 4-3二元搜尋法-BinarySearch 4-4Problems 5.第1次模擬考 6.Greedy 6-1練習題 6-2排工作系列 1.最多幾個工作可以執行 Solution 2.最多有幾台機器一起運作 Solution 6-3物品可以分割的背包(FractionalKnapsack)問題 Solution 6-4過橋問題 Solution 7.DFS 7-1列出所有運算式 7-1-1解答 7-2列出所有運算式(N個數版) 7-2-1解答 7-3題目3-Orio是否有機會吸引小鼠呢 7-3-1解答 7-4Problems d626:小畫家真好用 d365:RanktheLanguages 10776DetermineThecombination a160:祖靈想要下棋 c104:00167-TheSultan'sSuccessors(蘇丹的繼承者們) 老鼠走迷宮 8.Pointer 8-1.Pointer小考試 DynamicProgramming 語法列表 9.第2次模擬考 10.linked-list 10-1linkedlist進階 10-2BinarySearchTree二元搜尋樹 10-3problems 10-4linkedlist全功能程式碼 10-5LinkedListStarter 11.第三次模擬考 12.觀念題學期末總回顧練習題庫區手感練習手感練習答案 APCS考題-2017/10/18 解答補充資料 PoweredbyGitBook 7.DFS DFSvsBFS(深度優先搜尋法vs廣度優先搜尋法) Graph與Tree 在學DFS與BFS前，應該先了解Graph與Tree這些概念，所以我們先來看看以下的教材。

Graph教學文章 Tree教學文章實作Tree的練習一開始先輸入一個數字N，代表Tree的節點數量，N不超過7 接下來有N行資料，N行中的第1行代表node0的parent是誰，N行中的第2行代表node1的parent是誰，以此類推，如果是該節點是root，那parent為-1。

最後請輸出，所有葉節點，並且算出葉節點與根節點的距離輸入 4 usingnamespacestd; intmain() { //最多7個node boolleaf[7];//是葉節點的話為true intparent[7];//記錄每個節點的parent，root的話，parent填-1 intnodeCount;//這棵Tree有幾個node cin>>nodeCount; for(inti=0;i>parent[i]; if(parent[i]>=0){ leaf[parent[i]]=false; }else{ //遇到根節點的特殊處理 leaf[i]=false; } } //找出所有的葉節點(leaf)，並且輸出該葉節點與根節點(root)的距離 for(inti=0;i=0){ height++; idx=parent[idx]; } cout< #include usingnamespacestd; booledge[105][105], visited[105]; intN,M; voidDFS(intu){ //代表我現在人在u cout<v //u有一條邊走到v if(!visited[v]){ DFS(v); //走v } } } intmain(){ intx,y; //假設Ｎ個點Ｍ條邊 cout<>N; cout<>M; //初始化邊，一開始都沒有任何邊 for(inti=0;iy for(inti=0;i>x>>y; edge[x][y]=true; edge[y][x]=true; } //從0開始走 DFS(0); return0; } BFS(廣度優先搜尋法) 來試試看BFS模擬程式1號與模擬程式2號 BFS 搜尋順序:A,B,C,D,E,F,G BFS執行起來的樣子如下，可以用來搜尋迷宮中離自己最近的出口 BFS遊走範例： #include #include #include usingnamespacestd; booledge[105][105]; boolvisited[105],dist[105]; queueQ; intN,M; intmain(){ intx,y; //假設Ｎ個點Ｍ條邊 cout<>N; cout<>M; //初始化邊，一開始都沒有任何邊 for(inti=0;iy for(inti=0;i>x>>y; edge[x][y]=true;//x節點到y節點的邊相連 edge[y][x]=true;//y節點到x節點的邊相連 } //從節點0開始搜尋 dist[0]=0;//所以Node0的距離為0 visited[0]=true;//Node0被造訪了，因為他是起點 Q.push(0); while(!Q.empty()){ intu=Q.front(); Q.pop(); cout<