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

一、图的基本概念

图 是由顶点集合及顶点间的关系组成的一种数据结构：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）

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

一、图的基本概念

二、图的存储结构

1、邻接矩阵

【代码实现】

2、邻接表

（1）无向图邻接表存储

（2）有向图邻接表存储

【总结】

【代码实现】

三、图的遍历

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

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

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

热门文章

最新文章

相关课程

相关电子书