【高阶数据结构】图 -- 详解(上)

简介: 【高阶数据结构】图 -- 详解(上)

一、图的基本概念

是由顶点集合及顶点间的关系组成的一种数据结构: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,因此邻接矩阵(二维数组)即是:先用一 个数组将定点保存,然后采用矩阵来表示节点与节点之间的关系

注意

  1. 无向图的邻接矩阵是对称的(可以做压缩)第 i 行(列)元素之和,就是顶点 i 的度有向图的邻接矩阵则不一定是对称的,第 i 行(列)元素之后就是顶点 i 的出(入)度
  2. 如果边带有权值,并且两个节点之间是连通的,上图中的边的关系就用权值代替,如果两个顶点不通,则使用无穷大代替。
  3. 用邻接矩阵存储图(适合稠密图)的优点是能够 快速知道(O(1))两个顶点是否连通并取到权值 ,缺陷是如果顶点比较多,边比较少(稀疏图)时,矩阵中存储了大量的 0 成为系数矩阵,比较浪费空间,并且要求两个节点之间的路径不是很好求。
  4. 相对而言,邻接矩阵不适合查找一个顶点连接的所有边(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

相关文章
|
11天前
|
存储
数据结构学习记录——如何建立图(邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立)
数据结构学习记录——如何建立图(邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立)
12 0
|
11天前
|
存储 算法
数据结构学习记录——图应用实例-六度空间(题目描述、算法思路、伪代码及解读、图解)
数据结构学习记录——图应用实例-六度空间(题目描述、算法思路、伪代码及解读、图解)
9 0
|
11天前
|
存储 算法 安全
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
10 0
|
11天前
|
存储 C语言
数据结构学习记录——图的遍历(深度优先搜索、广度优先搜索、为什么需要两种遍历、图不连通怎么办)
数据结构学习记录——图的遍历(深度优先搜索、广度优先搜索、为什么需要两种遍历、图不连通怎么办)
17 0
|
11天前
|
存储 机器学习/深度学习
数据结构学习记录——什么是图(抽象数据类型定义、常见术语、邻接矩阵表示法、邻接表表示法)
数据结构学习记录——什么是图(抽象数据类型定义、常见术语、邻接矩阵表示法、邻接表表示法)
17 0
|
25天前
|
存储 NoSQL 算法
【高阶数据结构】跳表 -- 详解
【高阶数据结构】跳表 -- 详解
|
25天前
|
存储 算法 关系型数据库
【高阶数据结构】 B树 -- 详解
【高阶数据结构】 B树 -- 详解
|
26天前
|
缓存 算法 内存技术
【高阶数据结构】LRU Cache -- 详解
【高阶数据结构】LRU Cache -- 详解
|
26天前
|
算法
【高阶数据结构】图 -- 详解(下)
【高阶数据结构】图 -- 详解(下)
|
26天前
|
存储
【高阶数据结构】并查集 -- 详解
【高阶数据结构】并查集 -- 详解