hnust 1966: 廣度優先搜索

題目描述
輸入一個圖，用鄰接表存儲（實際上也可以選擇鄰接矩陣），并實現BFS操作。

拷貝前面已經實現的代碼，主函數必須如下，完成剩下的部分。

int main()
{
Graph g;
CreateUDG(g);
BFS(g, 0);//從0號頂點開始遍歷
DestroyUDG(g);
return 0;
}//main

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

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

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

具體見樣例。

輸出

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

具體見樣例。

樣例輸入 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 v3 v4 v5 v6 v7 v8
提示
樣例對應教材6.5的圖G4

解題過程

注：本題按照書上算法解析完成，廣度優先搜索的細化代碼及函數分解請看合集《2024.6 hnust 23級 數據結構 課程設計》“推箱子游戲-廣度優先搜索版本”
圖的廣度優先搜索（BFS）需要借助到隊列來遍歷：
①首先，選取圖中某一頂點vi作為出發點，訪問后將其入隊并標記為已訪問（使用隊列用于避免重復訪問，存放已經訪問過的各鄰接頂點）；
②依次訪問與vi鄰接的頂點，即當隊列不為空時檢查出隊頂點的所有鄰接頂點，訪問未被訪問的鄰接頂點并將其入隊，重復該過程；【可概括為由起始頂點開始，按照廣度優先的順序逐層遍歷與當前頂點相鄰的頂點將其訪問】
③當隊列為空時跳出循環，即所有已被訪問的頂點的鄰接頂點均被訪問到，則此時遍歷完成。

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

2、BFS算法的時間復雜度
時間復雜度取決于圖的存儲結構，若通過鄰接矩陣表示圖，則查找頂點的鄰接頂點所需時間為O(|V|)，總時間復雜度為O(|V2|)（鄰接矩陣為方陣n×n），這和DFS算法的時間復雜度是一樣的；若通過鄰接表表示圖，則每個頂點都入隊一次，即所需時間為O(|V|)，搜索頂點的鄰接頂點所需時間為O(|E|)，其時間復雜度為O(|V|+|E|)。

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

1. 頭文件和命名空間：

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

2. 讀取圖的參數：

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

3. 存儲頂點信息：

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

4. 輸入頂點名稱：

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

5. 建立頂點位置映射：

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

6. 創建無向圖：

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

7. 對鄰接表進行排序：

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

8. 初始化訪問標記：

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

9. 使用隊列實現BFS：

   • 使用 queue 來實現BFS，首先將起始頂點壓入隊列，并標記為已訪問。

10. BFS搜索：

    • 當隊列不為空時，執行循環：
      • 彈出隊列前端元素作為當前訪問的頂點，并輸出。
      • 遍歷當前頂點的所有鄰接頂點。
      • 如果鄰接頂點未被訪問，將其標記為已訪問，并壓入隊列。

11. 輸出訪問順序：

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

12. 程序結束：

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

代碼邏輯分析：

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

潛在問題：

• 代碼中注釋掉的部分提供了另一種實現拓撲排序的方法，但在當前實現中未使用。

改進建議：

• 考慮使用 std::vector 替代數組，以提高代碼的安全性和靈活性。
• 考慮使用 std::unordered_map 替代 std::map，以提高查找效率。
• 如果需要處理更大的圖或更復雜的圖結構，可以考慮優化內存使用和搜索算法。
• 代碼中的排序部分可能不是必要的，因為拓撲排序的目的是線性化圖，而不是排序頂點。如果不需要對頂點進行排序，可以省略排序邏輯。

---

AC代碼

#include<bits/stdc++.h>
using namespace std;int main(int argc, char const *argv[])
{map < string , std::vector<string> >  G;int n ,e;cin>> n >> e;  //輸入：8 9string nodes[n];for (int i = 0; i < n; ++i){cin >> nodes[i];  //輸入：v1 v2 v3 v4 v5 v6 v7 v8}map <string , int > location;for (int i = 0; i < n; ++i)   //排序數組{location[nodes[i]] = i;}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]]){string temp;temp = G[nodes[i]][q];G[nodes[i]][q] = G[nodes[i]][p];G[nodes[i]][p] = temp;}}}}map < string , bool > vis;  //是否被訪問queue < string > q;q.push(nodes[0]);vis[nodes[0]] = true;// string rev[n];// int r = 0;while(q.size()){string curr;curr = q.front();  q.pop();// rev[r++] = curr;cout << curr << " ";for(auto next : G[curr]){if(!vis[next]){vis[next] = true;q.push(next);}}}return 0;
}