网络路由拓扑规划系统

📌 项目概述

本项目模拟一个校园网环境（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)。

🔍 十大功能详解

从拓扑创建到文件持久化，覆盖完整业务流程

创建网络拓扑

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

头插法 · 邻接表

查看邻接矩阵（路由表）

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

二维数组 · 指针

全网巡检路线（DFS）

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

DFS · 递归 · 指针重置

路由环路检测（Kahn）

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

Kahn · 入度数组 · 队列

两设备最优路径（Floyd）

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

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

全网路由表

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

全源最短路径

光纤布线方案（MST）

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

Prim · Kruskal · 并查集

设备详情查询

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

结构体查询

保存拓扑到文件

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

文件IO · fprintf

从文件加载拓扑

用 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

延迟高 · 不推荐

✅ 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 忽略规则