【C++ 实现】图论概念,最小生成树,单/多源最短路径实现

这篇具有很好参考价值的文章主要介绍了【C++ 实现】图论概念,最小生成树,单/多源最短路径实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


数据结构表示图

首先节点的存取,V是节点key,vector<pair<V,V>> map;其实已经能表达一个图了,但是这样保存节点对我们使用来说会导致复杂度高。

常用保存节点的方式,有矩阵和邻接表。
矩阵的优点:O(1) 时间找到两点是否相连以及他们的权值。
矩阵的缺点:找一点相邻的所有节点的时候是O(N)的,即会遍历到不相连的两两节点。

图还分有向图和无向图,一般来说有向图存出边即可。

template<class V, class W, bool Direction = false> V表示节点的类型,W表示权值的类型,Direction表示是否是无向图。
图一般提供的函数,构造函数,将图的每一个节点的距离初始化;
AddEdge函数:将两个节点建立联系,附上权值;
GetVertexIndex: 将对应的图的节点转化为下标

template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{
public:
    typedef Graph<V, W, MAX_W, Direction> Self;
    Graph() = default;
    Graph(const V *vertexs, size_t n)
    {
        _vertexs.reserve(n);
        for (size_t i = 0; i < n; ++i)
        {
            _vertexs.push_back(vertexs[i]);
            _vIndexMap[vertexs[i]] = i;
        }
        // MAX_W 作为不存在边的标识值
        _matrix.resize(n);
        for (auto &e : _matrix)
        {
            e.resize(n, MAX_W);
        }
    }
    size_t GetVertexIndex(const V &v)
    {
        auto ret = _vIndexMap.find(v);
        if (ret != _vIndexMap.end())
        {
            return ret->second;
        }
        else
        {
            throw invalid_argument("不存在的顶点");
            return -1;
        }
    }
    void _AddEdge(size_t srci, size_t dsti, const W &w)
    {
        _matrix[srci][dsti] = w;
        if (Direction == false)
        {
            _matrix[dsti][srci] = w;
        }
    }
    void AddEdge(const V &src, const V &dst, const W &w)
    {
        size_t srci = GetVertexIndex(src);
        size_t dsti = GetVertexIndex(dst);
        _AddEdge(srci, dsti, w);
    }
           
        void Print()
    {
        // 打印顶点和下标映射关系
        for (size_t i = 0; i < _vertexs.size(); ++i)
        {
            cout << _vertexs[i] << "-" << i << " ";
        }
        cout << endl
             << endl;
        cout << " ";
        for (size_t i = 0; i < _vertexs.size(); ++i)
        {
            cout << i << " ";
        }
        cout << endl;
        // 打印矩阵
        for (size_t i = 0; i < _matrix.size(); ++i)
        {
            cout << i << " ";
            for (size_t j = 0; j < _matrix[i].size(); ++j)
            {
                if (_matrix[i][j] != MAX_W)
                    cout << _matrix[i][j] << " ";
                else
                    cout << "#"
                         << " ";
            }
            cout << endl;
        }
        cout << endl
             << endl;
        // 打印所有的边
        for (size_t i = 0; i < _matrix.size(); ++i)
        {
            for (size_t j = 0; j < _matrix[i].size(); ++j)
            {
                if (i < j && _matrix[i][j] != MAX_W)
                {
                    cout << _vertexs[i] << "-" << _vertexs[j] << ":" << _matrix[i][j] << endl;
                }
            }
        }
    }
            private : map<V, size_t> _vIndexMap;
    vector<V> _vertexs; // 顶点集合
    vector<vector<W>> _matrix;
      // 存储边集合的矩阵
};
void TestGraph()
{
    Graph<char, int, INT_MAX, true> g("0123", 4);
    g.AddEdge('0', '1', 1);
    g.AddEdge('0', '3', 4);
    g.AddEdge('1', '3', 2);
    g.AddEdge('1', '2', 9);
    g.AddEdge('2', '3', 8);
    g.AddEdge('2', '1', 5);
    g.AddEdge('2', '0', 3);
    g.AddEdge('3', '2', 6);
    g.Print();
}
}
namespace LinkTable
{
    template <class W>
    struct LinkEdge
    {
        int _srcIndex;
        int _dstIndex;
        W _w;
        LinkEdge<W> *_next;
        LinkEdge(const W &w)
            : _srcIndex(-1), _dstIndex(-1), _w(w), _next(nullptr)
        {
        }
    };
    template <class V, class W, bool Direction = false>
    class Graph
    {
        typedef LinkEdge<W> Edge;

