图的邻接矩阵以及深度优先遍历 + 广度优先遍历

左手的ㄟ右手 2022-06-01 08:40 333阅读 0赞

图的邻接矩阵表示法非常简单，一个定点数组，一个二维数组搞定，类似与这样  
![这里写图片描述][SouthEast]  
下面简单实现一个邻接矩阵表示的方法的图，以及遍历的两种方式。

#### Graph.h ####

#pragma once
    
    #define MAX_SIZE 30
    template<class T,class E>
    class Graph
    {
    public:
        Graph(size_t size);
        virtual ~Graph();
        bool isEmpty()const {
            return verticleSize == 0;
        }
        int numberofVerticles(){
            return verticleSize ;
        }
    
    
    
    protected:
        int maxVerticles=MAX_SIZE;
        int verticleSize;
    
        virtual T getValue(int i) = 0;                //获取值
        virtual E getWeight(int v1, int v2) = 0;      //根据两个定点获取边的权值
        virtual int getFirstNeighbor(int v) = 0;      //取顶点v的第一个邻接顶点  
        virtual int getNextNeighbor(int v, int w) = 0; //取邻接顶点w的下一个邻接顶点  
        virtual int getVertexPos(T vertex) = 0;      //由定点获取下标
        virtual T* getVerticles() = 0;              //获取定点数量
    
    };
    
    template<class T, class E>
     Graph<T, E>::Graph(size_t size):verticleSize(size)
    {
    
    }
    
     template<class T, class E>
     inline Graph<T, E>::~Graph()
     {
     }

父类只是定义了一些基本方法，不再赘述。

### 遍历方式 ###

![这里写图片描述][SouthEast 1]  
我们按照深度遍历的顺序，假设从v1开始，那么数序是v1->v0->v4->v2->v3  
![这里写图片描述][SouthEast 2]  
同样从v1开始，顺序是v1->v0->v2->v4->v3

#### GraphMatrix.h ####

