深度优先搜索邻接矩阵-Java 学习之路

对于这个程序，我需要一组输入，我需要存储在一个邻接矩阵中 . 我已经这样做了，所以我有一个邻接矩阵矩阵[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

2 回答

0
你在那里的伪代码似乎假设一个邻接列表 .

特别是这段代码:(对应于假定的代码块的缩进）
```
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)
```
据我所知，伪代码的其余部分应该看起来相同 .
回复于 2024-05-02T11:55:15+08:00

通常，首选代码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_;
}

par []矩阵计算每个顶点的父节点，strt []和fin []矩阵为顶点添加时间戳 . 顶点从0开始编号 .

回复于 2024-05-02T11:55:15+08:00

深度优先搜索邻接矩阵

2 回答

相关问题