hnust 1965: 深度優先搜索

題目描述
輸入一個圖，用鄰接矩陣存儲（實際上也可以選擇鄰接表），并實現DFSTraverse操作。
拷貝前面已經實現的代碼，主函數必須如下，完成剩下的部分。

int main()
{
Graph g;
CreateUDG(g);
DFSTraverse(g);
cout << endl;
DestroyUDG(g);
return 0;
}//main

輸入
輸入的第一行是兩個整數，分別是圖的總頂點數n和總邊數e

第二行是n個空格分開的字符串，是頂點的名字，依次對應編號0~n-1。

隨后有e行，每行兩個空格分開的頂點名字，表示一條邊的兩個頂點。

具體見樣例。

輸出
輸出圖的DFS序列，遍歷次序按教材，每個頂點后面跟一個空格。

具體見樣例。

樣例輸入 Copy
8 9
v1 v2 v3 v4 v5 v6 v7 v8
v1 v2
v1 v3
v2 v4
v2 v5
v3 v6
v3 v7
v4 v8
v5 v8
v6 v7
樣例輸出 Copy
v1 v2 v4 v8 v5 v3 v6 v7
提示
樣例對應教材6.5的圖G4

解題過程

注：本題按照書上算法解析完成，深度優先搜索的細化代碼及函數分解請看合集《2024.6 hnust 23級 數據結構 課程設計》“推箱子游戲-深度優先搜索版本”
圖的深度優先遍歷（DFS）需要借助棧來遍歷：
①首先，選取圖中某一頂點vi作為起始點訪問；
②任意選取一個與vi鄰接的頂點，且該頂點未被訪問，一直重復下去，直到圖中所有與vi連通的頂點都被訪問到；【可概括為由起始頂點開始，沿著一條路徑盡可能地深入搜索該圖，直到無法再繼續下去】
③若還有頂點未被訪問到，則另外選取一個未被訪問的頂點再次作為起始點，回溯到上一個未訪問的頂點，重復以上步驟，直至圖中所有結點被訪問。

DFS的空間復雜度和時間復雜度
對于一個圖G=（V，E），由頂點集V和邊集E組成。
1、DFS算法的空間復雜度
由于DFS算法是一個遞歸算法，即遞歸頂點集V，通過DFS遍歷的空間復雜度為O(|V|)。

2、DFS算法的時間復雜度
時間復雜度取決于圖的存儲結構，若通過鄰接矩陣表示圖，則查找頂點的鄰接頂點所需時間為O(|V|)，總時間復雜度為O(|V2|)（鄰接矩陣為方陣n×n）；若通過鄰接表表示圖，則查找所有頂點的鄰接頂點所需時間為O(|E|)，訪問頂點所需時間為O(|V|)，即總時間復雜度為O(|V|+|E|)。

這段C++代碼實現了一個基于深度優先搜索（DFS）的無向圖的拓撲排序算法。以下是對代碼的詳細解析：

1. 頭文件和命名空間：

   • 包含 <bits/stdc++.h> 頭文件，它包含了標準庫中的大部分內容。
   • 使用 using namespace std; 來避免在標準庫類型和函數前加 std::。

2. 輸入圖的參數：

   • 讀取兩個整數 n 和 e，分別代表圖中頂點的數量和邊的數量。

3. 存儲頂點信息：

   • 創建一個字符串數組 nodes 來存儲頂點的名稱。

4. 輸入頂點名稱：

   • 使用循環讀取 n 個頂點的名稱。

5. 建立頂點位置映射：

   • 使用 map（映射）來存儲每個頂點名稱與其在數組中的索引位置。

6. 創建無向圖：

   • 使用 map 來創建一個鄰接表 G，表示無向圖中的邊。

7. 對鄰接表進行排序：

   • 對每個頂點的鄰接表進行排序，以便在后續的搜索中按順序訪問。

8. 初始化訪問標記：

   • 使用 map 初始化所有頂點的訪問狀態為未訪問。

9. 使用棧實現DFS：

   • 使用 stack 來實現DFS，首先將起始頂點壓入棧中，并標記為已訪問。

10. DFS搜索：

    • 當棧不為空時，執行循環：
      • 彈出棧頂元素作為當前訪問的頂點。
      • 遍歷當前頂點的所有鄰接頂點。
      • 如果鄰接頂點未被訪問，將其標記為已訪問，并壓入棧中。
      • 如果成功訪問了一個鄰接頂點，輸出當前頂點名稱，并設置 flag 為 1。
      • 如果沒有鄰接頂點可訪問（flag 為 0），則繼續彈出棧中的元素。

11. 輸出訪問順序：

    • 在訪問過程中，每訪問一個頂點，就輸出其名稱。

12. 程序結束：

    • 當棧為空時，表示所有頂點都被訪問完畢，程序結束。

代碼邏輯分析：

• 這段代碼通過DFS實現了拓撲排序，適用于無向圖。
• 使用棧來存儲待訪問的頂點，使用映射來記錄頂點的訪問狀態和位置信息。

潛在問題：

• 代碼中注釋掉的部分提供了另一種交換變量值的方法，但在當前實現中未使用。
• 代碼中使用 9999 作為鄰接矩陣的初始值，這可能在某些情況下不是最佳選擇，比如圖中邊的權重可能超過這個值。

改進建議：

• 考慮使用 std::vector 替代數組，以提高代碼的安全性和靈活性。
• 考慮使用 std::unordered_map 替代 std::map，以提高查找效率。
• 考慮使用 std::swap 函數交換變量值，使代碼更加簡潔。
• 如果需要處理更大的圖或更復雜的圖結構，可以考慮優化內存使用和搜索算法。

---

AC代碼

#include<bits/stdc++.h>
using namespace std;int main(int argc, char const *argv[])
{int n , e;cin >> n >> e;  // 輸入 ： 8 9string nodes[n];for (int i = 0; i < n; ++i)  // 輸入： v1 v2 v3 v4 v5 v6 v7 v8{cin >> nodes[i];}map <string , int > location;for (int i = 0; i < n; ++i)   //排序數組{location[nodes[i]] = i;}map<string ,std::vector<string> > G;  //創建無向圖for (int i = 0; i < e; ++i){string l , r;cin >> l >> r;G[l].push_back(r);G[r].push_back(l);}for (int i = 0; i < n; ++i)  //對無向圖的排序{int j = G[nodes[i]].size();for (int p = 0; p < j; ++p){for (int q = 0; q < j; ++q){if(location[G[nodes[i]][q]] > location[G[nodes[i]][p]]){swap(G[nodes[i]][q],G[nodes[i]][p]);}}}}map<string,bool > vis; //是否被訪問stack <string > s;s.push(nodes[0]);vis[nodes[0]] = true;cout << nodes[0] << " " ;while(s.size()){string curr;curr = s.top();bool flag = 0;for(auto next : G[curr]){if(!vis[next]){vis[next] = true;s.push(next);flag = 1;cout << next << " ";break;}}if(flag == 0){s.pop();}}return 0;
}