    public:
        Graph(const V *vertexs, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0; i < n; ++i)
            {
                _vertexs.push_back(vertexs[i]);
                _vIndexMap[vertexs[i]] = i;
            }
            _linkTable.resize(n, nullptr);
        }
        size_t GetVertexIndex(const V &v)
        {
            auto ret = _vIndexMap.find(v);
            if (ret != _vIndexMap.end())
            {
                return ret->second;
            }
            else
            {
                throw invalid_argument("不存在的顶点");
                return -1;
            }
        }
        void AddEdge(const V &src, const V &dst, const W &w)
        {
            size_t srcindex = GetVertexIndex(src);
            size_t dstindex = GetVertexIndex(dst);
            // 0 1
            Edge *sd_edge = new Edge(w);
            sd_edge->_srcIndex = srcindex;
            sd_edge->_dstIndex = dstindex;
            sd_edge->_next = _linkTable[srcindex];
            _linkTable[srcindex] = sd_edge;
            // 1 0
            // 无向图
            if (Direction == false)
            {
                Edge *ds_edge = new Edge(w);
                ds_edge->_srcIndex = dstindex;
                ds_edge->_dstIndex = srcindex;
                ds_edge->_next = _linkTable[dstindex];
                _linkTable[dstindex] = ds_edge;
            }
        }

    private:
        map<string, int> _vIndexMap;
        vector<V> _vertexs;        // 顶点集合
        vector<Edge *> _linkTable; // 边的集合的临接表
    };
    void TestGraph()
    {
        string a[] = {"张三", "李四", "王五", "赵六"};
        Graph<string, int> g1(a, 4);
        g1.AddEdge("张三", "李四", 100);
        g1.AddEdge("张三", "王五", 200);
        g1.AddEdge("王五", "赵六", 30);
    }
}

最小生成树


什么是最小生成树
在给定一张无向图,如果在它的子图中,任意两个顶点都是互相连通,并且是一个树结构,那么这棵树叫做生成树。当连接顶点之间的图有权重时,权重之和最小的树结构为最小生成树!

Kruskal

  • 选最短的边,且不能构成回路,会用到并查集。因为需要找两个点是否已经存在路径当中。
  • AddEdge可以重载,但是由于V可能就是int,就会造成错误,所以采用换个函数名的方式达到复用的效果。
  • 总之细节很多,实现完看看代码。有不是连通图的情况也需要判断。
//传入参数为一个图,是一个输入型参数,最终图的数值会保存在该图当中。
//返回一个最终的权值总和
int Kruskal(Self& minTree)
{
	//首先初始化最小生成树
	minTree._vertex = _vertex;
	minTree._vertex2index = _vertex2index;
	size_t len = _weightmatrix.size();
	minTree._weightmatrix.resize(len, vector<W>(len, MaxSize));
	//Kruskal算法关注的是边的关系,需要每次取出权重最小的边
	priority_queue<Edge,vector<Edge>,greater<Edge>> pq;
	//初始化优先级队列
	for (int i = 0; i < len; ++i)
	{
		for (int j = 0; j < len; ++j)
		{
			//这个点存在有效权值则入pq,注意这里只用入矩阵的一半即可
			if (i < j && _weightmatrix[i][j] != MaxSize)
			{
				pq.push(Edge(i, j, _weightmatrix[i][j]));
			}
		}
	}
	//此时就有了一个优先级队列保存最小的节点。
	//需要拿出优先级队列的节点并且需要是不能构成环的
	//全局贪心,每次找最小的边进行合并,需要注意不能在一个集合当中,所以可以使用并查集来,且需要保存的是点
	//将所有找到的边合并起来就是答案
	UnionFindSet unionset(_vertex.size());
	W weight = W();
	int i = 1;//边是比点少一条的。
	while (!pq.empty())
	{
		Edge edge = pq.top();
		pq.pop();
		if (unionset.FindRoot(edge._srci) == unionset.FindRoot(edge._desti))
		{
			cout << "构成环: " << _vertex[edge._srci] << "->" << _vertex[edge._desti] << endl;
			continue;
		}
		i++;
		cout << "Add:" << edge._srci << "-> " << edge._desti << endl;
		minTree.Add2Weight(_vertex[edge._srci], _vertex[edge._desti], edge._weight);
		unionset.Union(edge._srci, edge._desti);
		cout << _vertex[edge._srci] << "->" << _vertex[edge._desti] << endl;
		weight += edge._weight;
	}
	if (i != _vertex.size())
	{
		//这个时候表示不是一个连通图
		cout << "不是连通图" << endl;
	}
	return weight;
}