#pragma once
    #include "Graph.h"
    #include <iostream>
    #include <stack>
    #include <queue>
    
    #define INF 0xffffff
    
    using namespace std;
    
    template<class T, class E>
    class GraphMatrix :public Graph<T, E>
    {
    public:
        GraphMatrix(size_t size);
        ~GraphMatrix();
        static const int MAX_WEIGHT = INF;
    
        T getValue(int i) override;
        E getWeight(int v1, int v2)override;
        int getFirstNeighbor(int v) override;      //取顶点v的第一个邻接顶点  
        int getNextNeighbor(int v, int w)override; //取邻接顶点w的下一个邻接顶点  
        int getVertexPos(T vertex)override;
        T* getVerticles() override;
        E** getMatrix();
        void outputGraph();
        void bfsIndex(int i);           //广度优先搜索
        void bfs(int i);
        void dfsStack(int i);//深度优先搜索使用堆栈
        void dfsIndex(int i);
        void dfs(int i); //深度优先搜索使用递归
        int getUnVisitedVerticles(int i);
        int findNextUnVisitedVert(int i);
    
    
    
    private:
        T* verticles;
        E** matrix;
        bool* visit;
    };
    
    
    
    template<class T, class E>
    GraphMatrix<T, E>::GraphMatrix(size_t size) :Graph<T, E>(size)
    {
        verticles = new T[size];
        matrix = new E*[size];
    
        for (int i = 0; i < this->verticleSize; i++) {
            matrix[i] = new E[size];
        }
    
        visit = new bool[size];
        for (int i = 0; i < size; i++) {
            visit[i] = false;
        }
    }
    
    template<class T, class E>
    GraphMatrix<T, E>::~GraphMatrix()
    {
        delete[] matrix;
        delete[] verticles;
    }
    
    template<class T, class E>
    T GraphMatrix<T, E>::getValue(int i)
    {
        if (i >= 0 && i < this->verticleSize)
            return verticles[i];
        else
            return NULL;
    }
    
    template<class T, class E>
    E GraphMatrix<T, E>::getWeight(int v1, int v2)
    {
        if (v1 >= 0 && v2 >= 0) {
            return matrix[v1][v2];
        }
        return -1;
    }
    
    template<class T, class E>
    int GraphMatrix<T, E>::getFirstNeighbor(int v)
    {
        for (int i = 0; i < this->verticleSize; i++) {
            if ((matrix[v][i]) != 0 && matrix[v][i] != MAX_WEIGHT) {
                return i;
            }
        }
        return MAX_WEIGHT;
    }
    
      template<class T, class E>
       int GraphMatrix<T, E>::getNextNeighbor(int v, int w)
      {
           for (int i = w+1; i < this->verticleSize; i++) {
               if ((matrix[v][i]) != 0 && matrix[v][i] != MAX_WEIGHT) {
                   return i;
               }
           }
           return MAX_WEIGHT;
    
      }
    
      template<class T, class E>
       int GraphMatrix<T, E>::getVertexPos(T vertex)
      {
           for (int i = 0; i < Graph<T,E>::verticleSize; i++) {
               if (verticles[i] == vertex) {
                   return i;
               }
           }
          return -1;
      }
    
      template<class T, class E>
       T * GraphMatrix<T, E>::getVerticles()
      {
          return verticles;
      }
    
       template<class T, class E>
       E ** GraphMatrix<T, E>::getMatrix()
       {
    
           return matrix;
       }
    
       template<class T, class E>
        void GraphMatrix<T, E>::outputGraph()
        {
                //输出图的所有顶点和边信息  
                int i, j, n, m;
                T e1, e2;
                E weight;
                n = this->numberofVerticles();     //点数  
                cout << "顶点数的边数为：";
                cout << n   << endl;      //输出点数
                cout << "各边依次为：" << endl;
                for (i = 0; i<n; i++)
                {
                    for (j = 0; j<n; j++)
                    {
                        weight = this->getWeight(i, j);
                        if (weight>0 && weight< MAX_WEIGHT)
                        {
                            e1 = this->getValue(i);
                            e2 = this->getValue(j);
                            cout << "(" << e1 << "," << e2 << "," << weight << ")" << endl;
                        }
                    }
                }
    
       }
    
        template<class T, class E>
         void GraphMatrix<T, E>::bfsIndex(int i)
        {
    
             for (int j = 0; j < this->verticleSize; j++) {
                 visit[j] = false;
             }
             for (int j = i; j < this->verticleSize; j++) {
                 if (!visit[j]) {
                     bfs(j);
                 }
             }
             for (int j = 0; j < i; j++) {
                 if (!visit[j]) {
                     bfs(j);
                 }
             }
    
        }
    
        template<class T, class E>
        void GraphMatrix<T, E>::bfs(int i)
        {
            if (!visit[i]) {
                cout << i << ",";
                visit[i] = true;
            }
             if (getFirstNeighbor(i) == MAX_WEIGHT) {
                 return;
             }
             queue<int> q;
             int v = getFirstNeighbor(i);
             while (v!=MAX_WEIGHT)
             {
                 if (!visit[v]) {
    
                     q.push(v);
                     visit[v] = true;
                     cout << v << ",";
                 }
                 v = getNextNeighbor(i, v);
             }
             while (!q.empty())
             {
                 int vert = q.front();
                 q.pop();
                 bfs(vert);
    
             }
    
    
    
    
    
        }
    
    
        template<class T, class E>
         void GraphMatrix<T, E>::dfsStack(int i)
        {
             stack<int> s;
             visit[i] = true;
             cout << i<<",";
             s.push(i);
            while (!s.empty())
             {
                 int vert = getUnVisitedVerticles(s.top());
                 if (vert != MAX_WEIGHT) {
                     visit[vert] = true;
                     cout << vert << ",";
                     s.push(vert);
    
                 }
                 else {
                     int top = s.top();
                     s.pop();
                     if (s.empty()) {
                         int un = findNextUnVisitedVert(top);
                         if (un != MAX_WEIGHT) {
                             s.push(un);
                             cout << un << ",";
                             visit[un] = true;
    
                         }
                     }
                 }
    
             }
    
    
        }
    
         template<class T, class E>
          void GraphMatrix<T, E>::dfsIndex(int i)
         {
    
              for (int j = 0; j < this->verticleSize; j++) {
                  visit[j] = false;
              }
              for (int j = i; j < this->verticleSize; j++) {
                  if (!visit[j]) {
                      dfs(j);
                  }
              }
              for (int j = 0; j < i; j++) {
                  if (!visit[j]) {
                      dfs(j);
                  }
              }
         }
    
         template<class T, class E>
          void GraphMatrix<T, E>::dfs(int i)
         {
              visit[i] = true;
              cout << i << ",";
              int vert = getFirstNeighbor(i);
    
              while (vert!=MAX_WEIGHT)
              {
                 if(!visit[vert])
                  dfs(vert);
                  vert = getNextNeighbor(i, vert);
              }
         }
    
         template<class T, class E>
          int GraphMatrix<T, E>::getUnVisitedVerticles(int i)
         {
             for (int j = 0; j < this->verticleSize; j++) {
                 if (matrix[i][j] > 0 && matrix[i][j] < MAX_WEIGHT && !visit[j]) {
                     return j;
                 }
             }
    
             return MAX_WEIGHT;
         }
    
          template<class T, class E>
          inline int GraphMatrix<T, E>::findNextUnVisitedVert(int i)
          {
              for (int j = i+1; j < this->verticleSize; j++) {
                  if (!visit[j]) {
                      return j;
                  }
              }
              for (int j = 0; j < i; j++) {
                  if (!visit[j]) {
                      return j;
                  }
              }
              return MAX_WEIGHT;
          }

测试代码

#include "GraphMatrix.h"
    #define varName(x) #x  
    int main() {
        GraphMatrix<string, int> m(5);
        int * v0 = new int[5]{
       0,INF,INF,INF,6};
        int * v1 = new int[5]{ 9,0,3,INF,INF };
        int * v2 = new int[5]{ 2,INF,0,5,INF };
        int * v3 = new int[5]{ INF,INF,INF,0,1 };
        int * v4 = new int[5]{ INF,INF,INF,INF,0 };
        m.getMatrix()[0] = v0;
        m.getMatrix()[1] = v1;
        m.getMatrix()[2] = v2;
        m.getMatrix()[3] = v3;
        m.getMatrix()[4] = v4;
    
        m.getVerticles()[0] = varName(v0);
        m.getVerticles()[1] = varName(v1);
        m.getVerticles()[2] = varName(v2);
        m.getVerticles()[3] = varName(v3);
        m.getVerticles()[4] = varName(v4);
    
        m.outputGraph();
    
    
        m.dfsIndex(1);
        cout << endl;
        m.bfsIndex(1);
    
        system("pause");
    }

[SouthEast]: /images/20220601/0a12f3c91fec4bf3bf687bc6308905e2.png
[SouthEast 1]: /images/20220601/bbda2ee4ca634615a3f94c526d092bdc.png
[SouthEast 2]: /images/20220601/692e0f41a1294fc0a8d759a5f4e5af04.png