【高阶数据结构】图 -- 详解（上）-阿里云开发者社区

一、图的基本概念

图 是由顶点集合及顶点间的关系组成的一种数据结构：G = (V， E)。其中：

顶点集合 V = {x | x属于某个数据对象集} 是有穷非空集合；
E = {(x,y) | x,y属于V} 或者 E = { | x,y属于V && Path(x, y)} 是顶点间关系的有穷集合，也叫做边的集合。
(x, y) 表示 x 到 y 的一条双向通路，即 (x, y) 是无方向的；
Path(x, y) 表示从 x 到 y 的一条单向通路，即 Path(x, y) 是有方向的。

G：Graph（图），E：Edge（边）。

注意：

树是一种特殊（无环联通）的图。

图不一定是树。

树关注的是节点（顶点）中存的值；而图关注的是顶点和边的权值。

树属于存储型结构，每个节点存储对应的值；而图属于表示型结构，表示某种场景。

【交通网络图】

顶点：城市

边：城市之间的一个关系（高铁距离、高铁价格、高铁时间、高速距离...）

【社交关系】

顶点：人

边：表示两个人是好友

边权值：亲密度等

强社交关系（微信、QQ 等关系 -> 无向图）

弱社交关系、媒体社交（微博、抖音等关系 -> 有向图）

顶点和边：图中结点称为顶点，第 i 个顶点记作 vi。两个顶点 vi 和 vj 相关联称作顶点 vi 和顶点 vj 之间有一条边，图中的第 k 条边记作 ek，ek = (vi，vj) 或。

有向图和无向图：在有向图中，顶点对< x, y> 是有序的，顶点对称为顶点 x 到顶点 y 的一条边(弧)，和是两条不同的边，比如下图 G3 和 G4 为有向图。在无向图中，顶点对 (x, y) 是无序的，顶点对 (x, y) 称为顶点 x 和顶点 y 相关联的一条边，这条边没有特定方向， (x, y) 和 (y，x) 是同一条边，比如下图 G1 和 G2 为无向图。

注意：无向边 (x, y) 等于有向边和 。

完全图：在有 n 个顶点的无向图中，若有 n * (n-1)/2 条边，即任意两个顶点之间有且仅有一条边，则称此图为无向完全图，比如上图 G1；在 n 个顶点的有向图中，若有 n * (n-1) 条边，即任意两个顶点之间有且仅有方向相反的边，则称此图为有向完全图，比如上图 G4。

邻接顶点：在无向图中 G 中，若 (u, v) 是 E(G) 中的一条边，则称 u 和 v 互为邻接顶点，并称边 (u, v) 依附于顶点 u 和 v；在有向图 G 中，若是 E(G) 中的一条边，则称顶点u邻接到v，顶点 v 邻接自顶点 u，并称边与顶点 u 和顶点 v 相关联。

顶点的度：顶点 v 的度是指与它相关联的边的条数，记作 deg(v)。在有向图中，顶点的度等于该顶点的入度与出度之和，其中顶点 v 的入度是以 v 为终点的有向边的条数，记作 indev(v)；顶点 v 的出度是以 v 为起始点的有向边的条数，记作 outdev(v)。因此：dev(v) = indev(v) + outdev(v)。

注意：对于无向图，顶点的度等于该顶点的入度和出度，即 dev(v) = indev(v) = outdev(v)。

路径：在图 G = (V, E) 中，若从顶点 vi 出发有一组边使其可到达顶点 vj，则称顶点 vi 到顶点 vj 的顶点序列为从顶点 vi 到顶点 vj 的路径。

路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。

简单路径与回路：若路径上各顶点 v1，v2，v3，…，vm 均不重复，则称这样的路径为简单路径。若路径上第一个顶点 v1 和最后一个顶点 vm 重合，则称这样的路径为回路或环。

子图：设图 G = {V, E} 和图 G1 = {V1，E1}，若 V1 属于 V 且 E1 属于 E，则称 G1 是 G 的子图。（顶点和边都是原图的一部分）

