Реализация первого обхода глубины для графика с использованием переполнения стека матрицы смежности
У меня есть набор узлов и несколько ребер, которые представляют, какие узлы связаны.
V_nodes 1 7 22 97 48 11
V_arcs (1 22) (97 22) (7 1) (11 48) (48 7) (11 0)
V_weight 1
Я создал матрицу смежности, которая показывает 1 для связанных и 0 для отключенных вершин.
Теперь я хочу реализовать обход глубины для этого графика, используя его матрицу смежности.
Я видел учебные пособия по DFS, но я запутался. Как я могу пройти по нему, используя свою матрицу смежности.
Мне просто нужно распечатать узлы с использованием глубины первого обхода.
Любая помощь будет оценена.
// Prints the adjacency matrix
cout<<"Adjacency Matrix : \n";
for(int i=0;i<6;i++)
cout<<" "<<nodes[i].nodevalue;
cout<<endl<<endl;
for(int i=0;i<6;i++)
{
for (int j=0;j<6;j++)
{
cout<<" "<<edges[i][j];
}
cout<<endl<<nodes[i].nodevalue;
cout<<endl<<endl;
}
Решение
Вы захотите использовать очередь «первым пришел — первым вышел», иначе известную как стек. Вы также можете использовать рекурсию, но вы рискуете переполнить стек, если ваш график слишком большой.
Для каждого узла выполните цикл по всем узлам, к которым подключен этот узел, и добавьте их в стек.
Извлеките первый узел из стека, выполните любую операцию, которую хотите выполнить, а затем повторите процесс.
Это может выглядеть как
void dfs(int node){
std::stack<int> expand;
expand.push(node);
while(!expand.empty()){
int tnode=expand.top();expand.pop();
do_operation_on(tnode);
for(int i=0;i<ADJACENCY_MATRIX_DIMENSION;i++)
if(adj_matrix[tnode][i])
expand.push(i);
}
}
Обратите внимание, что если у вас есть цикл в вашем графике, будут проблемы.
Другие решения
#include<cstdio>
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
int G[10][10],n;
void dfs(int strt)
{
int vis[n];
memset(vis,0,sizeof vis);
stack<int>st;
st.push(strt);
while(!st.empty())
{
int pre=st.top();st.pop();
if(!vis[pre])
{
cout<<pre<<" ";
vis[pre]=1;
for(int i=n-1;i>=0;i--)
{
if(G[pre][i]==1 and !vis[i])
{
st.push(i);
}
}
}
}
cout<<endl;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>G[i][j];
dfs(2);
}
Здесь я добавляю узлы, которые подключены к узлу в обратном порядке, его работа. https://ideone.com/AGm2xe