系列文章目录：

图

图（Graph）是一种由顶点和边组成的抽象数据结构，用于表示对象之间的连接关系。图中的顶点表示对象，边表示顶点之间的连接关系。

一般地，图这个集合用 $G(V,E)$ 表示，其中V是顶点（vertex）的集合，E是边（edge）的集合。

注意：图的点是有穷非空集合，即顶点数是有限的，且至少有一个顶点，而边可以没有一条边。

图的分类

有向图和无向图

图按照边有无方向分为有向图和无向图，顾名思义有向图中的边是有方向的，而无向图中的边是没有方向的。

以下示例即为有向图：

有向图可以用集合表示为：
$\begin{aligned} G&=(V,E) \\ V&= \{A,B,C,D,E,F\}\\ G&=\{<A,B>,<B,E>,<E,F>,<A,C>,<C,E>,<C,D>,<B,D>,<D,F>\}\subseteq V\times V \end{aligned}$
在有向图中，边也叫弧（arc），箭头指向的起点称弧尾（tail），箭头指向的终点称弧头（head）。

注意：有向图的边集合 $\mathbf E = \{ <u_i,v_i>|u_i,v_i\in \mathbf V \}$ 中要使用尖括号表示，强调关系指向。

以下示例即为无向图：

无向图可以用集合表示为：
$\begin{aligned} G&=(V,E) \\ V&= \{A,B,C,D,E,F\}\\ G&=\{(A,B), (A,C), (B,D), (B,E), (C,D), (C,E), (D,F), (E,F)\} \end{aligned}$

注意：无向图的边集合 $\mathbf E = \{(u_i,v_i)|u_i,v_i\in \mathbf V \}$ 中要使用圆括号表示。

简单图和多重图

图按照是否允许重边/自环可分为简单图（simple graph）、严格多重图（most common）和伪图（pseudograph），以下我们以无向图举例：

简单图：不允许有重边（同一对顶点之间出现两条或以上的边）和自环。其离散数学定义为：
$G=(V,E)\ , \ E\subseteq \{(u,v)|u,v\in V \wedge u ≠ v \}$
严格多重图：允许有重边和不允许自环 。其离散数学定义为：
- 这里的 $m$ 表示一个函数映射，对于边集合中的任意元素 $(u,v)$ 都会映射到一个自然数，表示该边出现的次数。
伪图：允许有重边和自环。其离散数学定义为：
- 这里不强调≠号，即允许自环 $u=v$。

本章学习中一般探讨的内容都是简单图，即不允许有重边和自环。

稠密图与稀疏图

按照图的边数与顶点数的比值，图可以分为稠密图和稀疏图：

无向图
- 完全图：边数 $|E|=\frac{|V|(|V|-1)}{2}\approx \frac{|V|^2}{2}$
- 稠密图：边数 $|E| \sim \frac{|V|^2}{2}$
- 稀疏图：边数 $|E| \ll \frac{|V|^2}{2}$
有向图
- 完全图：边数 $|E|=|V|(|V|-1)\approx |V|^2$
- 稠密图：边数 $|E| \sim |V|^2$
- 稀疏图：边数 $|E| \ll |V|^2$

对于有向图和无向图最大边数的推导：

无向图：
我们令 $|V|=n$，则边数 $|E|=\binom{n}{2} =\frac{n(n-1)}{2}$，当 $n$ 趋于无穷大时，$|E|$ 趋于 $\frac{n^2}{2}$。
有向图：
我们同样令 $|V|=n$，那么每个顶点可以与剩下的 $n-1$ 个顶点连边，因此 $|E|=n(n-1)$，当 $n$ 趋于无穷大时，$|E|$ 趋于 $n^2$。

一些定义和关系

基本概念

