Поиск в глубину по матрице смежности

Для этой программы мне дан набор входных данных, которые мне нужно сохранить в матрице смежности. Я сделал это, поэтому у меня есть матрица смежности Matrix[11][11]. Теперь, используя эту матрицу, мне нужно выполнить поиск в глубину и вернуть значения числа пи.

У меня есть псевдокод для этого, поэтому я считаю, что мне нужны два метода: 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

c++ algorithm adjacency-matrix depth-first-search
person user3543418    schedule 17.04.2014    source источник
comment
Это можно сделать только с помощью матрицы смежности. Что вы подразумеваете под значениями «пи»? Пожалуйста, покажите часть вашего кода.   -  person Codor    schedule 17.04.2014
comment
Ваш график - это матрица. Опубликуйте упрощенную версию вашей функции DFS(g).   -  person vz0    schedule 17.04.2014
comment
Эта матрица является представлением вашего графика, поэтому вам не нужно создавать еще одну структуру данных.   -  person Ilya    schedule 17.04.2014
comment
Однако может потребоваться дополнительное хранилище, чтобы пометить узлы как «посещенные» или нет; однако это зависит от типа графика и фактического применения алгоритма.   -  person Codor    schedule 17.04.2014
comment
Узлы будут переведены по индексам строк (например), а цикл для каждого соседа узла i будет переведен по циклу для каждого индекса j, такого что mat[i][j] положителен   -  person user189    schedule 17.04.2014
comment
Я добавил псевдокод, который у меня есть для двух функций.   -  person user3543418    schedule 17.04.2014
comment
Псевдокод запрашивает окраску узлов, чтобы увидеть, посещались ли они ранее; это может быть достигнуто с помощью массива bool длины n, где n — количество вершин. Кроме того, существует массив ∏, в котором хранятся родительские элементы в дереве DFS (узел, из которого посещается узел), и массив f для отслеживания последовательности посещения узлов.   -  person Codor    schedule 17.04.2014

Ответы (2)


arrow_upward
0
arrow_downward

Псевдокод, который у вас есть, похоже, предполагает список смежности.

В частности, этот код: (предполагается отступ, соответствующий блокам кода)

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)

Насколько я могу судить, остальная часть псевдокода должна выглядеть идентично.

person Bernhard Barker    schedule 17.04.2014

arrow_upward
0
arrow_downward

Обычно предпочтительнее кодировать 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.

person Gaurav Jain    schedule 08.01.2017