连通图：在无向图中，若从顶点 v1 到顶点 v2 有路径，则称顶点 v1 与顶点 v2 是连通的。如果图中任意一对顶点都是连通的，则称此图为连通图。

强连通图：在有向图中，若在每一对顶点 vi 和 vj 之间都存在一条从 vi 到 vj 的路径，也存在一条从vj 到 vi 的路径，则称此图是强连通图。

生成树：无向图，一个连通图的最小连通子图称作该图的生成树。有 n 个顶点的连通图的生成树有 n 个顶点和 n- 1 条边。

二、图的存储结构

因为图中既有节点，又有边（节点与节点之间的关系）。因此，在图的存储中，只需要保存：节点和边关系即可。节点保存比较简单，只需要一段连续空间即可，那边的关系该怎么保存呢？

1、邻接矩阵

因为节点与节点之间的关系就是连通与否，即为 0 或者 1，因此邻接矩阵（二维数组）即是：先用一 个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。

注意：

无向图的邻接矩阵是对称的（可以做压缩），第 i 行（列）元素之和，就是顶点 i 的度。有向图的邻接矩阵则不一定是对称的，第 i 行（列）元素之后就是顶点 i 的出（入）度。

如果边带有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果两个顶点不通，则使用无穷大代替。

用邻接矩阵存储图（适合稠密图）的优点是能够 快速知道（O(1)）两个顶点是否连通并取到权值 ，缺陷是如果顶点比较多，边比较少（稀疏图）时，矩阵中存储了大量的 0 成为系数矩阵，比较浪费空间，并且要求两个节点之间的路径不是很好求。

相对而言，邻接矩阵不适合查找一个顶点连接的所有边（O(N)）。

【代码实现】

//Test.cpp
#include <iostream>
using namespace std;
 
#include "Graph.h"
 
int main()
{
  matrix::TestGraph1();
  return 0;
}

//Graph.h
#pragma once
#include <vector>
#include <map>
 
// 邻接矩阵
namespace matrix
{
  template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
  class Graph
  {
  public:
    // 图的创建
    // 1、IO输入 —— 不方便测试，在OJ中更适合
    // 2、图结构关系写到文件中，读取文件
    // 3、手动添加边
    Graph(const V* a, size_t n)
    {
      _vertexs.reserve(n);
      for (size_t i = 0; i < n; i++)
      {
        _vertexs.push_back(a[i]);
        _indexMap[a[i]] = i;
      }
 
      // MAX_W作为不存在边的标识值
      _matrix.resize(n);
      for (size_t i = 0; i < _matrix.size(); i++)
      {
        _matrix[i].resize(n, MAX_W);
      }
    }
 
    size_t GetVertexIndex(const V& v)
    {
      auto it = _indexMap.find(v);
      if (it != _indexMap.end())
      {
        return it->second;
      }
      else
      {
        //assert(false);
        throw invalid_argument("顶点不存在");
        return -1; //防止编译器检查返回值
      }
    }
 
    void AddEdge(const V& src, const V& dst, const W& w)
    {
      size_t srci = GetVertexIndex(src);
      size_t dsti = GetVertexIndex(dst);
 
      _matrix[srci][dsti] = w;
      // 无向图
      if (Direction == false)
      {
        _matrix[dsti][srci] = w;
      }
    }
 
    void Print()
    {
      // 打印顶点和下标的映射关系
      // 打印顶点
      for (size_t i = 0; i < _vertexs.size(); i++)
      {
        cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
      }
      cout << endl;
 
      // 打印矩阵
      // 打印横下标
      cout << "  ";
      for (size_t i = 0; i < _vertexs.size(); i++)
      {
        cout << i << ' ';
      }
      cout << endl;
 
      for (size_t i = 0; i < _matrix.size(); i++)
      {
        cout << i << ' '; //打印竖下标
        for (size_t j = 0; j < _matrix[i].size(); j++)
        {
          //cout << _matrix[i][j] << ' ';
          if (_matrix[i][j] == MAX_W)
          {
            cout << "* ";
          }
          else
          {
            cout << _matrix[i][j] << ' ';
          }
        }
        cout << endl;
      }
      cout << endl;
    }
 