路径（Path）：从一个顶点到另一个顶点所经过的结点序列
路径长度（Path Length）：路径上经过的边的个数
回路（环）（Cycle / Circuit）：路径的第一个顶点和最后一个顶点相同
简单路径（Simple Path）：不重复经过顶点的路径
简单回路：除了第一个顶点和最后一个顶点外，不重复经过其他顶点的回路
欧拉图 （Euler Graph）：一个无向图，如果从图中任意两个顶点 $v_i$ 和 $v_j$ 都存在一条路径，则称该图为欧拉图
欧拉回路 （Euler Circuit）：在一个图中，若存在一条回路包含图中所有的边，则称这条回路为欧拉回路
度（ Degree ，deg(v) ）：在无向图中，与一个顶点相邻的边的条数称为该顶点的度
入度（ In-Degree ，deg⁻(v) ）：有向图中，以某顶点为终点的边的条数称为该顶点的入度
出度（ Out-Degree ，deg⁺(v) ）：有向图中，以某顶点为起点的边的条数称为该顶点的出度
子图（Subgraph）：若两个图 $G=(V,E)$ 和 $G’=(V’,E’)$ 满足 $V’\subseteq V$ 且 $E’\subseteq E$，则称 $G’$ 是 $G$ 的子图
连通图（Connected Graph）：在无向图中，若从顶点 $v_i$ 到顶点 $v_j$ 有路径，则称 $v_i$ 和 $v_j$ 是连通的。若图中任意两个顶点都是连通的，则称该图为连通图
连通分量（Connected Component）：无向图中的极大连通子图称为该图的连通分量
- 连通分量为子图；
- 子图为连通图；
- 连通子图含有极大顶点数；
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边
强连通图（Strongly Connected Graph）： 有向图中，若从顶点 $v_i$ 到顶点 $v_j$ 有路径，且从顶点 $v_j$ 到顶点 $v_i$ 也有路径，则称 $v_i$ 和 $v_j$ 是强连通的。若图中任意两个顶点都是强连通的，则称该图为强连通图
强连通分量（Strongly Connected Component ，SCC）：有向图中的极大强连通子图称为该图的强连通分量
生成树（Spanning Tree）：一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的 $|V|-1$ 条边
生成森林（Spanning Forest）：非连通图的生成森林是由各个连通分量的生成树构成的集合
权（Weight）：在图的边或顶点与某个数值之间建立对应关系，称为权
带权图（Weighted Graph / Network）：在图中边上带权值的图称为带权图，也称为网（络）
最短路径（Shortest Path）：从一个顶点到另一个顶点的权值之和最小的路径称为最短路径
最小生成树（Minimum Spanning Tree ，MST）：一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的 $|V|-1$ 条边，且各边的权值之和最小

关系

顶点度公式

无向图入度出度和顶点度满足以下关系：
$\sum_{v\in V}deg(v)=2|E|$

证明：

由于无向图每条边都对应两个顶点，每条边被它的两个端点各计算一次度，因此每条边被计算两次。即 $\sum_{v\in V}deg(v)=2|E|$

有向图入度出度和顶点度满足以下关系：
$\sum_{v\in V}deg⁻(v)=\sum_{v\in V}deg⁺(v)=|E|$

最大边数公式

无向图：
$|E_{max}|=\binom{n}{2}=\frac{n(n-1)}{2}$
有向图：
$|E_{max}|=n(n-1)$

树的性质

前面说过，树是一种连通且无环的无向图，满足树的边数 $|E|$ 等于顶点数 $|V|$ 减一，即 $|E|=|V|-1$ （用归纳法证）

欧拉图条件

无向图欧拉回路条件：所有顶点的度数都为偶数
无向图欧拉路径条件：连通且恰有 0 或 2 个奇度顶点（实际上这个是充分必要条件）

图的存储结构

邻接矩阵（Adjacency Matrix）

邻接矩阵是这样一种矩阵，对于个某个元素 $a_{ij}$ ，如果顶点 $u_i$ 到 $v_j$ 有边，则 $a_{ij}=1$ ，否则 $a_{ij}=0$ 。

