📌 项目概述

本项目模拟一个校园网环境（8 台设备、10 条链路），用 C 语言实现了一个网络路由拓扑规划系统。 用户可以创建网络拓扑、查看路由表、检测环路、查询最优路径、计算光纤布线方案等。

核心思想：把网络设备看作图的顶点，把网线看作图的边，用邻接表存储拓扑结构，用图算法解决路径规划问题。

💡 亮点：Floyd 算法发现"绕路更快"——AR-D → SV 直连需要 25ms，绕路只需 20ms
🏗️ 网络拓扑架构
三层网络模型：核心层 → 汇聚层 → 接入层

层级 | 设备 | 说明
--- | --- | ---
🔴 核心层 | CR | 核心路由器，校园网总枢纽，连接互联网出口
🟠 汇聚层 | DR-A | 教学区汇聚路由器，承载教学网络流量
DR-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

数字单位：毫秒（ms），数字越小表示传输越快

📦 数据结构设计
为什么用邻接表？三层结构体如何协作？

选型理由：8 台设备如果用邻接矩阵需要 64 格，大部分是 ∞（无直连），浪费空间。 邻接表只存储实际存在的连接，空间效率高，遍历邻居时只需顺着链表走。

结构体 | 作用 | 关键字段
--- | --- | ---
`CNode` | 边节点 | `index` 邻居下标 · `delay` 延迟 · `next` 指向下一邻居
`HNode` | 设备节点 | `name[20]` 设备名 · `desc[100]` 描述 · `first` 首邻居指针
`ALGraph` | 图结构 | `devices[]` 设备数组 · `deviceNum` · `linkNum`

🔗 CNode 的 `next` 指针就像寻宝游戏——每张纸条写着"下一个线索在哪儿"，顺着指针就能找到全部邻居。 建图时使用头插法（新节点插在链表头部），时间复杂度 O(1)。

🔍 十大功能详解
从拓扑创建到文件持久化，覆盖完整业务流程
1

### 创建网络拓扑

输入 8 台设备信息 + 10 条链路关系，用头插法存入邻接表，O(1) 插入。

头插法 · 邻接表
2

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

将邻接表转为二维表格，∞ 表示无直连。用 `parray` 指针数组动态分配存储。

二维数组 · 指针
3

### 全网巡检路线（DFS）

深度优先遍历所有设备。"一条路走到黑，走不通回头。" 递归返回后需重置全局指针。

DFS · 递归 · 指针重置
4

### 路由环路检测（Kahn）

"剥洋葱"——剥掉入度为 0 的顶点。如果还有剩余说明有环，数据包会绕晕出不去。

Kahn · 入度数组 · 队列
5

### 两设备最优路径（Floyd）

输入任意两台设备名，输出最短路径及总延迟。经典 k-i-j 三重循环，k 在外层是关键。

Floyd · 动态规划 · O(n³)
6

### 全网路由表

展示所有设备之间的最短延迟，列成 8×8 大表。Floyd 全源信息一次算完。

全源最短路径
7

### 光纤布线方案（MST）

用最少总网线连通所有设备。Prim（加点法）+ Kruskal（加边法）两种算法对照验证。

Prim · Kruskal · 并查集
8

### 设备详情查询

输入设备代号，显示描述、端口数、备注、所有邻居及延迟。数据均来自结构体。

结构体查询
9

### 保存拓扑到文件

用 `fprintf` 写入文本文件，利用 `i < pNode->index` 避免无向边重复写入。

文件IO · fprintf
10

### 从文件加载拓扑

用 `fscanf` 读取文件恢复网络地图。加载前自动释放旧内存（`freeGraph`）。

文件IO · fscanf · 内存管理
🧠 核心算法总结
每种算法一句话 + 时间复杂度 + 应用场景

