图的存储

树可以看作是一张具有$N-1$条边的无向图，也适用于图的存储。
为啥是$N-1$条边？，因为每个叶子节点到其父节点只有一条边，特殊的，根结点没有父节点。

假设一张图中，n是点的数量， m是边的数量：

当 ${m \approx n ^2}$ ,可以认为该图是稠密图;
当 ${m \approx n}$ ,可以认为该图是稀疏图.

邻接矩阵

稠密图，适合用邻接矩阵存储。

const int N = 1e5 + 7;
// const int M ;

// 图的定义(邻接矩阵)
int graph[N][N];
/*
	add操作: u->v这条边的权重为w
*/
inline void add (int u, v, w) {
    graph[u][v] = w;
}

邻接表

std::vector

vector是动态数组

链式前向星

稀疏图，适合用邻接表存储。

链式前向星：用数组模拟邻接表

#include <iostream>
#include <cstring>   // memset()
#include <stdlib.h>  // rand()
#include <algorithm>

using namespace std;

const int N = 1e5 + 7;
const int M = 1e5 + 7;

struct Edge{
    int to;    // 只存储当前边的终点
    int w;     // 权值，对于无权图可以没有w或者w置为1
    int nxt;   // 当前结点在链表中的下一个结点的编号idx
};

// head节点
int head[N];
// head展开的邻接表
Edge edge[M];
int idx;

/*
	add操作: from->to这条边的权重为w
*/
inline void add(int from, int to, int w) {
    edge[idx].to = to;
    edge[idx].w = w;
    edge[idx].nxt = head[from];
    head[from] = idx ++; 
}

int n, m;

int main() {
	// 使用时需要初始化head[]为-1，表示head[]的nxt指针为NULL
    memset(head, -1, sizeof head);
    
    cin >> n >> m;
    
    // add
    while (m --) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        
        add(u, v, w);       
        // add(v, u, w) // 无向图需要额外反着操作一次
    }
    
    // 图的遍历
    for (int t = 1; t <= n; t ++) {
        if (head[t] != -1) printf("%d: ", t);
        for (int i = head[t]; i != -1; i = edge[i].nxt) {
            printf("->%d(%d) ", edge[i].to, edge[i].w);
            // 取j进行后续操作
        	int j = edge[i].to;
        }
        if (head[t] != -1) puts("");
    }
    
    return 0;
}

##图的遍历

图的深度优先遍历

树的重心

图的广度优先遍历

拓扑排序

拓扑排序是对有向无环图(DAG)上的节点进行排序，使得对于每条有向边$u\to v$，$u$都在$v$之前出现。
换句话说，是在不破坏节点先后顺序的前提下，把有向无环图拉成一条链。

拓扑排序最经典的算法是Kahn算法，该算法的思想很简单：
每次从图中拿出当前入度为0的结点放到拓扑序列，并在原图中删除它们，直到图中没有结点。

因为是有向无环图，而删除结点操作不会产生环，所有每时每刻一定存在入度为0的结点，
因此一个有向无环图一定至少存在一个拓扑序列，有向无环图(DAG)也称为拓扑图。

#include <queue>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 7;
const int M = N;

struct Edge{
    int to;
    int w;
    int nxt;
};

Edge edge[N];
int head[N], idx = 1;
int deg[N], seq[N]; // 有向无环图的拓扑排序: 入度deg，拓扑序列seq

int n, m;

inline void add(int from, int to, int w) {
    edge[idx].to = to, edge[idx].w = w, edge[idx].nxt = head[from];
    head[from] = idx ++;
    deg[to] ++;
}

bool top_sort() {
    queue<int> q;
    for (int i = 1; i <= n; i ++) {
        if (deg[i] == 0) q.push(i);
    }
    
    int cnt = 0;
    while (!q.empty()) {
        int t = q.front(); q.pop();
       	seq[++ cnt] = t;
        
        for (int i = head[t]; ~i; i = edge[i].nxt) {
            int j = edge[i].to;
            deg[j] --;
            if (deg[j] == 0) {
                q.push(j);
            }
        }
    }
    
    return cnt == n;
}


int main() {
    memset(head, -1, sizeof head);
    memset(deg, 0, sizeof deg);
    
    cin >> n >> m;
    for (int i = 0; i < m; i ++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u, v, 1);
    }
    
    if (top_sort()) {
        for (int i = 1; i <= n; i ++) {
            printf("%d ", seq[i]);
        }
    }
    else puts("-1");
}

$top\_sort()$返回值为cnt == n，如果图中存在环，那么组成环的节点的入度不可能==0，最终加入A数组中的节点数cnt肯定会小于总节点数n，也就是说拓扑排序是可以用来简单地判环的。

有时会要求输出字典序最小的拓扑序列，这时把queue改成priority_queue即可，复杂度会多一个$\log$ 。

练习eg:

Acwing-848.有向图的拓扑序列

Acwing-3696.构造有向无环图

Acwing-164.可达性统计