数据结构小学期-算法演示程序实验报告

石家庄铁道大学实习报告

实习报告

实验名称：数据结构基本算法演示程序 日期：2017年7月1 日 姓名：于博 学号：20153236 班级：信1501-2 指导教师：陈娜

1．实验题目

1) Prim 算法 输入：无向图（顶点序列，边序列）

功能要求：输出最小生成树的各组成边及最小生成树的权值 2) Kruskal 算法 输入：无向图（顶点序列，边序列） 功能要求：输出最小生成树的各组成边及最小生成树的权值 3) Floyd 算法 输入：有向图（顶点序列，有向边序列） 功能要求：输出各顶点对间最短路径和路径长度 4) Dijkstra 算法

输入：有向图（顶点序列，有向边序列），起始顶点

功能要求：输出起始顶点到其它各顶点的最短路径和路径长度

2．需求分析

本演示程序用C++编写，完成四个算法的实现, Prim 算法，Kruskal 算法，Floyd 算法，Dijkstra 算法

① 输入的形式和输入值的范围： 整数，菜单项是1至5，其他输入根据图的实际情况。 ② 输出的形式：输出最小生成树，树的各组成边，所有路径及源点到其他点的所有最短路径。

③ 程序所能达到的功能：四个算法Prim 算法，Kruskal 算法，Floyd 算法，Dijkstra 算法的实现。

④ 测试数据：

A． 输入3个点，3条边。

B． 输入1 3 50 1 2 20 2 3 10三组点及权值。

3．概要设计

1) 为了实现上述程序功能，需要定义树、线性表的抽象数据类型： ADT Tree{

数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0} 数据关系：R={|ai,ai+1 ∈D} ADT LinkList{

数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0} 数据关系：R={|ai,ai+1 ∈D} 基本操作： a) Prim算法 ok(Tree &t,int k)

初始条件：树结构已存在

操作结果：作为判断函数的条件

1 / 22

石家庄铁道大学实习报告

judge(Tree &t)

初始条件：树结构已存在

操作结果：判断树是否包含所有图的结点 show_prim()

初始条件：树结构已存在，prim算法运行成功 操作结果：展示prim算法,输出最小生成树 b) Kruskal 算法 Find(int x)

初始条件：图已存在 操作结果：查寻父节点 Union(int x,int y) 初始条件：图已存在 操作结果：合并结点 bool Com(Node x,Node y) 初始条件：图已存在 操作结果：判断结点权值 show_kruskal()

初始条件：图已存在，kruskal算法运行成功 操作结果：展示kruskal算法，输出各组成边 c) Floyd 算法

F_Creategraph(F_MGraph *F_MGraph) 操作结果：创建图

Floyd(F_MGraph *F_MGraph, int **iArrPath) 初始条件：图已存在

操作结果：运行弗洛伊德算法

PrintResult(F_MGraph *F_MGraph, int **iArrPath) 初始条件：图已存在 操作结果：打印图的信息 show_floyd()

初始条件：图已存在，弗洛伊德算法运行成功 操作结果：展示弗洛伊德算法 d) Dijkstra 算法

createGraph(HeadNode *G, int nodeNum, int arcNum) 操作结果：创建图

printGraph(HeadNode *G, int nodeNum) 初始条件：图已存在 操作结果：打印图

getWeight(HeadNode *G, int begin, int end) 初始条件：图已存在

操作结果：得到出发点到终点权重

Dijkstra(HeadNode *G, int nodeNum, int begin) 初始条件：图已存在，出发点已知 操作结果：运行迪杰斯特拉算法 printPath(HeadNode *G, int end)

2 / 22

石家庄铁道大学实习报告

初始条件：图已存，迪杰斯特拉算法运行成功 操作结果：打印路径 show_Dijkstra()

初始条件：图已存，迪杰斯特拉算法运行成功 操作结果：展示迪杰斯特拉算法 menu()

操作结果：在屏幕上显示操作菜单 2) 本程序包含 17个函数： 主函数 main() 菜单函数menu() Prim算法 判断函数ok()

判断树是否包含所有图的结点judge() 展示prim算法函数show_prim() Kruskal算法

查寻父节点函数Find() 合并结点函数Union()

判断节点权值函数bool Com()