算法 | 一句话 | 复杂度 | 在项目中的应用
--- | --- | --- | ---
DFS | 一条路走到黑，走不通回头 | O(n+e) | 全网巡检路线——不重复、不遗漏走遍所有设备
Kahn | 剥洋葱，剥不完就是有环 | O(n+e) | 路由环路检测——防止数据包在网络中死循环
Floyd | 每个设备当中转站试试，看会不会更快 | O(n³) | 最优路径查询 + 全网路由表（k 放外层是关键）
Prim | 从一台开始，每次加离已建网络最近的点 | O(n²) | 光纤布线方案——盖房子，每次加最近一间
Kruskal | 网线按长短排序，从最短的接，会成环就跳过 | O(e log e) | 光纤布线方案——拼积木，从最好拼的开始

⭐ 亮点演示："绕路反而更快"
Floyd 算法发现反直觉的最优路径
🚫 直觉路线（直连）
AR-D → SV
25 ms
延迟高 · 不推荐
VS
✅ Floyd 算出的最优路线
AR-D → DR-B → DR-A → AR-T → SV
20 ms
🎯 节省 5ms（快 20%）

💡 为什么绕路更快？ 直连虽然"看起来近"，但 AR-D ↔ SV 的实际链路延迟高达 25ms。绕路经 DR-B → DR-A → AR-T 虽然多走 3 跳，但每跳延迟都很低（3+12+3+2 = 20ms），整体反而更快。

🔑 这就是算法的价值——不给直觉做决定，让数据说话。

🖥️ 运行效果展示
关键功能输出截图 / 数据展示

#### 📊 全网路由表（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

#### 🤖 DFS 巡检路线

CR → FW → DR-A → AR-L → SV → AR-T → DR-B → AR-D
8 台设备全部巡检，无重复无遗漏

#### 🔧 MST 最小生成树

CR ─ FW (2ms) DR-A ─ AR-T (3ms)
DR-A ─ AR-L (4ms) DR-B ─ AR-D (3ms)
AR-L ─ SV (3ms) CR ─ DR-A (5ms) CR ─ DR-B (8ms)
总延迟：26ms · 7 条边连通 8 台设备
💻 用到的 C 语言知识点
从结构体到文件操作，覆盖课程核心内容

#### 📦 结构体（struct）

定义设备、链路、图的数据结构

#### 📎 指针（* / ->）

链表操作、动态内存分配、函数传参

#### ⛓️ 链表（头插法）

邻接表存储，新节点插在头部 O(1)

#### 🔄 递归

DFS 遍历、Floyd 路径递归打印

#### 📊 二维数组

邻接矩阵、Floyd 最短路径矩阵

#### 💾 文件操作

fprintf / fscanf 保存与加载拓扑

#### 🧹 malloc / free

创建图节点、释放图内存

#### 🛡️ #ifndef 保护

防止头文件重复包含

#### 🔗 extern 声明

全局变量跨文件共享（parray, path）

#### ✅ scanf 返回值校验

3 层输入防护：格式 → 范围 → 业务依赖

📁 项目文件结构
6 个核心文件，模块化设计，职责清晰
📁 网络路由拓扑规划系统/
├── 📄 global.h —— 数据结构定义（CNode / HNode / ALGraph / Edge）
├── 📄 main.c —— 主程序 + 菜单循环 + 3 层输入校验
├── 📄 menu.c —— 菜单界面（画框显示 11 个选项）
├── 📄 graph.c —— 建图、打印邻接矩阵、保存 / 加载文件
├── 📄 travels.c —— 所有算法实现（DFS / Kahn / Floyd / Prim / Kruskal）
├── 📄 README.md —— 项目说明文档
├── 📄 network_topology.txt —— 示例数据文件
└── 📄 .gitignore —— Git 忽略规则

🎬 演示视频

系统功能运行演示

您的浏览器不支持视频播放，请更换浏览器后重试。

📌 视频较大时请耐心等待加载，建议在 Wi-Fi 下观看