# 🌐 网络路由拓扑规划系统

用 C 语言写的校园网通信路径规划工具。就像地图 App 告诉你哪条路最快一样，这个程序告诉网络数据走哪条路最省时间。

---

## 🏫 我们的校园网长什么样？

一个校园网里有好多台路由器，数据要从你的电脑传到互联网，中间要经过好多站。我们用 **8 台设备、10 条网线** 来模拟：

| 代号 | 名字 | 干什么的？ |
|:---:|:----:|:----------|
| 🔴 **CR** | 核心路由器 | 校园网的总枢纽，连接互联网出口 |
| 🟠 **DR-A** | 汇聚路由器A（教学区） | 管教学楼那片区域的网络流量 |
| 🟠 **DR-B** | 汇聚路由器B（生活区） | 管宿舍楼那片区域的网络流量 |
| 🟢 **AR-T** | 教学楼接入路由器 | 直接连教室里的有线网络 |
| 🟢 **AR-L** | 实验楼接入路由器 | 直接连实验室的网络 |
| 🟢 **AR-D** | 宿舍楼接入路由器 | 直接连宿舍的网络端口 |
| 🔵 **SV** | 服务器集群 | 存着校园网的各种服务（选课、网站等） |
| 🛡️ **FW** | 防火墙 | 保护校园网不被攻击 |

它们之间的连接关系（数字单位：**毫秒**，数字越小说明传得越快）：

```
           FW
           │ 2
           CR
         ╱ │ ╲
       5   │   8
      ╱    │     ╲
   DR-A──12──DR-B
   ╱ ╲         ╱ ╲
 4    3       3    25
╱      ╲    ╱      ╲
AR-L   AR-T       AR-D
  ╲    ╱
   3   2
    ╲ ╱
     SV
```

### 🤔 发现了吗？绕路反而更快！

查 **AR-D（宿舍路由器）→ SV（服务器）**：
- **直走**：AR-D → SV = **25 毫秒**
- **绕路**：AR-D → DR-B → DR-A → AR-T → SV = **3 + 12 + 3 + 2 = 20 毫秒**

😲 **绕路比直走快了 5 毫秒！** 这就是这个程序最大的用处——不是盲选最短的线，而是算出一条最快的路。

---

## 🧩 用到的数据结构知识

### 邻接表（怎么存这些设备和网线？）

每台设备都有一个"邻居清单"，记着它连着谁、延迟多少。

**为什么不用邻接矩阵？**
邻接矩阵像一张点名表，8 台设备要 8×8=64 格，但大部分格子是空的（没直连），浪费空间。  
邻接表只记"有连接"的，省内存。

### 三层结构体

```
CNode （边节点，存邻居是谁、延迟多少、下一个邻居在哪）
   ↑
HNode （设备节点，存设备名、描述、端口数、指向第一个邻居的指针）
   ↑
ALGraph（图结构体，存所有设备数组 + 设备数 + 网线数）
```

CNode 里面的 `next` 指针就像寻宝游戏——每张纸条写着"下一个线索在哪儿"，
顺着指针就能找到全部邻居。

---

## 🔍 10 个功能详细介绍

### 1. 创建网络拓扑 🏗️

输入 8 台设备的名字、描述，以及 10 条网线的连接关系。  
程序用**头插法**把网线信息存到邻接表里。

什么叫头插法？就是新插入的邻居信息总是放在链表最前面——插在"头"上，O(1) 时间复杂度。

### 2. 查看路由表（邻接矩阵）📊

把邻接表转成一张二维表格：

| 举例 | CR | DR-A | DR-B | AR-T | AR-L | AR-D | SV | FW |
|:---:|:---:|:----:|:----:|:----:|:----:|:----:|:--:|:--:|
| **CR** | 0 | 5 | 8 | ∞ | ∞ | ∞ | ∞ | 2 |
| **DR-A** | 5 | 0 | 12 | 3 | 4 | ∞ | ∞ | ∞ |

（∞ 表示两设备之间没有直连网线。自己到自己是 0。）

### 3. 全网巡检路线（DFS 深度优先遍历）🤖

想象一个**扫地机器人**要去检查每台设备，它的策略是：
"走一条路走到头，走不通就回头换一条。"

这样做能保证：**不重复、不遗漏**地走遍所有设备。

**DFS 递归的关键**：因为用了全局指针来遍历邻居链表，递归回来之后指针位置变了，
所以必须把指针重置到链表头，否则后面的邻居会被跳过。  
（就像你走迷宫退回到岔路口，得重新看一眼有哪些路，不能盯着死胡同那面墙。）

程序输出一条巡检路线：
```
CR → FW → DR-A → AR-L → SV → AR-T → DR-B → AR-D
```

### 4. 路由环路检测（Kahn 拓扑排序）🔄

如果网络中有"环"，数据包就会在里面**转圈圈永远出不去**。

Kahn 算法就像**剥洋葱**：
1. 算每个设备的"入度"（有几条线指向它）
2. 把入度为 0 的剥掉（相当于从网络里移除）
3. 被剥掉的设备，它的邻居入度减 1
4. 重复 2-3，如果还有设备剥不掉——那些就是"环"！

正常网络的**导游路线图**（有向图）不应该有环，这个功能就是帮管理员**检查配置错误**。

### 5. 两设备最优路径查询（Floyd 算法）🚀

输入任意两台设备的名字，程序告诉你**走哪条路最快**。

**Floyd-Warshall 算法的核心思想**：
> 把每个设备都当中转站试试——经过它会不会更快？如果会，就更新记录。

就像你去朋友家：直接走 30 分钟，但是先经过便利店买瓶水再去只要 25 分钟？那就绕一下。Floyd 会把所有设备都试一遍，最终得到全局最优解。