Prim


【C++ 实现】图论概念,最小生成树,单/多源最短路径实现,c++,图论,开发语言
步骤:

  • 先加入const V& v四周围的边入优先级队列(小堆),每次从头部获取一个最短的边,记录为访问,添加新增节点的四周围的边。
  • 为了防止添加的边有重复,我们采用vector<bool>来记录每一个顶点,记录每一个添加进来的顶点。

当然选的边不同,结果也有可能相同。
【C++ 实现】图论概念,最小生成树,单/多源最短路径实现,c++,图论,开发语言

//Prim算法是基于局部的贪心
int Prim(Self& minTree, const V& v)
{
	//初始化最小生成树
	minTree._vertex = _vertex;
	minTree._vertex2index = _vertex2index;
	int len = _vertex.size();
	minTree._weightmatrix.resize(len, vector<W>(len, MaxSize));

	//初始化优先级队列,只不过入一个节点周围的
	priority_queue<Edge,vector<Edge>,greater<Edge>> pq;
	int srci = VertexToIndex(v);
	for (int i = 0; i < len; ++i)
	{
		if (_weightmatrix[srci][i] != MaxSize)
			pq.push(Edge(srci, i, _weightmatrix[srci][i]));
	}
	//初始化访问的列表,这个可以用作区分集合,出边不在visited就不会构成环
	vector<bool> visited(len, false);
	visited[srci] = true;
	W weight = W();//默认权值

	int size = 0;//记录边数
	//从优先级队列取出一个点作为最小的值,这个位置被认为是总体权值最小所加的一条边。
	while (!pq.empty())
	{
		Edge indexEdge = pq.top();
		pq.pop();
		//如果该边终点已经访问过,那么就一定会构成环。
		if (visited[indexEdge._desti])
		{
			cout << "形成回路: " << _vertex[indexEdge._srci] << "->" << _vertex[indexEdge._desti] << endl;
			//该点若已经访问过,说明是入边,此时加入该点会造成环
			continue;
		}
		cout << "加入集合: " << _vertex[indexEdge._srci] << "->" << _vertex[indexEdge._desti] << endl;
		weight += _weightmatrix[indexEdge._srci][indexEdge._desti];
		//入四周围的边
		for (int i = 0; i < _weightmatrix[indexEdge._desti].size(); ++i)
		{
			//该点没有访问过并且是可以到达的则入集合
			if (_weightmatrix[indexEdge._desti][i] != MaxSize && visited[i] == false)
			{
				pq.push(Edge(indexEdge._desti, i, _weightmatrix[indexEdge._desti][i]));
				cout << "加入" << _vertex[indexEdge._desti] << " 后新增了" << _vertex[i] << endl;
			}
		}
		minTree.Add2Weight(_vertex[indexEdge._srci], _vertex[indexEdge._desti], indexEdge._weight);
		visited[indexEdge._desti] = true;
		size++;
	}
	//若size最终为边数说明边都入进来了。
	if (size == _vertex.size()-1)
	{
		//表明了到达这里的时候没有找到一个点
		cout << "是连通图" << endl;
		return weight;
	}
	else
	{
		cout << "不是联通图" << endl;
		return W();
	}

	return weight;
}

最短路径


从A点到其他点的最短距离。
Dijkstra无法解决带负权值的,后续的算法无法解决带负权回路。

Dijkstra

找的起始边,用邻接表和邻接矩阵的有各自的优缺点。

每次用最短的路径更新周围的节点进行松弛操作。
每一次选取一个点,作为到达该点的最短点,由该点更新周围其他点。
缺点:有负权边用Dijkstra会出错。
【C++ 实现】图论概念,最小生成树,单/多源最短路径实现,c++,图论,开发语言

