图论基础

一、图 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

只存一次