数据结构 最小生成树Prim算法 最短路径Dijkstra算法 最短路径Floyd算法

news/2024/7/15 18:31:32 标签: 数据结构, prim, dijkstra, 图论, c++

图的邻接矩阵存储看这里
使用的图为：
在这里插入图片描述

最小生成树Prim算法

  1. 首先标记第一个点已经确定，然后计算出第一个点到其余各个未确定点的权值，并修改邻接点为第一个点
  2. 之后每一步都找到上一步更新后的权值中最小的那个点，确定该点并计算出该点到其余各个未确定点的权值，若比原来的权值小则更新权值与邻接点，否则保持原来的权值和邻接点
  3. 每一步确定一个点，直到所有的点都被确定则结束

需要定义新的结构：

template<typename VertexType, typename VRType>
struct ClosEdgeType
{
	VertexType adjvex;
	VRType lowcost;
};

template<typename VertexType, typename VRType>
using ClosEdge = ClosEdgeType<VertexType, VRType>[MAX_VERTEX_NUM];

具体实现：

template<typename VertexType, typename VRType>
int minimum(ClosEdge<VertexType, VRType> closedge, int num)//取最小权值的下标
{
	int low = INFINITY;
	int lowpos = 0;
	for (int i = 0; i < num; i++)
	{
		if (closedge[i].lowcost > 0 && closedge[i].lowcost < low)
		{
			low = closedge[i].lowcost;
			lowpos = i;
		}
	}
	return lowpos;
}

template<typename VertexType, typename VRType, typename InfoType>
void miniSpanTree_PRIM(MGraph<VertexType, VRType, InfoType>MG, VertexType u)//最小生成树 Prim算法
{
	cout << "最小生成树：" << endl;
	ClosEdge<VertexType, VRType> closedge;
	int k = locateVex(MG, u);//找到u在数组中的下标
	closedge[k].lowcost = 0;//表示已经确定u
	for (int i = 0; i < MG.vexnum; i++)//初始化u到其余点的权重
	{
		if (i != k)
		{
			closedge[i].adjvex = u;
			closedge[i].lowcost = MG.arcs[k][i].adj;
		}
	}
	for (int i = 0; i < MG.vexnum - 1; i++)
	{
		k = minimum(closedge, MG.vexnum);//找到上一步确定的点到其余点权值最小的点
		closedge[k].lowcost = 0;//确定该点
		cout << "(" << closedge[k].adjvex << ", " << MG.vexs[k] << ")" << endl;//输出路径
		for (int j = 0; j < MG.vexnum; j++)//遍历k点到其余未确定顶点的权值
		{
			if (closedge[j].lowcost > 0 && MG.arcs[k][j].adj < closedge[j].lowcost)
			{//如果k->j的权值小于之前求得的到j的最小权值
				closedge[j].adjvex = MG.vexs[k];
				closedge[j].lowcost = MG.arcs[k][j].adj;
			}
		}
	}
}

在这里插入图片描述

最短路径Dijkstra算法

  1. 首先确定第一个点到其余各个顶点的路径，并修改邻接点，标记第一个点已经找到最短路径
  2. 每一步都寻找从第一个点出发到各个未确定点当中路径最短的点，确定该顶点
  3. 计算第一个点经上一步确定的点到其余各个未确定点的距离，再与原本第一个点到其余各个未确定点的距离比较，取小者，并设置相应路径长度和邻接点
  4. 每次确定一个点，直到确定所有顶点

需要定义新的结构：

using PathMatrix = int[MAX_VERTEX_NUM];

具体实现：

template<typename VertexType,typename VRType,typename InfoType, typename ShortPathTable>
void shortestPath_DIJ(MGraph<VertexType, VRType, InfoType>MG, int v0, PathMatrix& P, ShortPathTable& D)//最短路径 Dijkstra算法
{//P[i] v0到vi要经过的、vi直接前驱的点  D[i] v0到vi当前找到的最短路径长度
	bool finals[MAX_VERTEX_NUM] = { false };//标识已经找到从v0出发到下标对应的点的最短路径
	for (int i = 0; i < MG.vexnum; i++)//初始化
	{
		finals[i] = false;//未找到到i的最短路径
		D[i] = MG.arcs[v0][i].adj;//v0到i的最短路径
		if (D[i] < INFINITY)
			P[i] = v0;//表示v0可以到i
		else
			P[i] = -1;//表示目前没有点可以到i
	}
	D[v0] = 0;//v0到v0的最短路径
	finals[v0] = true;//已经找到v0到v0的最短路径
	for (int i = 0; i < MG.vexnum - 1; i++)
	{
		VRType min = INFINITY;
		int v;
		for (int j = 0; j < MG.vexnum; j++)//遍历所有节点，寻找所有v0到j中距离最短的那个j
		{
			if (!finals[j])
			{
				if (D[j] < min)
				{
					v = j;//v表示当前最短的v0到j的路径
					min = D[j];
				}
			}
		}//找到路径最短的v0到v
		finals[v] = true;
		for (int i = 0; i < MG.vexnum; i++)
		{
			if (!finals[i] && (MG.arcs[v][i].adj + min < D[i]) && (MG.arcs[v][i].adj < INFINITY))//比较v0到v再到i的路径和原先路径的长度
			{
				D[i] = MG.arcs[v][i].adj + min;
				P[i] = v;
			}
		}
	}
}

