数据结构基础图的遍历（三）之 BFS+DFS（非递归实现）

桃扇骨 2022-08-02 07:17 144阅读 0赞

【图例】

> > ![Center][]

【屌丝代码】

#include<iostream>  
    #include<vector>  
    #include<queue>  
    #include<list>  
    #include<stack>  
    #include<string>  
      
    using namespace std;  
      
    class Graph  
    {  
    private:  
     int V; //顶点数  
     int *indegree; // 入度数链表  
     queue< int > q; // 入度为 0 队列  
     list< int > *adj; // 出度表  
    public:  
     Graph(int V);  
          ~Graph();  
     void AddEdge(int v,int w);  
     bool TopoSort();  
     void BFS();  
     void DFS();  
    };  
      
    Graph::Graph(int V=10)  
    {  
     this->V = V;  
     adj = new list<int>[V];  
     indegree = new int[V];  
     for (int i=0;i<V;i++)  
          {  
              indegree[i] = 0;  
          }  
    }  
    Graph::~Graph()  
    {  
     delete []indegree;  
     delete []adj;  
    }  
    void Graph::AddEdge(int v,int w)  
    {  
     indegree[w]++;
     adj[v].push_back(w);
    }  
    bool Graph::TopoSort()  
    {  
     int data,count(0);  
     for(int i = 0;i<V;i++)  
              if(indegree[i] == 0)  
                  q.push(i);  
     while(!q.empty())  
          {  
              data = q.front();  
              q.pop();  
              count++;  
              cout<<data<<"\t";  
              list<int>::iterator it = adj[data].begin();  
              for(;it!=adj[data].end();it++)  
              {  
                  indegree[*it]--;  
                  if(indegree[*it] == 0)  
                      q.push(*it);  
              }  
          }  
     cout<<endl;  
     if(count<V)  
              return false;  
     else  
              return true;  
    }  
    void Graph::BFS()  
    {  
     cout<<"广度优先遍历!!! "<<endl;  
     int *visited = new int[V];  
     int i;  
     for(i=0;i<V;i++)  
          {  
              visited[i] = 0;  
          }  
     for(i=0;i<V;i++)  
              if(visited[i] == 0)  
              {  
                  visited[i] = 1;          
                  queue<int> q;  
                  q.push(i);  
                  while(!q.empty())  
                  {  
                      int tmp = q.front();  
                      q.pop();  
                      cout<<tmp<<"\t";  
                      list<int>::iterator it = adj[tmp].begin();  
                      for(;it!=adj[tmp].end();it++)  
                      {  
                          if(visited[*it] == 0)  
                          {  
                              q.push(*it);  
                              visited[*it] = 1;  
                          }  
                      }  
                  }  
             }  
    }  
    void Graph::DFS()  
    {  
     cout<<endl;  
     cout<<"深度优先遍历!!! "<<endl;  
     int *visited = new int[V];  
     int i,tmpv,flag;  
     list<int> *tmpadj = adj;  
     stack<int> s;  
     for(i=0;i<V;i++)  
          {  
              visited[i] = 0;  
          }  
     for(i=0;i<V;i++)  
          { 
              if(visited[i] == 0)  
              {  
                  visited[i] = 1;  
                  s.push(i);  
                  cout<<i<<"\t";  
                  while(!s.empty())  
                  {               
                      if(tmpadj[s.top()].size()>0)  
                      {               
                          // cout<<tmpadj[s.top()].size()<<endl;  
                          list<int>::iterator it = tmpadj[s.top()].begin();  
                          flag = 0;  
                          for(;it!=tmpadj[s.top()].end();it++)  
                          {  
                              if(visited[*it] == 0)  
                              {  
                                  flag = 1;  
                                  break;               
                              }
                          }  
                          if(flag == 1)  
                          {  
                              // cout<<*it<<endl;  
                              tmpv = *it;  
                              tmpadj[s.top()].erase(it);
                              // cout<<*it<<endl;  
                              s.push(tmpv);
                              cout<<s.top()<<"\t";  
                              visited[s.top()] = 1;  
                              // cout<<s.top()<<endl;  
                              // cout<<s.top()<<endl;  
                          }  
                          else  
                          {  
                              s.pop();  
                          }  
                      }  
                      else  
                      {  
                          // cout<<s.top()<<endl;  
                          s.pop();  
                      }  
                  }  
              }  
          }  
    }  
    int main()  
    {  
     Graph myg(9);  
     myg.AddEdge(0,1);  
     myg.AddEdge(0,3);  
     myg.AddEdge(0,4);  
     myg.AddEdge(1,2);  
     myg.AddEdge(1,5);  
     myg.AddEdge(2,5);  
     myg.AddEdge(0,6);  
     myg.AddEdge(0,7);  
     myg.AddEdge(1,8);  
        
     cout<<"TOPOSORT LIST"<<endl;  
     myg.TopoSort();  
    //   cout<<myg.TopoSort()<<endl;  
     myg.BFS();  
     myg.DFS();  
     return 0;  
    }

【运行结果】

> TOPOSORT LIST
> 
> 0 1 3 4 6 7 2 8 5 
> 
> 广度优先遍历!!! 
> 
> 0 1 3 4 6 7 2 5 8 
> 
> 深度优先遍历!!! 
> 
> 0 1 2 5 8 3 4 6 7

【备注与小结】

> 1.VS2010不承认无返回值函数，【AddEdge(int v,int w);】函数在VC6.0中编译可以通过，但是，在VS2010中，【void AddEdge(int v,int w);】才能编译通过；
> 
> 2.广度优先遍历一个自定义函数就能直接解决，但是，采用迭代递归实现深度优先遍历要比直接使用while循环要简单得多，诚然如此，但本文屌丝代码给出的是自己为了仿真递归机制实现的；
> 
> 3.广度优先直接使用队列实现即可，采用单函数实现深度优先是栈实现；
> 
> 4.**深度优先搜索双弹栈机制，是在仿迭代上十分重要的思想，也是使用非递归实现深度搜索的重中之重。**

[Center]: /images/20220731/a2c3d91a6d6740828b47d76520391e80.png