圖形和使用C++中的矢量進行深度優先搜索

Question

我看到以下代碼用於製作圖形並對其進行深度優先搜索。你能否在這裏向我解釋vector g的用法。在第二個函數中，它是如何寫成二維的。請清楚解釋整個過程，使用載體來達到此目的。問題如下：---一家公司連接到n個城市，編號從1到n。目前公司總部位於hq1指數。每對連接的城市都是雙向連接的。連接是這樣的，從總部到每個城市只有一個連接。連接城市的地圖保持如下方式：對於每個城市i，與總部不同，保存最後一個城市的編號ci - 索引，從總部到i。

該公司決定將總部從hq1城市移至hq2城市。所以，在這個改變之後，如上所述的地圖的舊的表示變得不正確。請幫助公司以上述方式查找新地圖。

輸入

第一行包含的測試用例的數量（0 <Ť< = 10）。下一行包含三個以空格分隔的整數n，hq1，hq2（2≤n≤2* 10 ^4,1≤hq1≠hq2≤n） - 連接城市數，舊總部索引和新總部索引， 分別。

以下行包含n-1個以空格分隔的整數 - 地圖的舊錶示。對於除hq1以外的每個城市，在從總部到城市i的路途中給出最後城市的整數ci - 索引。所有的城市都按照指數增長的順序來描述。

輸出

輸出n - 1個數字 - 以相同的格式顯示地圖的新表示。解決方案如下。

vector <int>g[10005]; 
void make_graph() 
{ 
    int k = 1; 
    for (int i = 1; i <= n; i++) 
    { 
     if (i == h1) 
      continue; 
     int x; 
     cin >> x; 
     g[x].push_back (i); 
     g[i].push_back (x); 
    } 

} 

int visited[20004], parent[20004]; 

void dfs(int x) 
{ 
    visited[x] = 1; 
    for (int i = 0; i < g[x].size(); i++) 
    { 
     int j = g[x][i]; 
     if (j == parent[x]) 
      continue; 
     parent[j] = x; 
     dfs (j); 
    } 

    return; 
} 



int 
main() 
{ 
int t; 
cin >> t; 
while (t--) 
    { 
     cin >> n >> h1 >> h2; 
     make_graph(); 
     dfs (h2); 
     for (int i = 1; i < n; i++) 
     { 
     if (i == h2) 
     continue; 
     cout << parent[i] << " "; 
    } 
    if (n != h2) 
cout << parent[n] << endl; 
    else 
cout << endl; 
    memset (parent, 0, sizeof (parent)); 
    memset (visited, 0, sizeof (parent)); 
    for (int i = 1; i <= n; i++) 
g[i].clear(); 

    } 

    return 0; 
    } 

Answer 1

向量可以通過[]作爲正常的數組訪問。 g是整數的向量數組，因此可以作爲二維數組訪問。它包含在城市的圖中的邊信息，作爲鄰接列表

在make_graph()上的第X個頂點列表（矢量），第i個一個被推動，反之亦然，這是因爲連接是雙向的。

在dfs()函數X個列表上的每個相鄰頂點j，x被標記爲j的父，因爲從DFS根（新HQ）開始，並x與j連接。

if (j == parent[x])if (j == parent[x])阻止DFS父節點（仍然在其子節點列表中）。