拓扑排序和无权最短路径

一、拓扑排序 Topological Sort

1. 前提条件

拓扑排序只用于：

有向无环图 DAG

也就是：有方向，不能有环

典型场景：

课程先修关系
任务依赖关系
编译依赖

例如：

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

表示：

必须先做 0
才能做 1 和 2
最后才能做 3

2. 核心概念：入度

入度：有多少条边指向这个点

如果一个点入度为 0：

说明没有前置条件
可以先处理

拓扑排序核心：

1. 把所有入度为 0 的点入队
2. 每次弹出一个点
3. 删除它连出去的边
4. 被影响的点入度减 1
5. 如果某个点入度变成 0，入队
6. 例子流程

图：

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

入度：

0: 0
1: 1
2: 1
3: 2

先入队：0

弹出 0：

结果：[0]

删除 0->1，0->2：

1 入度变 0
2 入度变 0

入队：1, 2

弹出 1：结果：[0,1]

删除 1->3： 3 入度从 2 变 1

弹出 2： 结果：[0,1,2]

删除 2->3： 3 入度从 1 变 0

入队 3。

最后：[0,1,2,3]

这就是一种拓扑序。

4. C 代码模板：邻接表 + 队列

#include <stdlib.h>

#define MAXN 1000

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

struct EdgeNode* adj[MAXN];
int indegree[MAXN];
//indegree就是表示入度的那个数组
void initGraph(int n)
{
for(int i = 0; i < n; i++)
{
adj[i] = NULL;
indegree[i] = 0;
}
}

void addEdge(int u, int v)
{
struct EdgeNode* node =
malloc(sizeof(struct EdgeNode));

node->to = v;
node->next = adj[u];
adj[u] = node;

indegree[v]++;

}

拓扑排序：

int topologicalSort(int n, int result[])
{
int queue[MAXN];
int front = 0;
int rear = 0;
//入度为0的先入队
for(int i = 0; i < n; i++)
{
if(indegree[i] == 0)
{
queue[rear++] = i;
}
}

int count = 0;

while(front < rear)
{
    int u = queue[front++];

    result[count++] = u;

    struct EdgeNode* cur = adj[u];
//选中入队元素之后出队
    while(cur != NULL)
    {
        int v = cur->to;

        indegree[v]--;
//出队之后对应连接的边入度减-1，如果为0那就继续入队，不为0就继续遍历邻接表的下一个元素，如果有入度为0就入队，直到遍历完这个元素的邻接表之后到下一个元素
        if(indegree[v] == 0)
        {
            queue[rear++] = v;
        }

        cur = cur->next;
    }
}

return count == n;

}

返回值：

1：拓扑排序成功，没有环
0：失败，说明有环

5. 为什么能判断有环？

如果有环：0 -> 1 -> 2 -> 0

每个点入度都不是 0。

队列一开始可能为空。

没有点能被处理。

最后：count < n

说明还有点没处理。

所以：图里有环

6.拓扑排序

前提：
有向无环图 DAG

核心：
入度

步骤：
1. 统计每个点入度
2. 入度为 0 的点入队
3. 出队一个点，加入结果
4. 删除它的出边
5. 邻接点入度减 1
6. 新的入度为 0 的点入队

判断有环：
如果最终处理点数 < n
说明有环

复杂度：
O(n + m)

二、无权最短路径 BFS

1. 前提条件

无权图：每条边的代价都一样

比如：走一条边，距离 +1

这种情况下，最短路用：BFS

不用 Dijkstra。

2. 核心概念

BFS 是一层一层扩展。

从起点 s 出发：

第 0 层：s
第 1 层：s 一步能到的点
第 2 层：两步能到的点
第 3 层：三步能到的点

第一次到达某个点时，就是最短距离。

3. 例子

图：

0 - 1 - 3
| |
2 - 4

从 0 出发。

初始：dist[0] = 0

0 的邻居：1, 2

所以：

dist[1] = 1
dist[2] = 1

再从 1 出发：3, 4

所以：

dist[3] = 2
dist[4] = 2

结果：0 到 3 的最短距离 = 2

4. BFS 代码模板：邻接表
   #include <stdlib.h>

#define MAXN 1000

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

struct EdgeNode* adj[MAXN];

void initGraph(int n)
{
for(int i = 0; i < n; i++)
{
adj[i] = NULL;
}
}

void addUndirectedEdge(int u, int v)
{
struct EdgeNode* node1 =
malloc(sizeof(struct EdgeNode));

node1->to = v;
node1->next = adj[u];
adj[u] = node1;

struct EdgeNode* node2 =
    malloc(sizeof(struct EdgeNode));

node2->to = u;
node2->next = adj[v];
adj[v] = node2;

}
//因为是无权路径，所以需要malloc两个node之后互相建立路径

BFS 最短路：

void bfsShortestPath(int n, int start, int dist[])
{
int queue[MAXN];
int front = 0;
int rear = 0;

for(int i = 0; i < n; i++)
{
    dist[i] = -1;
}

//先初始化都为-1
dist[start] = 0;
queue[rear++] = start;

while(front < rear)
{
    int u = queue[front++];

    struct EdgeNode* cur = adj[u];

    while(cur != NULL)
    {
        int v = cur->to;

//从start标定的开始先入队，之后看邻接表所指向的边，然后改变其dist之后再入队，当然首先还要检查完start本身其他相邻的边，之后再一次查看第二次所指向的其他相邻边
//比如说dist[0]=-1,之后定义为0，之后给了dist[1]变成1，之后dist[3]原本是-1，但是变成了1+1=2，但是dist[0]已经变了，所以有环也不会检查，最后return出来dist所需数的值就是要的答案
if(dist[v] == -1)
{
dist[v] = dist[u] + 1;
queue[rear++] = v;
}

        cur = cur->next;
    }
}

}
5. 为什么 dist[v] == -1 才更新？

dist[v] == -1 表示：v 还没访问过

BFS 第一次访问到 v 时，一定是最短距离。

所以：dist[v] = dist[u] + 1;

之后再遇到 v，不用更新。

6. 无权最短路笔记
   无权最短路

前提：
每条边权值相同

算法：
BFS

核心：
一层一层扩展

dist[start] = 0

如果从 u 到 v：
dist[v] = dist[u] + 1

访问过的点不再更新

原因：
BFS 第一次到达某点
就是最短路径

复杂度：
O(n + m)

三、拓扑排序 vs BFS 最短路
拓扑排序：

用队列
处理入度为 0 的点
解决有向依赖问题

---

BFS最短路：

用队列
一层一层扩展
解决无权最短距离问题

一句话：

拓扑排序的队列装“当前没有前置条件的点”；
BFS 的队列装“当前这一层能扩展出去的点”。