数据结构实验十.doc

一、实验目的 1.使学生熟悉最短路径算法实现。 2.掌握带权图的存储结构和处理方法。 二、实验环境 1.硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； 2.软件：DOS或Windows操作系统+Turbo c; 三、实验要求 1.能够独立完成带权图的存储和最短路径的生成。 四、实验内容 1.现在假设我国铁路交通图如下（权值表示距离），请用合适的存储结构将下图存储到 计算机中方便进行处理。 2.现在我想以最小的代价从徐州出发到达其他目的地，请用Dijkstra算法实现我的要求 的路径。 五、代码如下 #include <stdio.h> #include <malloc.h> typedef struct{ int *vexs; int **arcs; int vexnum; }ylx_graph ; typedef struct{ int adjvex; int lowcost; }ylx_markedg ; ylx_graph *ylx_initgraph (){ int i,j;ylx_graph *g; g=(ylx_graph *)malloc(sizeof 实验主题涉及数据结构中的图论知识，特别是最短路径算法的实现，以及带权图的存储结构。在本次实验中，学生需要理解并应用Dijkstra算法来解决实际问题，即在给定的中国铁路交通图中找出从徐州出发到其他城市的最短路径。 一、最短路径算法——Dijkstra算法 Dijkstra算法是一种单源最短路径算法，用于寻找图中从一个特定源节点到其他所有节点的最短路径。它通过逐步扩展当前已知最短路径来更新待计算节点的距离。算法的关键步骤包括： 1. 初始化：设置源节点的距离为0，其他所有节点的距离为无穷大。 2. 选择当前未访问且距离最小的节点，并标记为已访问。 3. 更新该节点的所有未访问邻接节点的距离，如果新路径比旧路径短，则更新其距离。 4. 重复步骤2和3，直到所有节点都被访问过。 二、带权图的存储结构 在实验中，采用了邻接矩阵作为图的存储结构。邻接矩阵是一个二维数组，其中的元素表示图中节点之间的边及其权重。在C语言实现中，`ylx_graph` 结构体定义了图的基本属性，包括顶点数组`vexs`，邻接矩阵`arcs`，以及顶点数量`vexnum`。邻接矩阵`arcs`是二维指针数组，用于存储图的边和权重信息。 三、实验代码分析 1. `ylx_initgraph` 函数初始化了一个空的图结构，分配内存并初始化邻接矩阵为0。 2. `ylx_creategraph` 函数填充了具体的图信息，即城市间的距离。这里使用索引代替城市名称，0表示徐州，依次类推。矩阵对角线以下的元素赋值为非零值，表示两个城市之间有连接，值代表距离。 3. `ylx_printgraph` 函数用于打印图的邻接矩阵，方便检查和调试。 4. `ylx_selectnearvex` 函数似乎是用于辅助Dijkstra算法的选择最近顶点操作，但提供的代码片段不完整。 为了实现Dijkstra算法，还需要编写一个核心函数，遍历未访问的节点并更新距离，同时维护一个优先队列（如最小堆）来选择距离最小的节点。根据每次迭代的结果，可以追踪回溯出最短路径。 总结来说，这次实验旨在让学生深入理解Dijkstra算法的原理，熟悉邻接矩阵的使用，以及如何在实际问题中应用这些理论知识。通过编写和运行代码，学生不仅能巩固理论学习，还能提升问题解决和编程技能。