深度優先搜索鄰接矩陣

對於該程序，我給了一組輸入，我需要存儲在一個鄰接矩陣中。我做了這個，所以我有一個鄰接矩陣矩陣[11] [11]。現在，使用這個矩陣，我需要執行深度優先搜索並返回pi值。深度優先搜索鄰接矩陣

我有這個僞代碼，所以我相信我需要兩種方法：DFS（圖形）和DFS-VISIT（節點）。但是，我實際上遇到了麻煩。我可以直接使用鄰接矩陣來做到這一點，還是我需要用矩陣創建一個圖形？任何幫助實際編碼這將不勝感激。

DFS(G) 
    for each u ∈ V[G] do 
     color[u] = WHITE 
     ∏[u] = NIL 
    time = 0 
    for each u ∈ V[G] do 
     if color[u] = WHITE then 
     DFS-VISIT(u) 

DFS-VISIT(u) 
    color[u] = GRAY 
    time++ 
    d[u] = time 
    for each v ∈ Adj[u] do 
     if color[v] = WHITE then 
     ∏[v] = u 
     DFS-VISIT(v) 
    color[u] = BLACK 
    time++ 
    f[u] = time

來源

2014-04-17 user3543418

可以單獨使用鄰接矩陣來完成。 'pi'值是什麼意思？請顯示您的部分代碼。 – Codor

你的圖是矩陣。請發佈您的DFS（g）功能的簡化版本。 – vz0

這個矩陣表示你的圖形，所以你不需要生成另一個數據結構。 – Ilya

您在那裏的僞代碼似乎假定有鄰接列表。

具體驗證碼（對應於假定的碼塊縮進）

for each v ∈ Adj[u] do 
    if color[v] = white then 
    ∏[v] = u 
    DFS-VISIT(v)

所不同的是：使用鄰接矩陣，所有頂點都在那裏，和一個通常使用0/1標誌以指示是否有當前頂點和目標頂點之間的邊。

所以，你應該通過循環在鄰接矩陣該行所有的頂點，只有當標誌被設置爲1

僞碼的那部分看起來像做一些事情：

for v = 1 to n do // assuming 1-indexed 
    if color[v] = white && AdjMatrix[u][v] == 1 then 
    ∏[v] = u 
    DFS-VISIT(v)

據我所知，僞代碼的其餘部分應該看起來完全相同。

來源

2014-04-17 10:25:01 Dukeling

一般來說，假設圖形被表示爲鄰接列表，最好編碼DFS，因爲結果的時間複雜度爲O(|V| + |E|)。但是通過鄰接矩陣，時間複雜度變爲O(|V|*|V|)。下面是DFS假定鄰接矩陣表示的實施方案：

#define WHITE 0 
#define GRAY 1 
#define BLACK 2 
int time_; 
vector<int> color(n, WHITE), par(n, 0), strt(n, 0), fin(n, 0); 
vector<vector<int> > G(n, vector<int>(n, 0)); 
void dfs_visit(int); 
void DFS(){ 
    for(int i = 0; i < n; i++) 
     color[i] = 0, par[i] = -1; 
    time = 0; 
    for(int j = 0; j < n; i++) 
     if(color[j] == WHITE) 
      dfs_visit(j); 
    } 
} 
void dfs_visit(int u){ 
    time_++; 
    strt[u] = time_; 
    color[u] = GRAY; 
    for(int v = 0; v < n && v++) 
     if(G[u][v] && color[v] == WHITE){ 
      par[v] = u; 
      dfs_visit(v); 
     } 
    color[u] = BLACK; 
    time_++; 
    fin[u] = time_; 
}

票面[]矩陣計算每個頂點和STRT []的親本和翅片[]矩陣時間戳的頂點。頂點是基於0的編號。

來源

2017-01-08 08:06:24

深度優先搜索鄰接矩陣

回答

相關問題