图论(Graph Theory)

图论(Graph Theory)

一、介绍

图是用来对对象之间的成对关系建模的数学结构,由”节点”或”顶点”(Vertex)以及连接这些顶点的”边”(Edge)组成。

图论(Graph Theory)

值得注意的是,图的顶点集合不能为空,但边的集合可以为空。图可能是无向的,这意味着图中的边在连接顶点时无需区分方向。否则,称图是有向的。

二、图的分类

  1. 图分为:无向图和有向图(无向图是有向图的特殊形式)
    无向图:
    图论(Graph Theory)

有向图:
图论(Graph Theory)

  1. 按权分为:无权图和有权图
    无权图:
    图论(Graph Theory)

有权图:

图论(Graph Theory)

  1. 图有平行边,自环边:

图论(Graph Theory)

三、图的表示

  1. 邻接矩阵:

    0——表示未连接 1——表示连接

  • 无向图的邻接矩阵:
    图论(Graph Theory)
  • 有向图的邻接矩阵:
    图论(Graph Theory)

适用说明:邻接矩阵适合表示稠密图

图论(Graph Theory)

  1. 邻接表:
  • 无向图的邻接表
    图论(Graph Theory)
  • 有向图的邻接表
    图论(Graph Theory)

适用说明:邻接表适合表示稀疏图

图论(Graph Theory)

四、稠密图、稀疏图的实现(无权图)

  1. 稠密图的实现
    支持的操作有:
  • 返回节点数

  • 返回边数

  • 向图中添加边

  • 验证两节点间是否有边

  • 显示图的信息

    #include <iostream>
    #include <vector>
    #include <cassert>
    using namespace std;
    //稠密图
    class DenseGraph{
    private:
        int n, m; //节点数和边数
        bool directed; //是否为有向图
        vector<vector<bool>> g; //图的具体数据,0 1 用bool值false和true表示
    public:
        DenseGraph(int n, bool directed){
          assert(n >= 0);
          this->n = n;
          this->m = 0;
          this->directed = directed;
    // g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边
          g = vector<vector<bool>>(n, vector<bool>(n, false));
    }
      //析构函数
      ~DenseGraph(){}
    //返回图中节点的个数
    int getV(){
         return n;
    }
    //返回图中边的条数
    int getE(){
         return m;
    }
    //向图中添加一条边
    void addEdga(int v, int w){
          assert(v >= 0 && v < n);
          assert(w >= 0 && w < n);
          if(hasEdga(v, w)){
               return;
           }
    
          g[v][w] = true;
        //无向图是双向的
          if(!directed){
               g[w][v] = true;
           }
          m++;
    }
    //验证图中是否有v到w的边
    bool hasEdga(int v, int w){
         assert(v >= 0 && v < n);
         assert(w >= 0 && w < n);
         return g[v][w];
    }
    //显示图中信息
    void show(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cout<<g[i][j]<<"\t";
        cout<<endl;
         }
        }
      }
    };
  1. 稀疏图的实现

支持的操作有:

  • 返回节点数

  • 返回边数

  • 向图中添加边

  • 验证两节点间是否有边

  • 显示图的信息

    #include <iostream>
    #include <vector>
    #include <cassert>
    using namespace std;
    //稀疏图—邻接表
    class SparseGraph{
    private:
        int n, m; //节点数和边数
        bool directed; //是否为无向图
        vector<vector<int>> g; //图的具体数据
    public:
       SparseGraph(int n,bool directed){
           assert(n >= 0);
           this->n = n;
           this->directed = directed;
           // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
           g = vector<vector<int>>(n, vector<int>());
    }
      //析构函数
      ~SparseGraph(){}
    
      int getV(){
          return n;
    }
      int getE(){
          return m;
    }
    // 向图中添加一个边
    void addEdga(int v, int w){
          assert( v >= 0 && v < n );
          assert( w >= 0 && w < n );
         //将w放入g[v][i]中,将w与v相连
          g[v].push_back(w);
          if(v != w && !directed){
              g[w].push_back(v);
          }
          m ++;
    }
    // 验证图中是否有从v到w的边
    bool hasEdga(int v, int w){
          assert( v >= 0 && v < n );
          assert( w >= 0 && w < n );
          for(int i = 0; i <= g[v].size(); i++){
                if(g[v][i] == w)
                     return true;
                return false;  }
    }
    //显示图中信息
    void show(){
        for(int i = 0; i < n; i++){
            cout<<"vector"<<":\t";
            for(int j = 0; j < g[i].size(); j++){
                cout<<g[i][j]<<":\t";
              }
            cout<<endl;
        }
      }
    };
    
    
    
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!