显然，对于有 $n$ 个顶点的图，邻接矩阵的大小为 $n^2$ 。

当然地，对于有向图，邻接矩阵是对称的，因为如果有 $u_i$ 到 $v_j$ 的边，那么一定有 $v_j$ 到 $u_i$ 的边，则 $a_{ij}=a_{ji}=1$ 。

邻接表（Adjacency List）

邻接表是这样一种数据结构，对于每一个顶点，存储一个链表，链表中的元素为与该顶点相连（出度）的顶点（位置）。

对于竞赛中，邻接表一般使用 vector<vector<int> > a(n); a[u].push_back(v) 表示u与v相连。

当然，如果是无向图，那么需要将两个顶点都加入对方的链表中，即：

1 2	G[u].push_back(v); G[v].push_back(u);

如果是用指针实现，请参考下面的代码：

// 边结构
struct EdgeNode
{
    int edge;  // 边指向的顶点编号
    EdgeNode* next;  // 指向下一个边结点
};

// 顶点结构
struct VertexNode
{
    int vertex;  // 顶点编号
    EdgeNode *fiedge;     // 指向第一条依附该顶点的边
};

// 图结构
struct Graph
{
    int vNum;  // 顶点数
    int eNum;  // 边数
    VertexNode *AdjList;  // 邻接表
};


void addEdge(Graph &G, int u, int v) //u->v
{
    EdgeNode *p = new EdgeNode;
    p->edge = v;
    p->next = G.AdjList[u].fiedge;  // // 新边指向原来的第一条边
    G.AdjList[u].fiedge = p;  // 新边成为第一条边
}

// 初始化图
void initGraph(Graph &G, int vNum, int eNum)
{
    G.vNum = vNum;
    G.eNum = eNum;
    G.AdjList = new VertexNode[G.vNum];
    for(int i=0; i<G.vNum; i++)
    {
        G.AdjList[i].vertex = i;
        G.AdjList[i].fiedge = nullptr;
    }
}

一定要注意，如果对空间要求比较严格的场景中，使用邻接表来存储无向图会多一倍的空间开销，那么此时使用邻接表不是一个很好的选择。后路面讲到的邻接多重表就可以解决这个问题。

逆向邻接表

和前面的邻接表类似，只不过存储的是入度的顶点（位置）。

这里就不贴代码了，和邻接表类似。

十字链表（Orthogonal List）

十字链表将邻接表和逆邻接表结合起来，使得可以同时表示有向图的出度和入度。

在十字链表中：

顶点结点（VNode）：存储顶点信息，以及指向第一条入边和第一条出边。
边结点（ENode）：存储一条有向边 u->v，主要包含：
- tailvex：边的起点编号
- headvex：边的终点编号
- hlink：下一条“以 v 为终点”的边（入边链）
- tlink：下一条“以 u 为起点”的边（出边链）

struct ArcNode
{
    int tailvex, headvex;    // 边<u, v>
    ArcNode *hlink;          // 指向同终点的下一条边 (入)
    ArcNode *tlink;          // 指向同起点的下一条边 (出)
};

struct VNode
{
    int data;        // 顶点信息
    ArcNode *firstin;    // 指向第一条入边
    ArcNode *firstout;   // 指向第一条出边
};

struct OLGraph
{
    VNode *xlist;   // 顶点数组
    int vexnum, arcnum; // 图的当前顶点数和边数
};

// 添加边 u->v
void addArc(OLGraph &g, int u, int v)
{
    ArcNode *arc = new ArcNode;
    arc->tailvex = u;
    arc->headvex = v;
    // 插入到 v 的入边表
    arc->hlink = g.xlist[v].firstin;
    g.xlist[v].firstin = arc;
    // 插入到 u 的出边表
    arc->tlink = g.xlist[u].firstout;
    g.xlist[u].firstout = arc;
}

邻接多重表 (Adjacency Multi-list)

该数据结构主要用于优化无向图的存储，原理和十字链表类似。

