一、图 Graph 基础

1. 前提条件

之前学的树：

一个根
父子关系
没有环

图比树更一般：

点和点之间可以任意连接
可以有方向
可以有权值
可以有环

例如：

A —— B
|    |
C —— D

这里：A、B、C、D 是顶点
线是边

2. 核心概念

图由两部分组成：G = (V, E)

其中：

V：顶点集合
E：边集合

比如：

V = {A, B, C, D}

E = {(A,B), (A,C), (B,D), (C,D)}

二、有向图和无向图

1. 无向图

边没有方向。

A —— B

表示：

A 可以到 B
B 也可以到 A

2. 有向图

边有方向。

A -> B

表示：

A 可以到 B
但 B 不一定能到 A

比如关注关系、任务依赖关系。

三、带权图

如果边上有数值，就叫带权图。

A --5-- B

这里：5 是权值

可以表示：

距离
时间
费用
代价

最短路径算法就是处理这种图。

四、度、入度、出度

1. 无向图的度

一个点连了几条边，度就是几。

A —— B
|
C

A 连着 B 和 C。

所以：A 的度 = 2

2. 有向图的入度

指向这个点的边数。

A -> C
B -> C

C 的入度：2

3. 有向图的出度

从这个点出去的边数。

A -> B
A -> C

A 的出度：2

五、图的存储方式

最常用两种：邻接矩阵和邻接表

六、邻接矩阵

1. 前提条件

邻接矩阵用二维数组存图。

如果有 n 个点，就开：

int graph[n][n];

含义：graph[i][j] 表示 i 到 j 是否有边

2. 无权图

如果没有权值：

有边：1
无边：0

例如：

0 —— 1
0 —— 2
1 —— 2

矩阵：

    0 1 2
0   0 1 1
1   1 0 1
2   1 1 0

因为是无向图，所以矩阵关于主对角线对称。

3. 有向图

例如：

0 -> 1
0 -> 2
2 -> 1

矩阵：

    0 1 2
0   0 1 1
1   0 0 0
2   0 1 0

注意：

graph[0][1] = 1

不代表

graph[1][0] = 1

4. 带权图

如果有权值：

有边：权值
无边：INF

例如：

0 --5-- 1
0 --2-- 2

可以写：

graph[0][1] = 5
graph[1][0] = 5

graph[0][2] = 2
graph[2][0] = 2

无边用：

#define INF 1000000000

5. 邻接矩阵代码
#define MAXN 100
#define INF 1000000000

int graph[MAXN][MAXN];

void initGraph(int n)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i == j)
            {
                graph[i][j] = 0;
            }
            else
            {
                graph[i][j] = INF;
            }
        }
    }
}

无向带权边：

void addUndirectedEdge(int u, int v, int w)
{
    graph[u][v] = w;
    graph[v][u] = w;
}

有向带权边：

void addDirectedEdge(int u, int v, int w)
{
    graph[u][v] = w;
}

七、邻接表
1. 前提条件

邻接表是：数组 + 链表

每个点开一条链表，存它能到哪些点。

例如：

0 -> 1
0 -> 2
1 -> 2

邻接表：

0: 1 -> 2
1: 2
2:

2. 为什么邻接表常用？

如果点很多，边很少，邻接矩阵很浪费。

比如：

1000 个点
只有 2000 条边

邻接矩阵要：1000 × 1000 = 1000000 个位置

邻接表只存真实存在的边。

所以：

边少用邻接表
边多用邻接矩阵

八、邻接表 C 代码

1. 结构体
#include <stdlib.h>

#define MAXN 100

struct EdgeNode {
    int to;
    int weight;
    struct EdgeNode* next;
};

struct EdgeNode* adj[MAXN];

含义：

adj[i] 是 i 号点的边链表头指针

to 表示这条边到哪个点
weight 表示边权
next 指向下一条边

2. 初始化
void initAdjList(int n)
{
    for(int i = 0; i < n; i++)
    {
        adj[i] = NULL;
    }
}

3. 加有向边
void addDirectedEdge(int u, int v, int w)
{
    struct EdgeNode* node =
        malloc(sizeof(struct EdgeNode));

    node->to = v;
    node->weight = w;

    node->next = adj[u];
    adj[u] = node;
}

意思：从 u 出发，能到 v，权值是 w

用的是链表中的头插法。

4. 加无向边

无向边：u —— v

等价于两条有向边：

u -> v
v -> u

代码：

void addUndirectedEdge(int u, int v, int w)
{
    addDirectedEdge(u, v, w);
    addDirectedEdge(v, u, w);
}

九、遍历邻接表

如果要看某个点 u 能到哪些点：

void printNeighbors(int u)
{
    struct EdgeNode* cur = adj[u];

    while(cur != NULL)
    {
        printf("%d %d\n", cur->to, cur->weight);

        cur = cur->next;
    }
}

十、区别

邻接矩阵：
优点：
    判断 u 到 v 有没有边很快
    O(1)

缺点：
    空间大
    O(n²)

适合：
    点少、边多的稠密图

--------------------------------

邻接表：

优点：
    省空间
    O(n + m)

缺点：
    判断 u 到 v 有没有边要遍历链表

适合：
    点多、边少的稀疏图

其中：

n = 点数
m = 边数

十一、总结

图 Graph

组成：G = (V, E)

V：顶点
E：边

--------------------------------

图的类型：

无向图：
    边没有方向

有向图：
    边有方向

带权图：
    边有权值

--------------------------------

度：

无向图：
    度 = 连着几条边

有向图：
    入度 = 指向它的边数
    出度 = 从它出去的边数

--------------------------------

存储方式：

1. 邻接矩阵

graph[i][j]

表示 i 到 j 是否有边或边权

空间：
    O(n²)

适合：
    稠密图

--------------------------------

2. 邻接表

adj[i]

表示 i 能到的所有点

空间：
    O(n + m)

适合：
    稀疏图

--------------------------------

无向边：

u - v

存两次：

u -> v
v -> u

--------------------------------

有向边：

u -> v

只存一次