  private:
    vector<V> _vertexs;     // 顶点集合
    map<V, int> _indexMap;    // 顶点映射下标
    vector<vector<W>> _matrix;  // 邻接矩阵
  };
 
  void TestGraph1()
  {
    Graph<char, int, INT_MAX, true> g("0123", 4);
    g.AddEdge('0', '1', 1);
    g.AddEdge('0', '3', 4);
    g.AddEdge('1', '3', 2);
    g.AddEdge('1', '2', 9);
    g.AddEdge('2', '3', 8);
    g.AddEdge('2', '1', 5);
    g.AddEdge('2', '0', 3);
    g.AddEdge('3', '2', 6);
    g.Print();
  }
}

结果显示：

2、邻接表

邻接表：使用数组表示顶点的集合，使用链表表示边的关系。

邻接表适合存储稀疏图，适合查找一个顶点连出去的边。
邻接表不适合确定两顶点之间是否相连和查看权值。

（1）无向图邻接表存储

注意：无向图中同一条边在邻接表中出现了两次。如果想知道顶点 vi 的度，只需要知道顶点 vi 边链表集合中结点的数目即可。

（2）有向图邻接表存储

一般情况下，有向图存储一个出边表即可。

注意：有向图中每条边在邻接表中只出现一次，与顶点 vi 对应的邻接表所含结点的个数，就

是该顶点的出度，也称出度表，要得到 vi 顶点的入度，必须检测其他所有顶点对应的边链

表，看有多少边顶点的 dst 取值是 i。

【总结】

邻接矩阵和邻接表相辅相成，各有优缺点的互补结构。

【代码实现】

//Test.cpp
#include <iostream>
using namespace std;
 
#include "Graph.h"
 
int main()
{
  link_table::TestGraph1();
  return 0;
}

//Graph.h
#pragma once
#include <vector>
#include <map>
#include <string>
 
//邻接表
namespace link_table
{
  template<class W>
  struct Edge
  {
    int _dsti; //目标点的下标
    W _w;    //权值
    Edge<W>* _next;
 
    Edge(int dsti, const W& w)
      :_dsti(dsti)
      ,_w(w)
      ,_next(nullptr)
    {}
  };
 
  template<class V, class W, bool Direction = false>
  class Graph
  {
    typedef Edge<W> Edge;
  public:
    Graph(const V* a, size_t n)
    {
      _vertexs.reserve(n);
      for (size_t i = 0; i < n; i++)
      {
        _vertexs.push_back(a[i]);
        _indexMap[a[i]] = i;
      }
 
      _tables.resize(n, nullptr);
    }
 
    size_t GetVertexIndex(const V& v)
    {
      auto it = _indexMap.find(v);
      if (it != _indexMap.end())
      {
        return it->second;
      }
      else
      {
        //assert(false);
        throw invalid_argument("顶点不存在");
        return -1; //防止编译器检查返回值
      }
    }
 
    void AddEdge(const V& src, const V& dst, const W& w)
    {
      size_t srci = GetVertexIndex(src);
      size_t dsti = GetVertexIndex(dst);
 
      // 1->2
      Edge* eg = new Edge(dsti, w);
      eg->_next = _tables[srci];
      _tables[srci] = eg;
 
      // 2->1
      if (Direction == false)
      {
        Edge* eg = new Edge(srci, w);
        eg->_next = _tables[dsti];
        _tables[dsti] = eg;
      }
    }
 
    void Print()
    {
      // 打印顶点和下标的映射关系
      // 打印顶点
      for (size_t i = 0; i < _vertexs.size(); i++)
      {
        cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
      }
      cout << endl;
 
      for (size_t i = 0; i < _tables.size(); i++)
      {
        cout << _vertexs[i] << "[" << i << "]->";
        Edge* cur = _tables[i];
        while (cur)
        {
          cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
          cur = cur->_next;
        }
        cout << "nullptr" << endl;
      }
    }
 