顶点结点（VNode）：存储顶点信息，以及连接该顶点一条边的指针
边结点（ENode）：存储一条无向边 u-v，主要包含：
- ivex：边连接其中一个顶点编号
- jvex：边连接另一个顶点编号
- ilink：挂在顶点 ivex 的下一条边
- jlink：挂在顶点 jvex 的下一条边

struct ENode
{
    int ivex, jidx;
    ENode *ilink, *jlink;  // 分别指向依附顶点相同的下一条边
};

struct VNode
{
    int idx;
    ENode *firstedge;  // 指向第一条依附该顶点的边
};

struct AMLGraph
{
    int vNum, eNum;
    VNode *adjList;
};

void addEdge(AMLGraph &G, int u, int v) // u<->v
{
    ENode *p = new ENode;
    p->ivex = u;
    p->jidx = v;
    // 插入到 u 的边表
    p->ilink = G.adjList[u].firstedge;
    G.adjList[u].firstedge = p;
    // 插入到 v 的边表
    p->jlink = G.adjList[v].firstedge;
    G.adjList[v].firstedge = p;
}

一个例子

例如下图，我们有集合 :

$\begin{aligned} G&=(V,E) \\ V&=\{1,2,3,4\}\\ E&=\{<1,2>,<2,3>,<3,4>,<4,1>,<2,4>\} \end{aligned}$

邻接矩阵为：

$G= \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \end{bmatrix}$

邻接表为：

逆邻接表为：

十字链表为：

图的遍历

图的遍历方式有很多，最基础的是深度优先搜索（DFS）和广度优先搜索（BFS），之后我们还会学习拓扑排序（Topological Sort）、强连通分量遍历（SCC）、最短路径遍历、最小生成树遍历、Eulerian / Hamiltonian 遍历等方法。

深度优先搜索（DFS）

顾名思义，该方法就是沿着一个方向一直往下搜索，直到无法继续为止，然后回溯到上一个节点，继续搜索其他路径。

这里采取洛谷书上的伪代码：

void dfs(...) // 函数内的参数主要是递归层数、当前节点位置等，记得要传vis
{
  if(达到目的/遍历完毕) // 比如说遍历到终点
  {
    判断是否满足条件
    记录结果
    return;
  }
  for(所有邻接点)
  {
    if(该点未访问)
    {
      vis标记为已访问（保存现场）
      dfs(递归层数+1/下一邻接点);
      vis标记为未访问（恢复现场）
    }
  }
}

递归的程序一定要留出口，否则会爆栈。
回溯时记得恢复现场，否则会影响后续的搜索。

广度优先搜索（BFS）

广度优先搜索就是从起点开始，一层一层地向外扩展，直到找到目标节点。

这里采取洛谷书上的伪代码：

void bfs(...) //由于bfs采用队列，这里传入的参数主要是队列、起点位置等
{
  初始化队列q;
  q.push(起点);
  while(!q.empty())
  {
    auto now=q.front(); //获取队首元素
    q.pop(); //弹出队首元素
    for(所有邻接点)
    {
      if(该点合法的)
        q.push(下一邻接点);
    }
  }
}

拓扑排序（Topological Sort）

拓扑排序是针对有向无环图（DAG）的遍历方式，它按照拓扑结构，将节点排序，使得每条有向边都从排在前面的节点指向排在后面的节点。

这里补充拓扑顺序的定义：

对于一个有向无环图（DAG） $G=(V,E)$ ，如果存在一个顶点序列：

$v_1,v_2,\cdots,v_n$

使得满足每条有向边u->v都有u在v前面 ，那么这个序列就被称为拓扑顺序。

例如上面这个图，它的拓扑顺序有：

$\begin{aligned} &1,5,2,9,7,3,4 \\ &1,2,5,9,7,3,4 \\ &1,5,2,7,9,3,4 \\ &\cdots \ \ \ \cdots \ \ \cdots \\ &1,2,5,3,7,9,4 \end{aligned}$