展示kruskal算法函数show_kruskal() Floyd算法

弗洛伊德创建图F_Creategraph() 弗洛伊德算法函数Floyd() 打印图信息函数PrintResult() 展示弗洛伊德函数show_floyd() Dijistra算法

创建图createGraph()

迪杰斯特拉算法函数Dijkstra () 打印路径函数printPath()

展示迪杰斯特拉函数show_Dijkstra() 各函数间关系如下：

3 / 22

石家庄铁道大学实习报告

4．详细设计

//------------------------------------------Prim算法--------------------------------------------------// //判断函数--是否树包含图的所有结点 void judge(Tree &t){

for(int i=1;i

for(int k=1;k<=t.v1;k++){ if(t.a[m][k]

biaoji1=t.a[m][k]; biaoji2=m; biaoji3=k; } } } }

t.v[i]=biaoji3; t.e[2*i-1]=biaoji2; t.e[2*i]=biaoji3; } }

//调用prim算法相关所有代码 void show_prim(){

cout<<\请输入图的点数和边数\输入提示 cin>>n>>m;

t.v1=n; //给树的结点总数和边的结点总数赋值 t.e1=m;

t.v=new int[n]; //结点数组 for(int i=0;i

t.e=new int[2*n-1]; //边与结点数的关系 for(int i=0;i<2*n-1;i++) //循环 初始化 t.e[i]=0; t.a=new int *[n+1]; for(int i=0;i<=n;i++) t.a[i]=new int[n+1];

cout<<\请依次输入各边的两端点及权值\ for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

t.a[i][j]=10000; //初始化为无穷大 for(int i=1;i<=m;i++){ //for循环输入

4 / 22

石家庄铁道大学实习报告

cin>>m1>>m2>>count;

t.a[m1][m2]=count; //无向网赋值 t.a[m2][m1]=count; }

judge(t); //判断是否有全部叶子节点 cout<<\最小生成树为：\ for(int i=1;i

cout<

cout<<\最小生成树的权值之和为：\}

//--------------------------------------kruskal算法------------------------------------------------------// int Find(int x){ //查

if(x==Father[x]) return x; else return Find(Father[x]); }

void Union(int x,int y){ //并 Father[x]=y ; }

int Top,Edge;

bool Com(Node x,Node y){ return x.Weight

dequeMap;

//调用克鲁斯卡尔的相关代码 void show_kruskal() {

cout<<\请输入结点个数及边数：\ cin>>Top>>Edge; cout<<\请依次输入两点及权值：\ for(i=1;i<=Top;i++) for(j=1;j<=Top;j++){ cin>>x;

if(j>i && x!=100) { y.Next=j; y.Priority=i; y.Weight=x;

Map.push_back(y); } }

sort(Map.begin(),Map.end(),Com);

5 / 22

石家庄铁道大学实习报告

for(i=1;i<=Top;i++) { Father[i]=i; } cout<<\树的各组成边有：\ for(i=0;i

if(Find(Map[i].Priority)!=Find(Map[i].Next)) { Union(Map[i].Priority,Map[i].Next); count++;

if(Map[i].Priority>Map[i].Next)

cout<

cout<

//--------------------------------------floyd算法---------------------------------------------------------------// //图的创建

void F_Creategraph(F_MGraph *F_MGraph){ cout << \请输入顶点数和边数\

cin >> F_MGraph->Vcount >> F_MGraph->Ecount;

for (int row = 1; row <= F_MGraph->Vcount; row++){ //初始化为无穷,即不连通 for (int col = 1; col <= F_MGraph->Vcount; col++){ F_MGraph->edges[row][col] = MAX_VALUE; } }

cout << \请输入起始结点 最终结点 权重\ for (int i = 1; i <= F_MGraph->Ecount; i++){ //赋值 cin >> row >> col >> weight;

F_MGraph->edges[row][col] = weight; } }

//佛洛依德算法

void Floyd(F_MGraph *F_MGraph, int **iArrPath){ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){ iArrPath[i][j] = i; } } //初始化路径表

for (int k = 1; k <= F_MGraph->Vcount; k++){ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){ if (F_MGraph->edges[i][k] + F_MGraph->edges[k][j] <

6 / 22

石家庄铁道大学实习报告

F_MGraph->edges[i][j]){

F_MGraph->edges[i][j] = F_MGraph->edges[i][k] F_MGraph->edges[k][j];

iArrPath[i][j] = iArrPath[k][j]; } } } } }

//打印佛洛依德算法最短路径

void PrintResult(F_MGraph *F_MGraph, int **iArrPath){ cout << \起点 ->终点\\t距离\\t\\t最短路径\ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){ if (i != j){

cout << i << \

if (F_MGraph->edges[i][j] == MAX_VALUE){ cout << \无连通路径\ } else{

cout << F_MGraph->edges[i][j] << \ std::stack stackVertices; do {

k = iArrPath[i][k]; stackVertices.push(k); } while (k != i);

cout << stackVertices.top(); stackVertices.pop();

unsigned int nLength = stackVertices.size();

for (unsigned int nIndex = 0; nIndex < nLength; nIndex++) {

cout << \ stackVertices.pop(); }

cout << \ } } } } }

