Внедряване на първо обхождане на дълбочина за графика с помощта на матрица на съседство 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 за несвързани върхове. Сега искам да внедря Depth First Traversal за тази графика, използвайки нейната матрица на съседство. Видях уроците за DFS, но съм объркан как мога да го обходя с помощта на моята матрица на съседство. Просто трябва да отпечатам възлите с помощта на Depth First Traversal. Всяка помощ ще бъде оценена.

// 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; expand.push(възел); докато (!expand.empty()){ int tnode=expand.top(); expand.pop(); 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. Има ли наличен онлайн инструмент, който позволява вмъкване на възли и ги свързва и след това показва bfs на графиката на потребителя. Като java аплет или така? - person Faizan; 30.12.2012
comment
За пояснение - FIFO е за опашка, а LIFO е за стек - Стек, абстрактен тип данни и структура на данните, базирани на принципа Последен влязъл, първи излязъл (LIFO)(en.wikipedia.org/wiki/Stack_(abstract_data_type)) - 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
Всъщност трябва да внедря и двете преминавания. Мислех, че Depth First ще бъде лесен за прилагане, затова попитах за DFS във въпроса. Въпреки че сте предоставили кода за DFS, но той не се отпечатва по DFS начин. Моля, помогнете ми с това нещо, правя го цял ден. Какви промени трябва да направя? Имам 2D масив {матрица на съседство], просто искам да отпечатам възлите в обхождането на 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
Питам за Depth First Traversal! Съжалявам, че написах BFS в горния коментар. - person Faizan; 30.12.2012
comment
@Faizan, може би вашите възли имат някакво име? В такъв случай бихте искали да замените cout<<tnode<<" " с cout<<name(tnode)<<" ". - person Richard; 30.12.2012
comment
Благодаря, поне възлите вече се печатат. Но каквото и да правя, отпечатва само 3 възела, а не всички. Моите възли се съхраняват в nodearray[6] и предавам tnode като индекс за nodearray. Направих следните промени и се отпечатва 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