显然地，我们可以得到拓扑排序的性质：

拓扑排序的起点是入度为0的节点
拓扑排序的结果不唯一

该排序方法常用于任务调度、编译顺序（先编译依赖的库）、课程安排（先修课关系）、版本依赖管理等

拓扑排序的算法实现有两种方式，一种是Kahn(BFS)算法，另一种是DFS算法。

Kahn算法

Kahn算法是基于BFS实现的，它的思想是：每次从图中取出一个入度为0的节点，将其加入拓扑序列，然后将其所有邻接点的入度减1，重复此过程直到图为空。

这里我们使用栈来实现：

int* topoSort(Graph &G)//G为邻接表
{
    int topo[G.vNum];
    int in[G.vNum]={0}; //入度数组
    for(int i=0; i<G.vNum; i++)
    {
        EdgeNode *p=G.AdjList[i].fiedge;
        while(p) 
        {
            in[p->edge]++;
            p=p->next;
        }
    }
    Stack s;
    for(int i=0; i<G.vNum; i++)
        if(in[i]==0)s.push(i);
    int idx=0;
    while(!s.isEmpty())
    {
        int u=s.top(); s.pop();
        topo[idx++]=u;
        EdgeNode *p=G.AdjList[u].fiedge;
        while(p) // 将与u相连的结点入度都减1
        {
            in[p->edge]--;
            if(in[p->edge]==0)s.push(p->edge);
            p=p->next;
        }
    }
    if(idx!=G.vNum) return nullptr; //有环
    int *res=new int[G.vNum];
    for(int i=0;i<G.vNum;i++) res[i]=topo[i];
}

这里Graph和Stack的结构自己回去看：

Graph

Stack

竞赛中的写法：

vector<int> topoSort(vector<vector<int> > &G)//G为邻接表
{
    vector<int> topo;
    vector<int> in(G.size(), 0); //记录每个节点的入度
    stack<int> s;
    for(int u=0; u<G.size(); u++)for(auto &v: G[u])in[v]++;
    for(int u=0; u<G.size(); u++)if(in[u]==0)s.push(u);
    while(!s.empty())
    {
      int u=s.top(); s.pop();
      topo.push_back(u);
      for(auto &v: G[u])
      {
        in[v]--;
        if(in[v]==0)s.push(v);
      }
    }
    return topo;
}

当然，对于可交换的顶点，如果要使其按字典序排列，可以使用priority_queue

DFS算法

使用DFS算法实现拓扑排序的思路是：从任意一个节点开始，进行深度优先搜索，当搜索到一个节点时，如果该节点的所有邻接点都已经访问过，则将该节点加入拓扑序列。但这样找到的排序是拓扑序列的逆序，最后要将其反转即可。

struct topoSortDFS
{
    Graph &G;
    int *vis, *topo, idx;
    bool hasCycle;
    topoSortDFS(Graph &Graph): G(Graph)
    {
        vis = new int[G.vNum]{0};  //初始化memset(vis, 0, sizeof(int)*G.vNum);
        topo = new int[G.vNum]{0};
        idx= G.vNum-1;
        hasCycle = false;
    }
    void dfs(int u)
    {
        vis[u]=1; // 标记为正在访问
        for(EdgeNode *p=G.AdjList[u].fiedge; p; p->edge)
        {
            int v=p->edge;
            if(!vis[v]) 
            {
                dfs(v);
                if(hasCycle) return;
            }
            else if(vis[v]==1) {hasCycle=true; return;} //发现环
        }
        topo[idx--]=u;
        vis[u]=2; // 标记访问完成
    }
    void run()
    {
        for(int i=0; i<G.vNum; i++)
        {
            if(!vis[i]) dfs(i);
            if(hasCycle) return;
        }
    }
};

注意，这里的vis数组有三种状态：

0：未访问
1：正在访问
2：访问完成

目的是为了区别正在访问的结点和已经访问的结点，如果dfs过程中vis为1，说明有环。