//调用弗洛伊德相关代码 void show_floyd(){

for (int i = 0; i < MAX_VALUE; i++){ iArrPath[i] = new int[MAX_VALUE];

7 / 22

+

石家庄铁道大学实习报告

}

F_MGraph F_MGraph;

for (int i = 0; i < MAX_VALUE; i++){

F_MGraph.edges[i] = new int[MAX_VALUE]; }

F_Creategraph(&F_MGraph); Floyd(&F_MGraph, iArrPath);

PrintResult(&F_MGraph, iArrPath); }

//-----------------------------Dijkstra算法------------------------------------// //创建图函数

void createGraph(HeadNode *G, int nodeNum, int arcNum) {//G表示指向头结点数组的第一个结点的指针 nodeNum表示结点个数 arcNum表示边的个数

cout << \开始创建图(\ << \ //初始化头结点

for (int i = 0; i < nodeNum; i++) {

G[i].nodeName = i+1; //位置0上面存储的是结点v1,依次类推 G[i].inDegree = 0; //入度为0 G[i].link = NULL; //指针置空 }

//给边赋权值

for (int j = 0; j < arcNum; j++) {

int begin, end, weight; //起点 终点 权值 cout << \请输入 起始顶点 结束顶点 权值: \

cin >> begin >> end >> weight; //输入起点 终点 权值

D_Node *node = new D_Node; //创建边表插入链接表 node->adjvex = end - 1; //记录终点信息 node->weight = weight; //赋权值

++G[end-1].inDegree; //边的终点入度加1

node->next = G[begin-1].link; //前插法 即后输入的先打印（打印图的时候是倒着的） G[begin-1].link = node; //插入链接表的第一个位置 } }

//打印图函数

void printGraph(HeadNode *G, int nodeNum) { //输出结点入度及以其为起点的边

for (int i = 0; i < nodeNum; i++) {

cout << \结点v\的入度为\以它为起始顶点的边为(起点---权重---终点): \ D_Node *node = G[i].link;

while (node != NULL) { //依附于该顶点的指针不为空，即还存在以该结点为起点的边

cout << \<< G[i].nodeName<<\<< G[node->adjvex].nodeName<

8 / 22

石家庄铁道大学实习报告

node = node->next; //依次向后遍历 }

cout << endl; } }

//得到begin->end权重

int getWeight(HeadNode *G, int begin, int end) { D_Node *node = G[begin-1].link; while (node) {

if (node->adjvex == end - 1) { return node->weight; }

node = node->next; } }

//从begin开始，计算其到每一个顶点的最短路径 void Dijkstra(HeadNode *G, int nodeNum, int begin) { //初始化所有结点的

for (int i = 0; i < nodeNum; i++) {

G[i].d = INT_MAX; //到每一个顶点的距离初始化为无穷大，头文件包含limits，增强可移植性

G[i].isKnown = false; //到每一个顶点的最短距离为未知数 }

G[begin-1].d = 0; //到其本身的距离为0 G[begin-1].parent = -1; //表示该结点是起始结点

while(true) { //如果所有的结点的最短距离都已知, 那么就跳出循环 bool ok = true; //表示是否全部ok for (int k = 0; k < nodeNum; k++) {

if (!G[k].isKnown) {//只要有一个顶点的最短路径未知,ok就设置为false ok = false; break; } }

if (ok) return;

//搜索未知结点中d最小的,将其变为known int minIndex = -1;

for (int i = 0; i < nodeNum; i++) { if (!G[i].isKnown) { if (minIndex == -1) minIndex = i;

else if (G[minIndex].d > G[i].d) minIndex = i; } }

9 / 22

石家庄铁道大学实习报告

cout << \已知最短路径的结点为: v\

G[minIndex].isKnown = true; //将其加入最短路径已知的顶点集

D_Node *node = G[minIndex].link; // 将以minIndex为起始顶点的所有的d更新 while (node != NULL) { int begin = minIndex + 1; int end = node->adjvex + 1;

int weight = getWeight(G, begin, end);

if (G[minIndex].d + weight < G[end-1].d) { G[end-1].d = G[minIndex].d + weight;

G[end-1].parent = minIndex; //记录最短路径的上一个结点 }

node = node->next; } } }

//打印到end-1的最短路径

void printPath(HeadNode *G, int end) { if (G[end-1].parent == -1) { cout << \ } else if (end != 0) {

printPath(G, G[end-1].parent + 1); // 因为这里的parent表示的是下标，从0开始，所以要加1

cout << \ } }

//调用迪杰斯特拉的相关代码 void show_Dijkstra() {

HeadNode *G; //头结点

int nodeNum, arcNum; //顶点个数，边的个数 cout << \请输入顶点个数，边的个数: \ cin >> nodeNum >> arcNum;

G = new HeadNode[nodeNum];

createGraph(G, nodeNum, arcNum); //创建图 cout << \ cout << \下面开始打印图信息...\

printGraph(G, nodeNum); //打印图 cout << \ cout << \下面开始运行dijkstra算法...\

Dijkstra(G, nodeNum, 1); //运行Dijkstra算法 cout << \ cout << \打印从v1开始所有的最短路径\ for (int k = 2; k <= nodeNum; k++) {

cout << \到v\的最短路径为\

printPath(G, k); //打印最短路径

10 / 22

石家庄铁道大学实习报告

cout << endl; } }

5．调试分析

1. 书本上的伪代码大多都没有初始化,注意初始化即可。 2. 调试时要多增加几个断点和监视对象。

6．使用说明

程序名为 algorithms.exe，运行环境为 DOS。程序执行后显示

***********************欢迎来到算法演示程序************************************ 1.Prim 算法 2.Kruskal算法 3.Floyd算法 4.Dijkstra算法 5.退出 请选择您的操作：

在” 请选择您的操作：”后输入数字选择执行不同的功能。

选择 1：执行Prim算法,输入结点及边的总数，起点终点和权值 选择 2：执行Kruskal算法，输入结点及边的总数，起点终点和权值 选择 3：执行Floyd算法 输入结点及边的总数，起点终点和权值 选择4：执行Dijkstra算法输入结点及边的总数，起点终点和权值 选择5：退出程序

7．测试结果

图 1

11 / 22

石家庄铁道大学实习报告

图 2

图 3

8.附录

/*4、 Prim 算法 输入：无向图（顶点序列，边序列） 功能要求：输出最小生成树的各组成边及最小生成树的权值 5、 Kruskal 算法 输入：无向图（顶点序列，边序列） 功能要求：输出最小生成树的各组成边及最小生成树的权值

6、 Floyd 算法 输入：有向图（顶点序列，有向边序列） 功能要求：输出各顶点对间最短

12 / 22

石家庄铁道大学实习报告

路径和路径长度 7、 Dijkstra 算法

输入：有向图（顶点序列，有向边序列），起始顶点 功能要求：输出起始顶点到其它各顶点的最短路径和路径长度*/ //于博 20153236 2017/6/30 #include #include

#include //增强程序可移植性，包含最值宏定义 using namespace std; #include \#include \#define Max 100

#define MAX_VALUE 1000 //宏定义 #define MAX_VERTEX_COUNT 20

//------------------------------------------Prim算法--------------------------------------------------// //树结构体 struct Tree{ int **a; int *v; int *e;

int v1; //叶子结点总数 int e1; //边的总数 };

int ok(Tree &t,int k){ int l=0;

while(l

if(t.v[l]==k){ return 0;} l++; }

return 1; }

//判断函数--是否树包含图的所有结点 void judge(Tree &t){ t.v[0]=1;

for(int i=1;i

int biaoji1=10000; //标记无穷大 int biaoji2=0; int biaoji3=0;

for(int j=0;j

for(int k=1;k<=t.v1;k++){ if(t.a[m][k]

13 / 22

石家庄铁道大学实习报告

if(ok(t,k)){

biaoji1=t.a[m][k]; biaoji2=m; biaoji3=k; } } } }

t.v[i]=biaoji3; t.e[2*i-1]=biaoji2; t.e[2*i]=biaoji3; } }

//调用prim算法相关所有代码 void show_prim(){

int x,y; //起点、终点 Tree t; //树 int n,m;

int m1,m2; //起点、终点 int count; ////权值计数 int sum=0; //权值之和 cout<<\请输入图的点数和边数\输入提示 cin>>n>>m;

t.v1=n; //给树的结点总数和边的结点总数赋值 t.e1=m;

t.v=new int[n]; //结点数组 for(int i=0;i

t.e=new int[2*n-1]; //边与结点数的关系 for(int i=0;i<2*n-1;i++) //循环 初始化 t.e[i]=0; t.a=new int *[n+1]; for(int i=0;i<=n;i++) t.a[i]=new int[n+1];

cout<<\请依次输入各边的两端点及权值\ for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

t.a[i][j]=10000; //初始化为无穷大 for(int i=1;i<=m;i++){ //for循环输入 cin>>m1>>m2>>count;

t.a[m1][m2]=count; //无向网赋值 t.a[m2][m1]=count; }

judge(t); //判断是否有全部叶子节点

14 / 22

石家庄铁道大学实习报告

cout<<\最小生成树为：\ for(int i=1;i

cout<

cout<<\最小生成树的权值之和为：\}

//--------------------------------------prim算法结束-----------------------------------------------------// //--------------------------------------kruskal算法

------------------------------------------------------// int Father[Max]; //结点结构体 struct Node { int Next;

int Weight; //权重 int Priority; //优先级 };

int Find(int x){ //查

if(x==Father[x]) return x; else return Find(Father[x]); }

void Union(int x,int y){ //并 Father[x]=y ; }

int Top,Edge;

bool Com(Node x,Node y){

return x.Weight

dequeMap;

//调用克鲁斯卡尔的相关代码 void show_kruskal() {

cout<<\请输入结点个数及边数：\ cin>>Top>>Edge; int i,j; Node y;

cout<<\请依次输入两点及权值：\ for(i=1;i<=Top;i++) for(j=1;j<=Top;j++){ int x; cin>>x;

15 / 22

石家庄铁道大学实习报告

if(j>i && x!=100) { y.Next=j; y.Priority=i; y.Weight=x;

Map.push_back(y); } }

sort(Map.begin(),Map.end(),Com); for(i=1;i<=Top;i++) { Father[i]=i; }

int count=0;

cout<<\树的各组成边有：\ for(i=0;i

if(Find(Map[i].Priority)!=Find(Map[i].Next)) { Union(Map[i].Priority,Map[i].Next); count++;

if(Map[i].Priority>Map[i].Next)

cout<

cout<

//----------------------------------------kruskal算法结束

-----------------------------------------------------------// //----------------------------------------floyd算法

-----------------------------------------------------------------// //图的定义

struct F_MGraph {

int *edges[MAX_VALUE]; //边指针

int Vcount, Ecount; //结点个数、边个数 };

//图的创建

void F_Creategraph(F_MGraph *F_MGraph){ cout << \请输入顶点数和边数\

cin >> F_MGraph->Vcount >> F_MGraph->Ecount;

for (int row = 1; row <= F_MGraph->Vcount; row++){ //初始化为无穷,即不连通

for (int col = 1; col <= F_MGraph->Vcount; col++){ F_MGraph->edges[row][col] = MAX_VALUE; } }

16 / 22

石家庄铁道大学实习报告

cout << \请输入起始结点 最终结点 权重\ int row, col, weight;

for (int i = 1; i <= F_MGraph->Ecount; i++){ //赋值 cin >> row >> col >> weight;

F_MGraph->edges[row][col] = weight; } }

//佛洛依德算法

void Floyd(F_MGraph *F_MGraph, int **iArrPath){ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){ iArrPath[i][j] = i; } }

//初始化路径表

for (int k = 1; k <= F_MGraph->Vcount; k++){ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){

if (F_MGraph->edges[i][k] + F_MGraph->edges[k][j] < F_MGraph->edges[i][j]){

F_MGraph->edges[i][j] = F_MGraph->edges[i][k] + F_MGraph->edges[k][j];

iArrPath[i][j] = iArrPath[k][j]; } } } } }

//打印佛洛依德算法最短路径

void PrintResult(F_MGraph *F_MGraph, int **iArrPath){ cout << \起点 ->终点\\t距离\\t\\t最短路径\ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){ if (i != j){

cout << i << \

if (F_MGraph->edges[i][j] == MAX_VALUE){ cout << \无连通路径\ } else{

cout << F_MGraph->edges[i][j] << \ std::stack stackVertices; int k = j; do {

17 / 22

石家庄铁道大学实习报告

k = iArrPath[i][k]; stackVertices.push(k); } while (k != i);

cout << stackVertices.top(); stackVertices.pop();

unsigned int nLength = stackVertices.size();

for (unsigned int nIndex = 0; nIndex < nLength; nIndex++) {

cout << \ stackVertices.pop(); }

cout << \ } } } } }

//调用弗洛伊德相关代码 void show_floyd(){

int *iArrPath[MAX_VALUE];

for (int i = 0; i < MAX_VALUE; i++){ iArrPath[i] = new int[MAX_VALUE]; }

F_MGraph F_MGraph;

for (int i = 0; i < MAX_VALUE; i++){

F_MGraph.edges[i] = new int[MAX_VALUE]; }

F_Creategraph(&F_MGraph); Floyd(&F_MGraph, iArrPath);

PrintResult(&F_MGraph, iArrPath); }

//--------------------------------------------------floyd算法结束------------------------------------------------------------// //--------------------------------------------------Dijkstra算法-------------------------------------------------------------// //定义边表

struct D_Node {

int adjvex; //邻接点域 该边所指向的顶点的位置 int weight; // 数据域 边的权值 D_Node *next; //链域 下一条边的指针 };

// 定义表头结点表

18 / 22

石家庄铁道大学实习报告

struct HeadNode{

int nodeName; //数据域 顶点信息 int inDegree; //数据域 入度

int d; //数据域 表示当前情况下起始顶点至该顶点的最短路径,初始化为无穷大

bool isKnown; //数据域 表示起始顶点至该顶点的最短路径是否已知,true表示已知，false表示未知

int parent; //数据域 表示最短路径的上一个顶点

D_Node *link; //链域 指向第一条依附该顶点的边的指针 };

//创建图函数

void createGraph(HeadNode *G, int nodeNum, int arcNum) {//G表示指向头结点数组的第一个结点的指针 nodeNum表示结点个数 arcNum表示边的个数

cout << \开始创建图(\ //初始化头结点

for (int i = 0; i < nodeNum; i++) {

G[i].nodeName = i+1; //位置0上面存储的是结点v1,依次类推 G[i].inDegree = 0; //入度为0 G[i].link = NULL; //指针置空 }

//给边赋权值

for (int j = 0; j < arcNum; j++) {

int begin, end, weight; //起点 终点 权值 cout << \请输入 起始顶点 结束顶点 权值: \

cin >> begin >> end >> weight; //输入起点 终点 权值

D_Node *node = new D_Node; //创建边表插入链接表 node->adjvex = end - 1; //记录终点信息 node->weight = weight; //赋权值

++G[end-1].inDegree; //边的终点入度加1

node->next = G[begin-1].link; //前插法 即后输入的先打印（打印图的时候是倒着的）

G[begin-1].link = node; //插入链接表的第一个位置 } }

//打印图函数

void printGraph(HeadNode *G, int nodeNum) { //输出结点入度及以其为起点的边

for (int i = 0; i < nodeNum; i++) {

cout << \结点v\的入度为\以它为起始顶点的边为(起点---权重---终点): \ D_Node *node = G[i].link;

while (node != NULL) { //依附于该顶点的指针不为空，即还存在以该结点为起点的边

cout << \

19 / 22

石家庄铁道大学实习报告

G[node->adjvex].nodeName<

node = node->next; //依次向后遍历 }

cout << endl; } }

//得到begin->end权重

int getWeight(HeadNode *G, int begin, int end) { D_Node *node = G[begin-1].link; while (node) {

if (node->adjvex == end - 1) { return node->weight; }

node = node->next; } }

//从begin开始，计算其到每一个顶点的最短路径

void Dijkstra(HeadNode *G, int nodeNum, int begin) { //初始化所有结点的

for (int i = 0; i < nodeNum; i++) {

G[i].d = INT_MAX; //到每一个顶点的距离初始化为无穷大，头文件包含limits，增强可移植性

G[i].isKnown = false; //到每一个顶点的最短距离为未知数 }

G[begin-1].d = 0; //到其本身的距离为0 G[begin-1].parent = -1; //表示该结点是起始结点

while(true) { //如果所有的结点的最短距离都已知, 那么就跳出循环 bool ok = true; //表示是否全部ok for (int k = 0; k < nodeNum; k++) {

if (!G[k].isKnown) {//只要有一个顶点的最短路径未知,ok就设置为false ok = false; break; } }

if (ok) return;

//搜索未知结点中d最小的,将其变为known int minIndex = -1;

for (int i = 0; i < nodeNum; i++) { if (!G[i].isKnown) { if (minIndex == -1) minIndex = i;

else if (G[minIndex].d > G[i].d) minIndex = i; }

20 / 22

石家庄铁道大学实习报告

}

cout << \已知最短路径的结点为: v\ G[minIndex].isKnown = true; //将其加入最短路径已知的顶点集

D_Node *node = G[minIndex].link; // 将以minIndex为起始顶点的所有的d更新 while (node != NULL) {

int begin = minIndex + 1; int end = node->adjvex + 1;

int weight = getWeight(G, begin, end); if (G[minIndex].d + weight < G[end-1].d) { G[end-1].d = G[minIndex].d + weight;

G[end-1].parent = minIndex; //记录最短路径的上一个结点 }

node = node->next; } } }

//打印到end-1的最短路径

void printPath(HeadNode *G, int end) { if (G[end-1].parent == -1) { cout << \ } else if (end != 0) {

printPath(G, G[end-1].parent + 1); // 因为这里的parent表示的是下标，从0开始，所以要加1

cout << \ } }

//调用迪杰斯特拉的相关代码 void show_Dijkstra() {

HeadNode *G; //头结点

int nodeNum, arcNum; //顶点个数，边的个数 cout << \请输入顶点个数，边的个数: \ cin >> nodeNum >> arcNum;

G = new HeadNode[nodeNum];

createGraph(G, nodeNum, arcNum); //创建图 cout << \ cout << \下面开始打印图信息...\

printGraph(G, nodeNum); //打印图 cout << \ cout << \下面开始运行dijkstra算法...\

Dijkstra(G, nodeNum, 1); //运行Dijkstra算法 cout << \ cout << \打印从v1开始所有的最短路径\ for (int k = 2; k <= nodeNum; k++) {

cout << \到v\的最短路径为\

21 / 22

石家庄铁道大学实习报告

printPath(G, k); //打印最短路径 cout << endl; } }

//------------------------------------------Dijkstra算法结束

---------------------------------------------------------------// //菜单

void menu(){

cout<<\欢迎来到算法演示程序****************************************\

cout<<\算法 2.Kruskal算法\ cout<<\算法 4.Dijkstra算法\

cout<<\退出\}

void main(){

menu();int i; while(1){

cout<<\请选择您的操作：\ switch(i){

case 1:cout<<\接下来运行Prim算法...\

case 2:cout<<\接下来运行Kruskal算法...\ case 3:cout<<\接下来运行Floyd算法...\

case 4:cout<<\接下来运行Dijkstra算法...\ case 5:cout<<\退出成功，欢迎下次登录。。。\ default:cout<<\输入错误。\

} //switch结束 if(i!=5)continue; else break;

} //while循环结束 }

22 / 22

本文来源：https://www.bwwdw.com/article/optp.html