网站建设需求说明建设部网站 注册违规

网站建设需求说明,建设部网站 注册违规,邮箱账号做网站用户名好不好,网站建设与推广员岗位职责图论是数据结构与算法的核心模块#xff0c;也是面试高频考点#xff0c;但很多新手会卡在“概念抽象”“代码难写”“逻辑理不清”三个环节。本文避开复杂理论#xff0c;从“用代码实现”的角度出发#xff0c;手把手教你掌握图的两种核心存储结构#xff08;邻接矩阵、…图论是数据结构与算法的核心模块也是面试高频考点但很多新手会卡在“概念抽象”“代码难写”“逻辑理不清”三个环节。本文避开复杂理论从“用代码实现”的角度出发手把手教你掌握图的两种核心存储结构邻接矩阵、邻接表再深入讲解深度优先DFS、广度优先BFS遍历算法全程附可直接运行的C语言代码和清晰的执行逻辑零基础也能跟着敲、跟着懂。一、先搞懂图是什么为什么需要存储结构简单来说图是由“顶点”和“边”组成的数据结构——比如社交网络中每个人是“顶点”朋友关系是“边”地图中城市是“顶点”道路是“边”。但计算机无法直接“理解”顶点和边的关系必须通过特定的结构存储这就有了“邻接矩阵”和“邻接表”两种经典方案邻接矩阵用二维数组存适合顶点少、边多的“稠密图”比如地图中相邻城市邻接表用“顶点数组链表”存适合顶点多、边少的“稀疏图”比如社交网络。先从最直观的邻接矩阵开始学起再对比理解邻接表的优势。二、图的第一种存储结构邻接矩阵Adjacency Matrix2.1 核心逻辑用二维数组映射顶点关系假设图有 n 个顶点用 n×n 的二维数组 matrix 存储matrix[i][j] 权值 表示顶点 i 和顶点 j 之间有边权值是边的“长度”或“权重”matrix[i][j] 无穷大INF 表示顶点 i 和顶点 j 之间无边matrix[i][i] 0 表示顶点自身到自身无边可选。比如一个5顶点的图邻接矩阵长这样 ∞ 表示无边plaintext0 1 2 3 40 0 2 3 ∞ ∞1 2 0 ∞ 1 ∞2 3 ∞ 0 ∞ 43 ∞ 1 ∞ 0 ∞4 ∞ ∞ 4 ∞ 02.2 完整代码实现可直接运行新建 adjacency_matrix.c 文件复制以下代码包含“初始化、加边、打印”核心功能c#include stdio.h#include stdbool.h// 配置参数最大顶点数、无边标识无穷大#define MAX_VERTICES 100#define INF 999999// 邻接矩阵结构体存储顶点和边的关系typedef struct {char vertex[MAX_VERTICES]; // 顶点数组用0/1/2...标识顶点int matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵存边权int vertex_num; // 实际顶点数量} AdjMatrixGraph;// 1. 初始化邻接矩阵void initAdjMatrix(AdjMatrixGraph *graph, int n) {graph-vertex_num n;// 初始化顶点默认用0~n-1标识也可自定义为字母比如Afor (int i 0; i n; i) {graph-vertex[i] 0 i;}// 初始化矩阵无边设为INF自身设为0for (int i 0; i n; i) {for (int j 0; j n; j) {graph-matrix[i][j] (i j) ? 0 : INF;}}}// 2. 添加无向边v1、v2是顶点索引weight是边权void addEdgeMatrix(AdjMatrixGraph *graph, int v1, int v2, int weight) {// 先检查顶点索引是否合法避免越界if (v1 0 || v1 graph-vertex_num || v2 0 || v2 graph-vertex_num) {printf(顶点索引错误添加边失败\n);return;}// 无向图边是双向的所以matrix[v1][v2]和matrix[v2][v1]都要设为weightgraph-matrix[v1][v2] weight;graph-matrix[v2][v1] weight;}// 3. 打印邻接矩阵直观查看图结构void printAdjMatrix(AdjMatrixGraph *graph) {printf(邻接矩阵INF表示无边\n);// 先打印顶点表头方便对应printf( );for (int i 0; i graph-vertex_num; i) {printf(%c , graph-vertex[i]);}printf(\n);// 打印矩阵内容for (int i 0; i graph-vertex_num; i) {printf(%c , graph-vertex[i]);for (int j 0; j graph-vertex_num; j) {if (graph-matrix[i][j] INF) {printf(∞ );} else {printf(%d , graph-matrix[i][j]);}}printf(\n);}}// 主函数测试邻接矩阵int main() {AdjMatrixGraph graph;// 1. 初始化5个顶点的图initAdjMatrix(graph, 5);// 2. 添加无向边顶点0-1边权20-2边权31-3边权12-4边权4addEdgeMatrix(graph, 0, 1, 2);addEdgeMatrix(graph, 0, 2, 3);addEdgeMatrix(graph, 1, 3, 1);addEdgeMatrix(graph, 2, 4, 4);// 3. 打印结果printAdjMatrix(graph);return 0;}2.3 编译运行步骤新手必看1. 环境准备确保已安装MinGWC语言编译器若未安装可参考文末“附录”的MinGW安装教程2. 保存代码用VS Code打开文件按 CtrlS 保存为 adjacency_matrix.c 3. 编译代码打开VS Code终端“终端”→“新建终端”输入命令bashgcc adjacency_matrix.c -o adjacency_matrix4. 运行代码输入命令执行生成的可执行文件bash./adjacency_matrix.exe5. 查看结果终端会输出5×5的邻接矩阵与前文示例一致说明代码运行成功。三、图的第二种存储结构邻接表Adjacency List3.1 核心逻辑用“顶点数组链表”节省空间邻接矩阵的缺点很明显如果顶点多但边少比如1000个顶点只有100条边二维数组会浪费大量空间大部分都是 INF 。邻接表的解决方案是- 顶点数组存储所有顶点每个顶点对应一个“链表头”- 链表每个顶点的链表只存储该顶点的“邻接点”和“边权”无边的顶点不占空间。比如同样是5顶点的图邻接表长这样plaintext0 - 2(3) - 1(2) - NULL1 - 3(1) - 0(2) - NULL2 - 4(4) - 0(3) - NULL3 - 1(1) - NULL4 - 2(4) - NULL3.2 完整代码实现可直接运行新建 adjacency_list.c 文件复制以下代码核心是“边节点结构体顶点结构体邻接表操作”c#include stdio.h#include stdlib.h#include stdbool.h#define MAX_VERTICES 100 // 最大顶点数// 1. 边节点结构体存储邻接点和边权链表的每个节点typedef struct EdgeNode {int adjvex; // 邻接点的索引对应顶点数组的下标int weight; // 边的权值struct EdgeNode *next; // 指向下一个边节点链表指针} EdgeNode;// 2. 顶点结构体存储顶点数据和边链表头指针typedef struct VertexNode {char data; // 顶点标识如0/1EdgeNode *firstedge; // 指向边链表的头指针初始为NULL} VertexNode;// 3. 邻接表结构体顶点数组顶点数量typedef struct {VertexNode adjlist[MAX_VERTICES]; // 顶点数组int vertex_num; // 实际顶点数量int edge_num; // 实际边数量可选用于统计} AdjListGraph;// 4. 初始化邻接表void initAdjList(AdjListGraph *graph, int n) {graph-vertex_num n;graph-edge_num 0;// 初始化每个顶点数据设为0~n-1边链表头指针设为NULLfor (int i 0; i n; i) {graph-adjlist[i].data 0 i;graph-adjlist[i].firstedge NULL;}}// 5. 添加无向边v1、v2是顶点索引weight是边权void addEdgeList(AdjListGraph *graph, int v1, int v2, int weight) {// 检查顶点索引合法性if (v1 0 || v1 graph-vertex_num || v2 0 || v2 graph-vertex_num) {printf(顶点索引错误添加边失败\n);return;}