  private:
    vector<V> _vertexs;     // 顶点集合
    map<V, int> _indexMap;    // 顶点映射下标
    vector<Edge*> _tables;    // 邻接表
  };
 
  void TestGraph1()
  {
    string a[] = { "张三", "李四", "王五", "赵六" };
    Graph<string, int, true> g1(a, 4);
    g1.AddEdge("张三", "李四", 100);
    g1.AddEdge("张三", "王五", 200);
    g1.AddEdge("王五", "赵六", 30);
    g1.Print();
  }
}

三、图的遍历

图的遍历针对的是图的顶点，而不是图的边。

给定一个图 G 和其中任意一个顶点 v0，从 v0 出发，沿着图中各边访问图中的所有顶点，且每个顶点仅被遍历一次。“遍历” 即对结点进行某种操作的意思。

树以前是怎么遍历的，此处可以直接用来遍历图吗？为什么？

1、图的广度优先遍历（BFS）

如何防止节点被重复遍历？

void BFS(const V& src)
{
    size_t srci = GetVertexIndex(src);
 
  // 队列和标记数组
  queue<int> q;
  vector<bool> visited(_vertexs.size(), false);
      
  q.push(srci);
  visited[srci] = true;
  int levelSize = 1;
 
  size_t n = _vertexs.size();
  while (!q.empty())
  {
    // 一层一层出
    for (int i = 0; i < levelSize; i++)
    {
      int front = q.front();
      q.pop();
      cout << front << ":" << _vertexs[front] << ' ';
      // 把front顶点的邻接顶点入队列
      for (size_t i = 0; i < n; i++)
      {
        if (_matrix[front][i] != MAX_W)
        {
          if (visited[i] == false)
          {
            q.push(i);
            visited[i] = true;
          }
        }
      }
    }
    cout << endl;
    levelSize = q.size();
  }
  cout << endl;
}
 
void TestBDFS()
{
  string a[] = { "张三", "李四", "王五", "赵六", "周七" };
  Graph<string, int> g1(a, sizeof(a) / sizeof(string));
  g1.AddEdge("张三", "李四", 100);
  g1.AddEdge("张三", "王五", 200);
  g1.AddEdge("王五", "赵六", 30);
  g1.AddEdge("王五", "周七", 30);
  g1.Print();
 
  g1.BFS("张三");
}

2、图的深度优先遍历（DFS）

void _DFS(size_t srci, vector<bool>& visited)
{ 
  cout << srci << ":" << _vertexs[srci] << endl;
  visited[srci] = true;
 
  // 找一个srci相邻的没有访问过的点，去往深度遍历
  for (size_t i = 0; i < _vertexs.size(); i++)
  {
    if (_matrix[srci][i] != MAX_W && visited[i] == false)
    {
      _DFS(i, visited);
    }
  }
}
 
void DFS(const V& src)
{
  size_t srci = GetVertexIndex(src);
  vector<bool> visited(_vertexs.size(), false);
 
  _DFS(srci, visited);
}
 
void TestBDFS()
{
    string a[] = { "张三", "李四", "王五", "赵六", "周七" };
    Graph<string, int> g1(a, sizeof(a) / sizeof(string));
  g1.AddEdge("张三", "李四", 100);
  g1.AddEdge("张三", "王五", 200);
  g1.AddEdge("王五", "赵六", 30);
  g1.AddEdge("王五", "周七", 30);
  g1.Print();
 
  g1.DFS("张三");
}

【高阶数据结构】图 -- 详解（下）https://developer.aliyun.com/article/1515770?spm=a2c6h.13148508.setting.27.11104f0e63xoTy

【高阶数据结构】图 -- 详解（上）

一、图的基本概念

二、图的存储结构

1、邻接矩阵

【代码实现】

2、邻接表

（1）无向图邻接表存储

（2）有向图邻接表存储

【总结】

【代码实现】

三、图的遍历

1、图的广度优先遍历（BFS）

如何防止节点被重复遍历？

2、图的深度优先遍历（DFS）

热门文章

最新文章

相关课程

相关电子书