图论相关帖子

• 基本概念
• 图的表示: 邻接矩阵和邻接表
• 图的遍历: 深度优先与广度优先
• 拓扑排序
• 图的最短路径:Dijkstra算法和Bellman-Ford算法
• 最小生成树: Prim算法和Kruskal算法
• 二分图
• 多源最短路径: Floyd-Warshall算法和Johnson算法
• 强连通分量: Kosaraju算法和Tarjan算法
• 欧拉回路: Fleury算法和Hierholzer算法
• 网络流算法: Edmonds-Karp算法
• 网络流算法: Dinic算法

环境要求

本文所用样例在Windows 11以及Ubuntu 24.04上面编译通过.

1. Windows: 使用[Visual Studio],
2. Ubuntu: 使用 Clang 18.1.3. (Ubuntu 24.04 系统安装版本)
3. GCC 无法编译直接本项目代码, 因为本文代码使用了 C++20 Module, 而 GCC 对此支持不完整.

概述

本节讲述如何在 C++ 中表示简单图, 本节将介绍邻接矩阵和邻接表的实现. 后续系列的博客中将会以邻接表为主, 偶尔会用到邻接矩阵.

简单图, 即没有自环边(自己指向自己的边)和平行边(两个顶点之间存在多条边). 根据前一节提到的知识, 我们给出一个简单图的接口:

typedef unsigned Vertex;
typedef int Weight;
typedef std::pair<Vertex, Vertex> Edge;
typedef std::tuple<Vertex, Vertex, Weight> WeightedEdge;

struct Graph {
   
  virtual ~Graph() = default;

  // 获取顶点数量
  [[nodiscard]] virtual size_t V() const = 0;

  // 获取边数量
  [[nodiscard]] virtual size_t E() const = 0;

  // 该图是有向图吗?
  [[nodiscard]] virtual bool Directed() const = 0;

  // 该图是带权图吗?
  [[nodiscard]] virtual bool Weighted() const = 0;

  // 获取顶点u的所有邻接顶点
  [[nodiscard]] virtual std::set<Vertex> Adj(Vertex u) const = 0;

  // 顶点u,v之间是否存在一条边
  [[nodiscard]] virtual bool HasEdge(Vertex u, Vertex v) const = 0;

  // 添加边u,v
  virtual void AddEdge(Vertex u, Vertex v) = 0;

  // 添加带权边u,v
  virtual void AddEdge(Vertex u, Vertex v, Weight w) = 0;

  // 将图以dot格式输出(Graphviz支持的格式), 可用于可视化
  [[nodiscard]] virtual std::string FormatAsDot() const = 0;
};
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">