最小生成树

最小生成树（Minimum Spanning Tree，MST）是在带权无向强连通图中将该图转化为树，并使得该树边权和最小的一颗树。

树的边权和：

$W(T)=\sum_{(u,v)\in T} w(u,v)$

即 $|V|-1$ 条边的权值之和。请区分Huffman编码中的带权路径长度。

最小生成树的性质有：

该树的边数一定是 $|V|-1$
权值和最小
生成的树无根（因为图是无向的）
不唯一（如果有若干边权值相等）
局部最优->全局最优（贪心）

Kruskal 算法

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。算法步骤如下：

将所有边按权值从小到大排序
从权值最小的边开始，依次加入生成树，如果该边加入后不形成环，则加入生成树，否则舍弃该边（并查集DSU）
重复步骤2，直到生成树中有 $|V|-1$ 条边为止

// 边结构
struct Edge
{
    int u,v,w;
    bool operator<(const Edge &other) const{return w < other.w;}
};

// 并查集
struct DSU
{
    vector<int> fa, rank;
    DSU(int n): fa(n), rank(n, 0)
    {
        iota(fa.begin(), fa.end(), 0);
    }

    int find(int x)
    {
        // 路径压缩
        if (fa[x] != x) fa[x] = find(fa[x]);  
        return fa[x];
    }

    bool unite(int x, int y)
    {
        x = find(x), y = find(y);
        if (x == y) return false;  // 已经连通，不能合并

        // 按秩合并（谁树深度小，就挂到谁下面）
        if (rank[x] < rank[y]) fa[x] = y;
        else if (rank[x] > rank[y]) fa[y] = x;
        else
        {
            fa[y] = x;
            rank[x]++; // 两棵一样高，合并后高度 +1
        }
        return true;
    }
};

// LCRS树
struct LCRSNode
{
    int vertex;
    LCRSNode* firstChild;
    LCRSNode* nextSibling;
    LCRSNode(int v): vertex(v), firstChild(nullptr), nextSibling(nullptr) {}
};

/*
最小生成树Kruskal算法
@param G: 图结构
@return: 最小生成树边集
*/
vector<Edge> Kruskal(Graph& G)
{
    vector<Edge> edges;
    // 这里使用了之前写的指针邻接表存图结构
    for (int u=0; u<G.vNum; u++)
    {
        for (EdgeNode* p=G.AdjList[u].fiedge; p; p=p->next)
        {
            int v = p->edge, w = p->weight;
            if (u < v) edges.push_back({u, v, w}); // 防止无向图重复
        }
    }

    // 排序
    // 这里构造struct时重载了<运算符，所以可以直接sort
    sort(edges.begin(), edges.end());

    //Kruskal + DSU
    DSU dsu(G.vNum);
    vector<Edge> mst;
    for (auto& e : edges)
    {
        if (dsu.unite(e.u, e.v))
        {
            mst.push_back(e);
            if (mst.size() == G.vNum - 1) break;
        }
    }
    return mst;
}

/*
将MST边集转化为LCRS树
@param root: 根节点
@param mst: 最小生成树边集
@param n: 图中顶点数
@return: LCRS树根节点指针
*/
LCRSNode* MSTtoLCRS(int root, vector<Edge>& mst, int n)
{
    // MST 边集 → 邻接表
    vector<vector<int>> tree(n);
    for (auto& e : mst) {
        tree[e.u].push_back(e.v);
        tree[e.v].push_back(e.u);
    }

    // 调用递归构造 LCRS
    function<LCRSNode*(int,int)> dfs = [&](int u, int parent) -> LCRSNode*
    {
        LCRSNode* node = new LCRSNode(u);
        LCRSNode* prevChild = nullptr;
        for (int v : tree[u])
        {
            if (v == parent) continue;
            LCRSNode* child = dfs(v, u);
            if (!node->firstChild) node->firstChild = child;
            else prevChild->nextSibling = child;
            prevChild = child;
        }
        return node;
    };

    return dfs(root, -1);
}