//Dist数组就是告知从src到对应下标所要的代价(权值),path就是该节点父亲节点的下标
void Dijkstra(const V& src, vector<int>& dist, vector<int>& path)
{
	int index = VertexToIndex(src);
	size_t n = _vertex.size();
	dist.resize(n, MaxSize);
	path.resize(n, -1);
	path[index] = index;//自己就是自己的父节点
	dist[index] = 0;
	int len = path.size();
	vector<bool> visited(len, false);
	int size = len;
	while (size--)
	{
		//用index去跟新其他节点的路径
		for (int i = 0; i < n; ++i)
		{
			if (_weightmatrix[index][i] != MaxSize && dist[i] > dist[index] + _weightmatrix[index][i])
			{
				//更新其他路径需要保证更新完更小
				dist[i] = dist[index] + _weightmatrix[index][i];
				//更新父亲
				path[i] = index;
			}
		}
		//更新index
		visited[index] = true;
		int minNum = INT_MAX;

		for (int i = 0; i < n; ++i)
		{
			if (!visited[i] && dist[i] < minNum)
			{
				index = i;
				minNum = dist[i];
			}
		}
		if (minNum == INT_MAX)
		{
			break;
		}
	}
	if (size != 0)
	{
		cout << "不是连通图" << endl;
	}
}

Bellman-Ford算法

Dijkstra算法只能用来解决正权图的单源最短路径问题,但有些题目会出现负权图。这时这个算法
就不能帮助我们解决问题了,而bellman—ford算法可以解决负权图的单源最短路径问题。它的
优点是可以解决有负权边的单源最短路径问题,而且可以用来判断是否有负权回路。它也有明显
的缺点,它的时间复杂度 O(N*E) (N是点数,E是边数)普遍是要高于Dijkstra算法O(N²)的。像这里
如果我们使用邻接矩阵实现,那么遍历所有边的数量的时间复杂度就是O(N^3),这里也可以看出
来Bellman-Ford就是一种暴力求解更新。

  • 优化:第一个轮次进行更新的边才会影响其他路径,只需要拿这些边去更新其他边(SPFA优化,队列优化)。但是对于时间复杂度并没有得出一个结论。最坏情况O(N^3),最好情况O(N^2)
  • 循环提前跳出优化
    可以用SPFA优化,采用队列优化。
    【C++ 实现】图论概念,最小生成树,单/多源最短路径实现,c++,图论,开发语言
    用 (i,j)存在权值的情况去更新其他边。由于每次遍历整个邻接矩阵就好了。
    但是需要遍历n回,n是点的个数。
    注意每一个点dist[到自己] = 0,一开始可以设置为无穷大,根据给的顶点进行更新就可以了。dist[index] = W();//自己到自己的权值为0
    a->b假设需要更新,最多用len条边更新。
// 时间复杂度:O(N^3) 空间复杂度:O(N)
bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
{
	//从src更新其他节点,首先看src能够更新哪些节点
	int len = _vertex.size();
	dist.resize(len, MaxSize);
	pPath.resize(len,-1);

	int index = VertexToIndex(src);
	dist[index] = W();//自己到自己的权值为0


	//如果只更新一次,可能出现后续的节点影响了前面的节点的情况,一个节点最多经过k-2个节点,需要更新k次
	for (int k = 0; k < len; ++k)
	{
		bool flag = true;//如果不需要跟新就可以跳出来
		cout << "更新第:" << k << "轮" << endl;
		for (int i = 0; i < len; ++i)
		{
			//更新已经能够到达的路径周围的节点
			if (dist[i] == MaxSize)
				continue;

			//这里的i就是需要更新周围节点
			for (int j = 0; j < len; ++j)
			{
				if (i != j && _weightmatrix[i][j] != MaxSize)
				{
					//表示这个点是有联系的
					if (dist[j] > dist[i] + _weightmatrix[i][j])
					{
						cout << _vertex[i] << "->" << _vertex[j] << ":" << _weightmatrix[i][j] << endl;
						flag = false;
						//就可以更新
						dist[j] = dist[i] + _weightmatrix[i][j];
						//更新父路径实际上是从i这个节点的父路径来的,观察这里
						pPath[j] = i;
					}
				}
			}
		}
		if (flag)
			break;
	}
	//检测是否有负权回路,检测方法为再更新一次即可。
	bool flag = false;
	for (int i = 0; i < len; ++i)
	{
		//更新已经能够到达的路径周围的节点
		if (dist[i] == MaxSize)
			continue;

		//这里的i就是需要更新周围节点
		for (int j = 0; j < len; ++j)
		{
			if (i != j && _weightmatrix[i][j] != MaxSize)
			{
				//表示这个点是有联系的
				if (dist[j] > dist[i] + _weightmatrix[i][j])
				{
					flag = true;
					break;
				}
			}
		}
		if (flag)
			return false;//有负权回路

		return true;
	}

}

