Реализация обхода в глубину для графа с использованием матрицы смежности C++

У меня есть набор узлов и несколько ребер, которые представляют, какие узлы связаны. 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;
}

c++ graph traversal adjacency-matrix depth-first-search
person Faizan    schedule 30.12.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете использовать очередь «последний вошел – первый вышел», также известную как стек. Вы также можете использовать рекурсию, но вы рискуете получить переполнение стека, если ваш график слишком велик.

Для каждого узла выполните цикл по всем узлам, к которым подключен этот узел, добавляя их в стек.

Извлеките первый узел из стека, выполните любую операцию, которую хотите выполнить, а затем повторите процесс.

Это может выглядеть как

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);
  }
}

Обратите внимание, что если у вас есть цикл на вашем графике, будут проблемы.

person Richard    schedule 30.12.2012
comment
Я попробовал именно ваш код, но он не печатает обход в глубину. В моем main () я вызвал его с любым случайным начальным узлом, внутри dfs я пытаюсь напечатать tnode. Что я делаю неправильно ? Что вы подразумеваете под циклом на графике? Я не думаю, что на моем графике есть цикл. так, чтобы он начинался и заканчивался на одном и том же узле. это цикл? - person Faizan; 30.12.2012
comment
Вы не могли попробовать именно мой код, потому что функция do_operation_on не была определена. Боюсь, я не понимаю, что вы имеете в виду под этим не печатает e. Пожалуйста, объясни. - person Richard; 30.12.2012
comment
~void dfs(int node) { std::stack‹int›expand; расширить .push (узел); while(!expand.empty()){ int tnode=expand.top(); расширить.поп(); cout‹‹tnode‹‹ ; // do_operation_on(tnode); for(int i=0;i‹6;i++) if(edges[tnode][i]) expand.push(i); }~ - person Faizan; 30.12.2012
comment
Извините, я здесь новичок, я не знаю, как добавить встроенный код в комментарии. В любом случае программа печатает узлы, но случайным образом, а не так, как ожидалось. Есть ли какой-либо онлайн-инструмент, который позволяет вставлять узлы и соединять их, а затем отображает BFS пользовательского графика. Как Java-апплет или около того? - person Faizan; 30.12.2012
comment
Для пояснения: FIFO для очереди, а LIFO для стека. Стек, абстрактный тип данных и структура данных, основанные на принципе «последним пришел — первым вышел» (LIFO)(en.wikipedia.org/wiki/Stack_(абстрактный_тип_данных)) - person SChepurin; 30.12.2012
comment
@Faizan, узлы отображаются неслучайно. Ваш вопрос касался поиска в глубину. Если вам нужен поиск в ширину, замените стек поиском в порядке поступления поставить в очередь. - person Richard; 30.12.2012
comment
Спасибо, @SChepurin, я только что заметил, что сам все испортил. - person Richard; 30.12.2012
comment
Кроме того, @Faizan, в зависимости от того, как настроена ваша матрица, вам может потребоваться заменить adj_matrix[tnode][i] на adj_matrix[i][tnode]. - person Richard; 30.12.2012
comment
На самом деле я должен реализовать оба обхода. Я думал, что Deep First будет легко реализовать, поэтому я спросил о DFS в вопросе. Даже если вы предоставили код для DFS, но он не печатается в формате DFS. Пожалуйста, помогите мне с этим делом, я делал это весь день. Какие изменения мне нужно сделать? У меня есть двумерный массив {матрица смежности], я просто хочу распечатать узлы в обходе BFS. Это оно ! - person Faizan; 30.12.2012
comment
Могу ли я передать любой начальный узел при вызове этой функции, например: dfs(1); В основном мои узлы хранятся в массиве 1D. Я передаю 1 в качестве тестового узла, чтобы проверить, правильно ли он проходит. Такой вызов функции дает результат: 1 4 5. тогда как мои узлы 1 7 22 97 48 11 , как указано в вопросе. - person Faizan; 30.12.2012
comment
Я спрашиваю о глубине первого обхода! Извините, я написал BFS в комментарии выше. - person Faizan; 30.12.2012
comment
@Faizan, возможно, у ваших узлов есть какое-то имя? В этом случае вы захотите заменить cout<<tnode<<" " на cout<<name(tnode)<<" ". - person Richard; 30.12.2012
comment
Спасибо, по крайней мере, узлы теперь печатаются. Но что бы я ни делал, это распечатывает только 3 узла, а не все из них. Мои узлы хранятся в nodearray[6], и я передаю tnode в качестве индекса для массива узлов. Я внес следующие изменения, и он печатает 7 1 22. cout<<nodearray[tnode]<<" "; if(edges[tnode][i]) Также конечное значение цикла for равно 6. - person Faizan; 30.12.2012
comment
@Faizan, если ваш граф смежности действительно (1 22) (97 22) (7 1) (11 48) (48 7) (11 0), то алгоритм работает правильно. С 22 никуда не денешься, поэтому он обрывается. Кажется, что вы не можете распечатать каждый узел, начиная с одного заданного узла. Вы хотите напечатать каждый узел? Если это так, вы должны запустить алгоритм, поместив несколько узлов в стек/очередь в начале и отслеживая, какие узлы вы посетили. Имеет ли это смысл? Обычно DFS/BFS не используется для печати всего графика. - person Richard; 30.12.2012

arrow_upward
0
arrow_downward 

    #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

person Community    schedule 22.06.2015