竞赛中的写法：

struct Edge
{
    int u, v, w;
    Edge(int u, int v, int w): u(u), v(v), w(w){}
    bool operator<(const Edge &e) const
    {
        return w<e.w;
    }
};

int find(vector<int> &fa, int x)
{
    if(fa[x] != x) fa[x] = find(fa, fa[x]);
    return fa[x];  
}

vector<Edge> kruskal(vector<Edge> &edges, int n)
{
    vector<int> fa(n+1);
    for(int i=1; i<=n; i++) fa[i]=i;
    sort(edges.begin(), edges.end());
    vector<Edge> mst;
    for(auto &e: edges)
    {
        int fu=find(fa, e.u), fv=find(fa, e.v);
        if(fu!=fv)
        {
            fa[fu]=fv;
            mst.push_back(e);
        }
    }
    return mst;
}

Prim 算法

Prim算法与Kruskal算法不同，每次要选择权重距离最小的一个结点，以及用新的边更新其他结点的距离。而Kruskal算法每次选择权值最小的边。

算法具体步骤：

从任意一个点出发，把它加入生成树。
用一个 小根堆 (优先队列) 维护当前生成树到外部点的最小边。
每次取堆顶最小边，如果该点未加入生成树，就把它加入，并更新堆。
直到所有点都加入，累加得到最小生成树的权值。

这里用邻接表和小根堆实现：

struct node
{
    int u,v,w;
};

vector<node> Prim(Graph &G)
{
    vector<node> MST;
    vector<bool> vis(G.vNum, false);
    using tup = tuple<int,int,int>;
    priority_queue<tup, vector<tup>, greater<tup>> pq;
    vis[0] = true;  // 这里假设从顶点0开始
    for (EdgeNode *p = G.AdjList[0].fiedge; p; p = p->next)
        pq.push({p->weight, 0, p->edge});
    while (!pq.empty() && MST.size() < G.vNum - 1)
    {
        auto [w,u,v] = pq.top(); pq.pop();
        if(vis[v]) continue;
        vis[v] = true;
        MST.push_back({u,v,w});
        for (EdgeNode *p = G.AdjList[v].fiedge; p; p = p->next)
            if (!vis[p->edge])
                pq.push({p->weight, v, p->edge});
    }
}

竞赛中的写法：

#include <bits/stdc++.h>
using namespace std;
#define tup tuple<int,int,int>

struct node
{
    int u,v,w;
};

vector<node> Prim(vector<vector<int>>& g, vector<vector<int>> &weight, int st)
{
    vector<node> MST;
    vector<bool> vis(g.size(), false);
    priority_queue<tup, vector<tup>, greater<tup>> pq;
    vis[st] = true;
    for (auto &v: g[st])pq.push({weight[st][v], st, v});
    while (!pq.empty() && (int)MST.size() < (int)g.size() - 1)
    {
        auto [w, u, v] = pq.top(); pq.pop();
        if (vis[v]) continue;
        vis[v] = true;
        MST.push_back({u, v, w});
        for (auto nxt: g[v])
        {
            if (!vis[nxt]) pq.push({weight[v][nxt], v, nxt});
        }
    }
    return MST;
}

图

图的分类

有向图和无向图

简单图和多重图

稠密图与稀疏图

一些定义和关系

基本概念

关系

顶点度公式

最大边数公式

树的性质

欧拉图条件

图的存储结构

邻接矩阵 （Adjacency Matrix）

邻接表 （Adjacency List）

逆向邻接表

十字链表（Orthogonal List）

邻接多重表 (Adjacency Multi-list)

一个例子

图的遍历

深度优先搜索（DFS）

广度优先搜索（BFS）

拓扑排序（Topological Sort）

Kahn算法

DFS算法

最小生成树

Kruskal 算法

Prim 算法

邻接矩阵（Adjacency Matrix）

邻接表（Adjacency List）