template<typename VertexType, typename VRType, typename InfoType, typename ShortPathTable>
void printShortestPath_DIJ(MGraph<VertexType, VRType, InfoType> MG, PathMatrix P, ShortPathTable D, int v, int w)
{//打印最短路径
	cout << MG.vexs[v] << "到" << MG.vexs[w] << "最短路径：" << endl;
	SqStack<int> S;
	initSqStsck(S);
	int t = w;
	push(S, t);
	while (P[t] != -1)
	{
		t = P[t];
		push(S, t);
	}
	while (!isEmpty(S))
	{
		pop(S, t);
		cout << MG.vexs[t] << "-->";
	}
	cout << "\b\b\b   \t路径长度：";
	D[w] == INFINITY ? cout << "∞" : cout << D[w];
	cout << endl;
}

栈参考这里
在这里插入图片描述

最短路径Floyd算法

  1. 首先计算各个顶点之间的距离，修改邻接表
  2. 循环求出各个顶点分别经所有顶点到其余各个顶点的路径与原有路径比较，取小者，设置邻接点

具体实现：

template<typename VertexType, typename VRType, typename InfoType>
void shortestPath_FLOYD(MGraph<VertexType, VRType, InfoType>MG, int (*P)[MAX_VERTEX_NUM], int (*D)[MAX_VERTEX_NUM])
{//最短路径 Floyd算法
	for (int i = 0; i < MG.vexnum; i++)//初始化每个顶点间的距离
		for (int j = 0; j < MG.vexnum; j++)
		{
			D[i][j] = MG.arcs[i][j].adj;
			if (D[i][j] != INFINITY)
				P[i][j] = i;//i->j经过i
		}
	for (int k = 0; k < MG.vexnum; k++)
		for (int i = 0; i < MG.vexnum; i++)
			for (int j = 0; j < MG.vexnum; j++)
			{
				if ((D[i][j] > D[i][k] + D[k][j]) && D[i][k] < INFINITY && D[k][j] < INFINITY)//i->k->j的距离比之前求得的i->j的距离小
				{//替换最短路径
					D[i][j] = D[i][k] + D[k][j];
					P[i][j] = k;
				}
			}
}

http://www.niftyadmin.cn/n/1712036.html

相关文章

数据结构 图 邻接表表示法

数据结构 图 邻接表表示法

图 邻接表表示法 图的邻接矩阵表示法看这里 基本结构&#xff1a; template<typename InfoType> struct ArcNode {int adjvex;ArcNode* nextarc;InfoType* info; };template<typename VertexType, typename InfoType> struct VNode {VertexType data;ArcNode<…
阅读更多...
数据结构 图 深度优先遍历（DFS） 广度优先遍历（BFS）

数据结构 图 深度优先遍历（DFS） 广度优先遍历（BFS）

图的邻接表表示法看这里 首先定义必要的辅助数组和函数 bool visited[MAX_VERTEX_NUM];//标志是否访问过template<typename VertexType, typename InfoType> int firstAdjVex(ALGraph<VertexType, InfoType>ALG, int vIndex)//寻找第一个邻接点&#xff0c;未找到…
阅读更多...
数据结构 顺序表（泛型编程）

数据结构 顺序表（泛型编程）

顺序表 虽然之前写过顺序表&#xff0c;但是没用模板所以很不方便&#xff0c;于是这次补一个顺序表的模板&#xff0c;写得比较仓促也比较简单&#xff0c;虽然没有注释但应该不难懂 #pragma once #include <iostream> #define MAX_LIST_SIZE 20using namespace std;e…
阅读更多...
数据结构 排序（直接插入排序、起泡（冒泡）排序、简单选择排序、快速排序、堆排序、基数排序）

数据结构 排序（直接插入排序、起泡（冒泡）排序、简单选择排序、快速排序、堆排序、基数排序）

这是目录直接插入排序起泡排序&#xff08;冒泡排序&#xff09;简单选择排序快速排序堆排序基数排序测试需要用到的结构的定义template<typename KeyType, typename InfoType> struct RedType {KeyType key;InfoType otherinfo; };enum Status { ERROR 0, OK 1 };temp…
阅读更多...
数据结构 单链表 C++模板

数据结构 单链表 C++模板

数据结构 单链表 C模板 #pragma once #include<iostream>using namespace std;template<class C> class LinkNode {C data;LinkNode* next;public:LinkNode();LinkNode(const C& data);void setData(const C& data) { this->data data; }C& getDa…
阅读更多...
编译原理 词法分析

编译原理 词法分析

编译原理 词法分析 实验目的&#xff1a; 通过设计编制调试一个具体的词法分析程序&#xff0c;加深对词法分析原理的理 解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法 分析方法。 编制一个读单词过程&#xff0c;从输入的源程序中&#xff0c;识别…
阅读更多...
编译原理 词法分析 DFA 确定的有限自动机

编译原理 词法分析 DFA 确定的有限自动机

编译原理 词法分析 DFA 实验目的 通过本次实验&#xff0c;加深对DFA及其识别的语言的理解&#xff0c;学习对一般的DFA的表达方法与编程实现方法。 实验环境 Microsoft Visual Studio 2019 Community 思路 &#xff08;1&#xff09;DFA的输入&#xff1a; 分别输入DFA的“…
阅读更多...
数据库（事务、视图、变量、存储过程 、函数 、循环结构）

数据库（事务、视图、变量、存储过程 、函数 、循环结构）

文章目录一. 事务1.事务的ACID属性2.事务的创建&#xff1a;3.事务产生并发问题3.1 事务隔离级别&#xff1a;3.2 回滚二. 视图1. 视图的创建2. 视图的修改3.视图的删除4. 视图的查看5. 视图的更新6.视图和表的区别三. 变量1.系统变量&#xff1a;2.设置系统变量的值3.全局变量…
阅读更多...
最新文章

Copyright @ 2022~2023