Первый поиск по глубине в матрице смежности
Для этой программы мне дали набор входных данных, которые мне нужно сохранить в матрице смежности. Я сделал это, поэтому у меня есть матрица смежности Матрица [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
Решение
Кажется, у вас есть псевдокод, который предполагает список смежности.
В частности, этот код: (отступ, соответствующий предполагаемым блокам кода)
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)
Насколько я могу судить, остальная часть псевдо-кода должна выглядеть одинаково.
Другие решения
Как правило, предпочтительно кодировать 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 [] отмечают время вершин. Вершины нумеруются с нуля.