**三重循环为什么 k 必须在外层？**  
k 代表"开放第几个中转站"——先允许经过 0 号中转，再允许经过 0、1 号中转……逐步放开。  
如果 k 放在最内层，就会还没算出短路径就拿去用，结果算不对。

查 AR-D → SV 的结果：
```
AR-D → DR-B → DR-A → AR-T → SV
总延迟：3 + 12 + 3 + 2 = 20 毫秒
```

### 6. 全网路由表（Floyd 全源展示）📋

展示所有设备之间的最短延迟，列成一张大表：

```
           CR  DR-A DR-B AR-T AR-L AR-D  SV  FW
    CR     0    5    8    8    9   11   10   2
   DR-A    5    0   12    3    4   15    7   7
   DR-B    8   12    0   15   16    3   18  10
   AR-T    8    3   15    0    7   18    2  10
   AR-L    9    4   16    7    0   19    3  11
   AR-D   11   15    3   18   19    0   20  13
     SV   10    7   18    2    3   20    0  12
     FW    2    7   10   10   11   13   12   0
```

横着看：CR 到 AR-T 最快是 8 毫秒，到 SV 是 10 毫秒。

### 7. 光纤布线方案（Prim / Kruskal）🔧

学校要重新铺光纤，怎么用**最少的总网线长度**连通所有设备？

**最小生成树（MST）** 就解决这个问题：8 台设备至少需要 7 条线才能全部连通，MST 找到这 7 条线里总长度最少的方案。

**Prim 算法**：从一台设备开始，每次找一条"离已连接集合最近"的线接上。  
→ 就像**盖房子，先盖一间，每次在旁边加最近的一间。**

**Kruskal 算法**：把所有网线按延迟排序，从最短的开始接，会形成环就跳过。  
→ 就像**拼积木，从最好拼的开始，不对就换一块。**

两种算法算出的总延迟都是 **26 毫秒**，选中的 7 条线：

```
CR -- FW (2)    DR-A -- AR-T (3)    DR-A -- AR-L (4)
DR-B -- AR-D (3)    AR-L -- SV (3)    CR -- DR-A (5)    CR -- DR-B (8)
```

### 8. 设备详情查询 🔍

输入设备代号，就能看到：
- 描述（这台设备是干什么的）
- 端口数
- 备注信息（比如"24h 运行"）
- 所有邻居设备及延迟

### 9. 保存拓扑到文件 💾

把网络地图存到文本文件，格式很简单：

```
8 10
CR 校园网核心路由器，连接互联网出口 4 24h运行
DR-A 教学区汇聚路由器，承载教学网络流量 4 24h运行
...
CR FW 2
CR DR-B 8
...
```

第 1 行是设备数和网线数，接着 n 行是设备信息，再 m 行是连接关系。

### 10. 从文件加载拓扑 📂

读取之前保存的文件，恢复网络地图。加载后需要重新选 2 来生成路由表。

---

## 🧠 算法一句话总结

| 算法 | 一句话 | 用在哪儿 |
|:-----|:-------|:---------|
| **DFS** | 一条路走到黑，走不通回头 | 巡检所有设备 |
| **Kahn** | 剥洋葱，剥不完就是有环 | 检测路由环路 |
| **Floyd** | 每个设备当中转站试试，看会不会更快 | 最优路径查询 |
| **Prim** | 从一台开始，每次加"最近"的那台 | 光纤布线 |
| **Kruskal** | 网线按长短排序，从最短的接，会成环就跳过 | 光纤布线 |

---

## 🎬 推荐演示流程

```
选 1 → 创建拓扑图
选 2 → 查看路由表
选 5 → 查 AR-D 到 SV（会发现绕路更快！）
选 3 → DFS 巡检路线
选 4 → 环路检测
选 7 → 光纤最省方案（Prim 和 Kruskal 对比看）
选 8 → 查看某台设备详情
选 9 → 保存到文件
选 0 → 退出，再打开程序
选 10 → 从文件加载，接着用
```

---

## 💻 用了哪些 C 语言知识？

| 知识点 | 用在哪？ |
|:-------|:---------|
| 结构体（struct） | 定义设备、链路、图 |
| 指针（*、->） | 链表操作、动态内存 |
| 链表（头插法） | 邻接表存储 |
| 递归 | DFS、Floyd 路径输出 |
| 二维数组 | 邻接矩阵、Floyd 矩阵 |
| 文件操作 | 保存/加载拓扑 |
| malloc / free | 创建节点、释放内存 |
| #ifndef 保护 | 防止头文件重复包含 |

---

## 📁 项目文件

```
网络路由拓扑规划系统/
├── global.h            ← 数据结构定义（CNode/HNode/ALGraph/Edge）
├── main.c              ← 主程序 + 菜单循环 + 三层输入校验
├── menu.c              ← 菜单显示
├── graph.c             ← 建图、打印邻接矩阵、保存、加载
├── travels.c           ← 所有算法：DFS / Kahn / Floyd / Prim / Kruskal / 设备详情
├── README.md           ← 本文件
└── network_topology.txt  ← 示例数据文件
```

---

## ✨ 总结

这个程序把一个真实的网络问题，用 C 语言的**数据结构**变成电脑能算的东西：

1. **邻接表**存地图 → 省内存，好遍历
2. **DFS**巡检 → 不重复不遗漏走遍所有设备
3. **Kahn**检测环路 → 防止数据包绕晕
4. **Floyd**找最优路径 → 所有中转站试一遍，找到最快的
5. **Prim / Kruskal**找最省布线 → 用最少网线连通所有设备
6. **文件 IO**持久化 → 存盘下次接着用

这就是数据结构的魅力——让电脑替人类做复杂的计算，而我们只需要告诉它"怎么存"和"怎么算"。