多源最短路径:FloydWarshall


dist数组和pPath数组得是二维的,就能记录任意两个点。结构和前面的有所不同。 距离矩阵能存储任意两个点的距离。
dist数组在前面都是以一个特定的点出发,是我们传参决定的。
FloydWarshall 是取中间点进行更新。本质是用了动态规划。
不需要像Dijstra,Bellman-Ford一个在距离矩阵取,一个在邻接矩阵取。而是都在距离矩阵dist取即可。
【C++ 实现】图论概念,最小生成树,单/多源最短路径实现,c++,图论,开发语言
三维当中的k是经过多少个点的意思。情况就是上述的两种。他虽然是三维空间来表示,但是实现的时候由于中间节点k也可以查二维矩阵就可以了,所以就用二维的矩阵表示。

若是不带负权回路,用Dijstra遍历每一个顶点也是O(N^3),但是FloydWarshall是可以解决负权回路的。
而Bellman-Ford算法的话效率太低了。所以多源最短路径横空出世。

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。
Floyd算法考虑的是一条最短路径的中间节点,即简单路径p={v1,v2,…,vn}上除v1和vn的任意节
点。
设k是p的一个中间节点,那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1,p2。p1
是从i到k且中间节点属于{1,2,…,k-1}取得的一条最短路径。p2是从k到j且中间节点属于{1, 2,…,k-1}取得的一条最短路径。
【C++ 实现】图论概念,最小生成树,单/多源最短路径实现,c++,图论,开发语言

【C++ 实现】图论概念,最小生成树,单/多源最短路径实现,c++,图论,开发语言
左边是距离矩阵,右边是父路径矩阵。

  • 初始化
  • 直接相连的边更新,自己到自己初始化成0
  • 注意父路径vvpPath[i][j] 若是经过了k,则是k,所以需要改变,并且即使是vvDist[i][j] + vvDist[k][j]途中经过了其他的节点,因为我们要找的与j相连的上一个邻接点。k->j不一定是直接相连,若是则是k,否则就是其他。
  • 由于起始点和终点都有可能变,所以中间节点都是需要遍历的,也就是for(int k = 0;k < len;++k)如同i->j最多经过n-2个点。
void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
		{
			vvDist = _weightmatrix;
			int len = vvDist.size();
			//vvDist是权值矩阵
			//vvpPath用来表示到达i,j位置的父亲
			vvpPath.resize(len, vector<int>(len, -1));
			// 直接相连的边更新一下
			for (size_t i = 0; i < len; ++i)
			{
				for (size_t j = 0; j < len; ++j)
				{
					if (_weightmatrix[i][j] != MaxSize)
					{
						vvpPath[i][j] = i;
					}
					if (i == j)
					{
						vvDist[i][j] = W();
					}
				}
			}
			for (int k = 0; k < len; ++k)
			{
				for (int i = 0; i < len; ++i)
				{
					//每次更新从i出去的点
					for (int j = 0; j < len; ++j)
					{
					
							// k 作为的中间点尝试去更新i->j的路径
						if (vvDist[i][k] != MaxSize && vvDist[k][j] != MaxSize
							&& vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
						{
							vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
							vvpPath[i][j] = vvpPath[k][j];
						}
					}
				}
			}
			// 打印权值和路径矩阵观察数据
			for (size_t i = 0; i < len; ++i)
			{
				for (size_t j = 0; j < len; ++j)
				{
					if (vvDist[i][j] == MaxSize)
					{
						//cout << "*" << " ";
						printf("%3c", '*');
					}
					else
					{
						//cout << vvDist[i][j] << " ";
						printf("%3d", vvDist[i][j]);
					}
				}
				cout << endl;
			}
			cout << endl;

			for (size_t i = 0; i < len; ++i)
			{
				for (size_t j = 0; j < len; ++j)
				{
					//cout << vvParentPath[i][j] << " ";
					printf("%3d", vvpPath[i][j]);
				}
				cout << endl;
			}
			cout << "=================================" << endl;		
		}

总结


图论到此为止~文章来源地址https://www.toymoban.com/news/detail-545940.html

  • 喜欢就收藏
  • 认同就点赞
  • 支持就关注
  • 疑问就评论

到了这里,关于【C++ 实现】图论概念,最小生成树,单/多源最短路径实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树

    ✅作者简介:热爱后端语言的大学生,CSDN内容合伙人 ✨精品专栏:C++面向对象 🔥系列专栏:算法百炼成神 本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面

    2024年02月03日
    浏览(45)
  • 数学建模十大算法04—图论算法(最短路径、最小生成树、最大流问题、二分图)

    一、最短路径问题 从图中的某个顶点出发,到达另一个顶点的 所经过的边的权重之和最小 的一条路径。 1.1 两个指定顶点之间的最短路径 问题如下:给出了一个连接若干个城镇的铁路网络,在这个网络的两个指定城镇间,求一条最短铁路线。 1.1.1 Dijkstra算法 迪杰斯特拉(D

    2024年02月02日
    浏览(69)
  • leetcode&lintcode分类刷题:图论(三、多源最小距离问题)

    1、本次总结的题目通常是多个源头节点分别求解到达目标节点的最小距离,目标节点可能为多个,也可能为一个;要采用 广度优先搜索 的方法,但先提前入队的不是源头节点了,而是目标节点,由目标节点为基准一圈一圈的更新能够达到的“新目标”位置,每一圈更新能够

    2024年02月07日
    浏览(36)
  • 【算法导论】图论(图的基本概念,图上的深度优先搜索(DFS),广度优先搜索(BFS),最小生成树(MST)及Prim,Kruskal算法)

    图(Graph)是一种包含节点与节点的边的集合,记作G=(V,E),V是节点的集合,E是边的集合。 有向图 一个有向图G=(V,E),E中每个元素是V上的一个二值关系:一条从a出发的连向b的边e可以记作一个 有序 对e = (a,b) 。 无向图 一个无向图G=(V,E),E的每个元素e可以表示V上的一个 无序 对,记

    2024年02月03日
    浏览(49)
  • Floyd_Warshall算法详解及实现(多源最短路径)

    小明要去这样的城市旅游(城市交通图如下),为了减轻经济负担,小明想知道任意两个城市之间的最短路径。 从图中,可以得到:小明打算去4个城市(节点数)旅游,而这4个城市之间有8条公路(边数)连通,公路上的数字(权重)表示这条公路的长短。 现在需要设计一

    2023年04月17日
    浏览(35)
  • 2304. 网格中的最小路径代价 : 从「图论最短路」过渡到「O(1) 空间的原地模拟」

    这是 LeetCode 上的 「2304. 网格中的最小路径代价」 ,难度为 「中等」 。 Tag : 「最短路」、「图」、「模拟」、「序列 DP」、「动态规划」 给你一个下标从 0 开始的整数矩阵 grid ,矩阵大小为 m x n ,由从 0 到 的不同整数组成。 你可以在此矩阵中,从一个单元格移动到下一行

    2024年01月23日
    浏览(48)
  • [Daimayuan] 最短路计数(C++,DP,图论)

    题目描述 给出一个 N N N 个顶点 M M M 条边的无向无权图。 问从顶点 1 1 1 开始,到其他每个点的最短路有几条。 输入格式 第 1 1 1 行包含两个正整数 N N N , M M M 。 接下来 M M M 行,每行两个正整数 x , y x,y x , y 表示存在一条由顶点 x x x 到顶点 y y y 的边。(可能存在重边和自环

    2023年04月22日
    浏览(36)
  • 图论- 最小生成树

    一幅图可以有很多不同的生成树,比如下面这幅图,红色的边就组成了两棵不同的生成树: 对于加权图, 每条边都有权重(用最小生成树算法的现实场景中,图的边权重一般代表成本、距离这样的标量),所以每棵生成树都有一个权重和。 比如上图,右侧生成树的权重和显

    2024年04月25日
    浏览(34)
  • 图论——最小生成树

    想了解最小生成树,首先得明白什么是生成树。 生成树的概念: 包含连通图中所有的顶点,且任意两顶点之间有且仅有一条通路。 那什么是最小生成树? 最小生成树(Minimum Spanning Trees)的概念:连通图的一颗生成树(Spanning Tree)是包含图的所有顶点的连通无环子图(也就是一棵

    2023年04月13日
    浏览(32)
  • 算法提高-图论- 最小生成树

    和上题一摸一样,但是题意要求的out看起来需要特别处理,其实只要想清楚kruskal的性质就好 题意就是求最小生成树,因为边权都是正数,那么我们多选一条边必然会导致我们的代价增大 但如果题目说了边权为正或者负数,那么就不是最小生成树了,极端一点所有边都是负的

    2024年02月16日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包