图的拓扑排序(AOV网络)

这篇具有很好参考价值的文章主要介绍了图的拓扑排序(AOV网络)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

拓扑排序

概念

拓扑排序是对有向无环图的顶点的一种排序.

  • AOV网络 : 在有向图中, 用顶点表示活动或者任务, 弧表示活动或者任务间的优先关系, 则此有向图称为用顶点表示活动的网络(Activity On Vertex简称AOV网络).
  • 拓扑序列(Topolagical Order) : 在有向无环图中, 若存在顶点vi到顶点vj的路径, 那么在序列中顶点vi就排在顶点vj的前面, 称此序列为拓扑排序.
  • 拓扑排序(Topological Sort) : 将有向无环图的顶点按照它们之间的优先关系排成一个拓扑序列的操作称为拓扑排序.

拓扑排序可以解决先决条件问题, 即以某种线性顺序来组织多项任务, 使任务顺序完成.

拓扑序列应该满足 : 如果有向无环图G存在顶点vi到vj的一条路径, 那么在序列中顶点vi必在顶点vj之前.

aov网络,数据结构,排序算法,图论,拓扑排序,c++,数据结构

实现

拓扑排序的步骤如下 :

  1. 在有向图中任选一个入度为0的顶点(即没有前驱的顶点)并输出它.
  2. 删除该顶点以及该顶点的所有出边, 将其邻接顶点的入度减一, 重复上述步骤, 最后结果可能有两种情况 : (1) 当输出了全部顶点时, 拓扑排序成功, 得到该图的拓扑排序. (2) 当图中还有顶点没有输出时, 拓扑排序失败, 说明该图中含有环, 剩余顶点的入度均不为零.
  • 如何计算和存储顶点的入度?

  • 定义一个整形数组inDegreeSize, 数组元素表示的各顶点的入度, 随图中边数的减少而减少. 从逻辑上删除某顶点以及该顶点的所有出边的操作, 可通过对该顶点的后继顶点的入度减一来实现. 此外, 为了便于查找入度为零的顶点, 可以另设一个存储空间来暂存入度为零的顶点 (可以用栈或者队列, 当度为零的顶点出栈或者出队时, 将对应的后继顶点的入度减一, 再将新的入度为零的顶点入栈或者入队) .

拓扑排序算法描述如下 :

  1. 计算每一个顶点的入度, 存入inDegreeSize数组, 遍历inDegreeSize数组并将所有入度为零的顶点入队列或者栈.
  2. 若队列或者栈非空, 从队头或者栈顶取出一个入度为零的顶点并输出它, 将以该顶点为弧尾的所有邻接顶点(弧头)的入度减一, 若此时某个邻接顶点的入度为零, 便将其入队或者入栈.
  3. 重复步骤2, 直到队列或者栈为空. 此时, 若所有顶点均被输出, 拓扑排序成功有意义返回true; 否则, 还有顶点未被输出表示图中有环, 拓扑排序失败没有意义返回false.

注意:在下面的邻接表与邻接矩阵中有写法一与写法二, 比较推荐编写写法一因为代价更低. 之所以有写法一与写法二只是想说明拓扑排序不唯一.

邻接表(队列)
namespace AdjacentList
{
	template<typename W>
	struct Edge
	{	
		int _dsti; // 终点顶点的下标
		W _weight; // 边的权值

		struct Edge<W>* _next; // 下一个结点的指针

		Edge(int dsti, const W& weight)
			:_dsti(dsti)
			,_weight(weight)
			,_next(nullptr)
		{}
	};

	template<typename V, typename W,bool Directed = false>
	class Graph
	{
		using Edge = Edge<W>;
	private:
		std::vector<V> _vertexSet; // 顶点的集合
		std::map<V, int> _vertexIndex; // 顶点映射下标
		std::vector<Edge*> _table; // 出度顶点表
    }
}

写法一:

aov网络,数据结构,排序算法,图论,拓扑排序,c++,数据结构

	void TestGraph()
	{
        std::string aStr[] = {
			"V1","V2","V3","V4","V5","V6","V7","V8","V9"
		};
        
		Graph<std::string, int, true> dg(aStr,sizeof(aStr)/sizeof(aStr[0]));
        
		dg.AddEdge("V1", "V3", 1);
		dg.AddEdge("V2", "V3", 1);
		dg.AddEdge("V2", "V4", 1);
		dg.AddEdge("V2", "V7", 1);
		dg.AddEdge("V3", "V4", 1);
		dg.AddEdge("V3", "V5", 1);
		dg.AddEdge("V4", "V5", 1);
		dg.AddEdge("V4", "V6", 1);
		dg.AddEdge("V4", "V7", 1);
		dg.AddEdge("V5", "V6", 1);
		dg.AddEdge("V5", "V9", 1);
		dg.AddEdge("V6", "V9", 1);
		dg.AddEdge("V7", "V8", 1);
		dg.AddEdge("V8", "V9", 1);

		dg.TopologicalSort();
	}

aov网络,数据结构,排序算法,图论,拓扑排序,c++,数据结构

写法二:

aov网络,数据结构,排序算法,图论,拓扑排序,c++,数据结构

aov网络,数据结构,排序算法,图论,拓扑排序,c++,数据结构

邻接矩阵(栈)
namespace AdjacentMatrix
{
	template<class V,class W=int,W W_MAX=INT_MAX,bool Directed=false>
	class Graph
	{
	private:
		std::vector<V> _vertexs; // 顶点集合,下标找顶点

		std::vector<vector<W>> _matrix; // 邻接矩阵,顶点与顶点之间的权值

		YX::RedBlackTree<V, int> _findIndexTree; // 顶点与下标的映射,顶点找下标
    }
}

写法一:

aov网络,数据结构,排序算法,图论,拓扑排序,c++,数据结构

	void TestGraph()
	{
		std::string aStr[] = {
			"V1","V2","V3","V4","V5","V6","V7","V8","V9"
		};

		Graph<std::string, int, INT_MAX,true> dg(aStr,sizeof(aStr)/sizeof(aStr[0]));
		
		dg.AddEdge("V1", "V3", 1);
		dg.AddEdge("V2", "V3", 1);
		dg.AddEdge("V2", "V4", 1);
		dg.AddEdge("V2", "V7", 1);
		dg.AddEdge("V3", "V4", 1);
		dg.AddEdge("V3", "V5", 1);
		dg.AddEdge("V4", "V5", 1);
		dg.AddEdge("V4", "V6", 1);
		dg.AddEdge("V4", "V7", 1);
		dg.AddEdge("V5", "V6", 1);
		dg.AddEdge("V5", "V9", 1);
		dg.AddEdge("V6", "V9", 1);
		dg.AddEdge("V7", "V8", 1);
		dg.AddEdge("V8", "V9", 1);

		dg.TopologicalSort();
	}

aov网络,数据结构,排序算法,图论,拓扑排序,c++,数据结构

写法二:

aov网络,数据结构,排序算法,图论,拓扑排序,c++,数据结构

aov网络,数据结构,排序算法,图论,拓扑排序,c++,数据结构

总结

与图的遍历相同:

  • 图的每条边弧处理一次
  • 图的每个顶点访问一次

采用邻接表表示时, 时间复杂度为O(n+e).

采用邻接矩阵表示时, 时间复杂度O(n2).

空间复杂度都为O(n).文章来源地址https://www.toymoban.com/news/detail-813825.html

源代码

邻接表

namespace AdjacentList
{
	template<typename W>
	struct Edge
	{
		int _dsti;
		W _weight;

		struct Edge<W>* _next;

		Edge(int dsti, const W& weight)
			:_dsti(dsti)
			, _weight(weight)
			, _next(nullptr)
		{}
	};

	template<typename V, typename W, bool Directed = false>
	class Graph
	{
		using Edge = Edge<W>;
	private:
		std::vector<V> _vertexSet; // 顶点的集合
		std::map<V, int> _vertexIndex; // 顶点映射下标
		std::vector<Edge*> _table; // 出度边表
	public:

		typedef Graph<V, W, Directed> Self;

		Graph() = default;

		Graph(const V* a, int n)
		{
			for (int i = 0; i < n; i++)
			{
				AddVertex(a[i]);
			}
		}

		int GetVertexIndex(const V& v)
		{
			typename std::map<V, int>::iterator pos = _vertexIndex.find(v);
			if (pos != _vertexIndex.end())
			{
				return pos->second;
			}
			else
			{
				return -1;
			}
		}

		bool AddVertex(const V& v)
		{
			if (GetVertexIndex(v) != -1)
				return false;

			_vertexSet.push_back(v);

			_vertexIndex.insert(std::make_pair(v, _vertexSet.size() - 1));

			_table.push_back(nullptr);

			return true;
		}

		bool _AddEdge(int srci, int dsti, const W& weight)
		{
			Edge* edge = new Edge(dsti, weight);

			// 头插
			edge->_next = _table[srci];
			_table[srci] = edge;

			// 无向图
			if (!Directed)
			{
				edge = new Edge(srci, weight);

				edge->_next = _table[dsti];
				_table[dsti] = edge;
			}

			return true;
		}

		bool AddEdge(const V& src, const V& dst, const W& weight)
		{
			int srci = GetVertexIndex(src);
			int dsti = GetVertexIndex(dst);

			// 顶点不在图中,添加边失败
			if (srci == -1 || dsti == -1)
				return false;

			//Edge* edge = new Edge(dsti, weight);

			 头插
			//edge->_next = _table[srci];
			//_table[srci] = edge;

			 无向图
			//if (!Directed)
			//{
			//	edge = new Edge(srci, weight);

			//	edge->_next = _table[dsti];
			//	_table[dsti] = edge;
			//}

			return _AddEdge(srci, dsti, weight);
		}

		//bool TopologicalSort()
		//{
		//	if (!Directed)
		//		return false;

		//	// 记录顶点的入度大小
		//	std::vector<int> inDegreeSize(_vertexSet.size(), 0);
		//	// 记录顶点是否被访问过(即是否入过队或者栈)
		//	std::vector<bool> visited(_vertexSet.size(), false);

		//	// 顶点个数
		//	int n = static_cast<int>(_vertexSet.size());

		//	// 获取图中所有顶点对应的入度大小
		//	for (int i = 0; i < n; i++)
		//	{
		//		Edge* curr = _table[i];

		//		while (curr != nullptr)
		//		{	
		//			inDegreeSize[curr->_dsti]++;
		//			curr = curr->_next;
		//		}
		//	}
		//	
		//	// 记录入度为零的顶点
		//	std::queue<int> q;

		//	// 将入度为零的顶点下标入队或者入栈
		//	for (int i = 0; i < n; i++)
		//	{
		//		if (inDegreeSize[i] == 0 && !visited[i])
		//		{
		//			q.push(i);
		//			visited[i] = true;
		//		}
		//	}

		//	while (!q.empty())
		//	{
		//		// 先遍历某入度为零的顶点
		//		int front = q.front();
		//		q.pop();
		//		std::cout << _vertexSet[front] << "--->";// << std::endl;

		//		// 再将该顶点对应的后继顶点的入度减一
		//		Edge* curr = _table[front];

		//		while (curr != nullptr)
		//		{
		//			inDegreeSize[curr->_dsti]--;

		//			curr = curr->_next;
		//		}

		//		// 最后将没有入过队或者栈的入度为零的顶点入队
		//		for (int i = 0; i < n; i++)
		//		{
		//			if (inDegreeSize[i] == 0 && !visited[i])
		//			{
		//				q.push(i);
		//				visited[i] = true;
		//			}
		//		}
		//	}

		//	// 判断是否还有顶点没有访问到
		//	for (int i = 0; i < n; i++)
		//	{
		//		if (inDegreeSize[i] != 0 && !visited[i])
		//		{
		//			printf("\nTopological sorting doesn't make sense\n");
		//			return false;
		//		}
		//	}

		//	printf("\nTopological sorting makes sense\n");
		//	return true;
		//}
		
		bool TopologicalSort()
		{
			if (!Directed)
				return false;

			// 记录顶点的入度大小
			std::vector<int> inDegreeSize(_vertexSet.size(), 0);

			// 顶点个数
			int n = static_cast<int>(_vertexSet.size());

			// 获取图中所有顶点对应的入度大小
			for (int i = 0; i < n; i++)
			{
				Edge* curr = _table[i];

				while (curr != nullptr)
				{
					inDegreeSize[curr->_dsti]++;
					curr = curr->_next;
				}
			}

			// 记录入度为零的顶点
			std::queue<int> q;

			// 将入度为零的顶点下标入队或者入栈
			for (int i = 0; i < n; i++)
			{
				if (inDegreeSize[i] == 0)
				{
					q.push(i);
				}
			}

			while (!q.empty())
			{
				// 先遍历某入度为零的顶点
				int front = q.front();
				q.pop();
				std::cout << _vertexSet[front] << "--->";// << std::endl;

				// 再将该顶点对应的后继顶点的入度减一
				Edge* curr = _table[front];

				while (curr != nullptr)
				{
					// 如果有顶点的入度被减为零时,则该顶点入队或者入栈
					if (--inDegreeSize[curr->_dsti] == 0)
					{
						q.push(curr->_dsti);
					}
					curr = curr->_next;
				}
			}

			// 判断是否还有顶点没有访问到
			for (int i = 0; i < n; i++)
			{
				if (inDegreeSize[i] != 0)
				{
					printf("\nTopological sorting doesn't make sense\n");
					return false;
				}
			}

			printf("\nTopological sorting makes sense\n");
			return true;
		}
	};

	void TestGraph()
	{
		Graph<std::string, int, true> dg;

		dg.AddVertex("V1");
		dg.AddVertex("V2");
		dg.AddVertex("V3");
		dg.AddVertex("V4");
		dg.AddVertex("V5");
		dg.AddVertex("V6");
		dg.AddVertex("V7");
		dg.AddVertex("V8");
		dg.AddVertex("V9");

		dg.AddEdge("V1", "V3", 1);
		dg.AddEdge("V2", "V3", 1);
		dg.AddEdge("V2", "V4", 1);
		dg.AddEdge("V2", "V7", 1);
		dg.AddEdge("V3", "V4", 1);
		dg.AddEdge("V3", "V5", 1);
		dg.AddEdge("V4", "V5", 1);
		dg.AddEdge("V4", "V6", 1);
		dg.AddEdge("V4", "V7", 1);
		dg.AddEdge("V5", "V6", 1);
		dg.AddEdge("V5", "V9", 1);
		dg.AddEdge("V6", "V9", 1);
		dg.AddEdge("V7", "V8", 1);
		dg.AddEdge("V8", "V9", 1);

		dg.TopologicalSort();
	}
}

邻接矩阵

namespace AdjacentMatrix
{
	template<typename V, typename W, W W_MAX, bool Directed = false>
	class Graph
	{
	private:
		std::vector<V> _vertexSet;
		std::map<V, int> _vertexIndex;
		std::vector<std::vector<W>> _matrix;
	public:

		typedef Graph<V, W, W_MAX, Directed> Self;

		Graph() = default;

		Graph(const V* a, int n)
		{
			for (int i = 0; i < n; i++)
			{
				AddVertex(a[i]);
			}
		}

		int GetVertexIndex(const V& v)
		{
			typename std::map<V, int>::iterator pos = _vertexIndex.find(v);
			if (pos != _vertexIndex.end())
			{
				return pos->second;
			}
			else
			{
				return -1;
			}
		}

		bool AddVertex(const V& v)
		{
			// 顶点存在不需要继续增加
			if (GetVertexIndex(v) != -1)
				return false;

			_vertexSet.push_back(v);
			_vertexIndex.insert(std::make_pair(v, _vertexSet.size() - 1));

			// 先在原有的行上一列
			for (int i = 0; i < _matrix.size(); i++)
			{
				_matrix[i].push_back(W_MAX);
			}

			// 增加一行
			_matrix.push_back(std::vector<W>(_vertexSet.size(), W_MAX));

			return true;
		}

		bool AddEdge(const V& src, const V& dst, const W& weight)
		{
			int srci = GetVertexIndex(src);
			int dsti = GetVertexIndex(dst);

			// 顶点不在图中,添加边失败
			if (srci == -1 || dsti == -1)
				return false;

			//_matrix[srci][dsti] = weight;

			 如果为无向图,则需要再添加一条dst->src的边
			//if (!Directed)
			//{
			//	_matrix[dsti][srci] = weight;
			//}

			//return true;

			return _AddEdge(srci, dsti, weight);
		}

		bool _AddEdge(int srci, int dsti, const W& weight)
		{
			// 顶点不在图中,添加边失败
			if (srci == -1 || dsti == -1)
				return false;

			_matrix[srci][dsti] = weight;

			// 如果为无向图,则需要再添加一条dst->src的边
			if (!Directed)
			{
				_matrix[dsti][srci] = weight;
			}

			return true;
		}

		//bool TopologicalSort()
		//{
		//	if (!Directed)
		//		return false;

		//	// 记录顶点的入度大小
		//	std::vector<int> inDegreeSize(_vertexSet.size(), 0);
		//	// 记录顶点是否被访问过(即是否入过队或者栈)
		//	std::vector<bool> visited(_vertexSet.size(), false);

		//	// 顶点个数
		//	int n = static_cast<int>(_vertexSet.size());
		//	
		//	// 统计图中所有顶点的入度数
		//	for (int i = 0; i < n; i++)
		//	{
		//		for (int j = 0; j < n; j++)
		//		{
		//			if (_matrix[i][j] != W_MAX)
		//			{
		//				inDegreeSize[j]++;
		//			}
		//		}
		//	}

		//	// 将入度为零的顶点压入栈中
		//	std::stack<int> st;
		//	for (int i = 0; i < n; i++)
		//	{
		//		if (inDegreeSize[i] == 0 && !visited[i])
		//		{
		//			st.push(i);
		//			visited[i] = true;
		//		}
		//	}
		//	// 栈不为空时,将存储在栈中入度为零的顶点输出
		//	while (!st.empty())
		//	{
		//		int top = st.top();
		//		st.pop();
		//		// 输出栈顶元素
		//		std::cout << _vertexSet[top] << "--->";

		//		// 将以该顶点为弧尾的边对应顶点的入度减一
		//		for (int i = 0; i < n; i++)
		//		{
		//			if (top != i && _matrix[top][i] != W_MAX)
		//			{
		//				inDegreeSize[i]--;
		//			}
		//		}

		//		// 最后将没有入栈的入度为零的顶点入栈
		//		for (int i = 0; i < n; i++)
		//		{
		//			if (inDegreeSize[i] == 0 && !visited[i])
		//			{
		//				st.push(i);
		//				visited[i] = true;
		//			}
		//		}
		//	}

		//	// 判断是否还有顶点没有访问到
		//	for (int i = 0; i < n; i++)
		//	{
		//		if (inDegreeSize[i] != 0 && !visited[i])
		//		{
		//			printf("\nTopological sorting doesn't make sense\n");
		//			return false;
		//		}
		//	}

		//	printf("\nTopological sorting makes sense\n");
		//	return true;
		//}

		bool TopologicalSort()
		{
			if (!Directed)
				return false;

			// 记录顶点的入度大小
			std::vector<int> inDegreeSize(_vertexSet.size(), 0);
			// 顶点个数
			int n = static_cast<int>(_vertexSet.size());

			// 统计图中所有顶点的入度数
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (_matrix[i][j] != W_MAX)
					{
						inDegreeSize[j]++;
					}
				}
			}

			// 将入度为零的顶点压入栈中
			std::stack<int> st;
			for (int i = 0; i < n; i++)
			{
				if (inDegreeSize[i] == 0)
				{
					st.push(i);
				}
			}
			// 栈不为空时,将存储在栈中入度为零的顶点输出
			while (!st.empty())
			{
				int top = st.top();
				st.pop();
				// 输出栈顶元素
				std::cout << _vertexSet[top] << "--->";

				// 将以该顶点为弧尾的边对应顶点的入度减一
				for (int i = 0; i < n; i++)
				{
					if (top != i && _matrix[top][i] != W_MAX)
					{
						// 如果有顶点的入度被减为零时,则该顶点入队或者入栈
						if (--inDegreeSize[i] == 0)
						{
							st.push(i);
						}
					}
				}
			}

			// 判断是否还有顶点没有访问到
			for (int i = 0; i < n; i++)
			{
				if (inDegreeSize[i] != 0)
				{
					printf("\nTopological sorting doesn't make sense\n");
					return false;
				}
			}

			printf("\nTopological sorting makes sense\n");
			return true;
		}
	};

	void TestGraph()
	{
		std::string aStr[] = {
			"V1","V2","V3","V4","V5","V6","V7","V8","V9"
		};

		Graph<std::string, int, INT_MAX,true> dg(aStr,sizeof(aStr)/sizeof(aStr[0]));
		
		dg.AddEdge("V1", "V3", 1);
		dg.AddEdge("V2", "V3", 1);
		dg.AddEdge("V2", "V4", 1);
		dg.AddEdge("V2", "V7", 1);
		dg.AddEdge("V3", "V4", 1);
		dg.AddEdge("V3", "V5", 1);
		dg.AddEdge("V4", "V5", 1);
		dg.AddEdge("V4", "V6", 1);
		dg.AddEdge("V4", "V7", 1);
		dg.AddEdge("V5", "V6", 1);
		dg.AddEdge("V5", "V9", 1);
		dg.AddEdge("V6", "V9", 1);
		dg.AddEdge("V7", "V8", 1);
		dg.AddEdge("V8", "V9", 1);

		dg.TopologicalSort();
	}
}

到了这里,关于图的拓扑排序(AOV网络)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】图的应用:最小生成树;最短路径;有向无环图描述表达式;拓扑排序;逆拓扑排序;关键路径

    目录 1、最小生成树 1.1 概念  1.2 普利姆算法(Prim) 1.3 克鲁斯卡尔算法(Kruskal)  2、最短路径 2.1 迪杰斯特拉算法(Dijkstra) 2.2 弗洛伊德算法(Floyd)  2.3 BFS算法,Dijkstra算法,Floyd算法的对比 3、有向无环图描述表达式 3.1 有向无环图定义及特点 3.2 描述表达式 4、拓扑排序

    2024年02月07日
    浏览(50)
  • 有向无环图的应用—描述表达式、AOV网、AOE网

    目录 一、有向无环图描述表达式 二、拓扑排序 相关概念  实现方法  算法代码  补充 三、关键路径 相关概念  算法步骤  补充  四、总结图的应用我们都学了什么 有向无环图 :若一个有向图中不存在环,则称为有向无环图,简称DAG图。  对于一个表达式 ( (a+b)* ( b*(c+d)

    2024年02月12日
    浏览(47)
  • 数据结构-拓扑排序

    一个无环的有向图称作有向无环图(Directed Acycline Graph),简称DAG图。 DAG图是描述含有公共子式的表达式的有效工具。 在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,称这种有向图为顶 点表示活动的网,简称AOV网。 AOV网中不能出现回路,而判

    2024年02月08日
    浏览(41)
  • 数据结构--拓扑排序

    A O V ⽹ color{red}AOV⽹ A O V ⽹ (Activity On Vertex NetWork,⽤顶点表示活动的⽹): ⽤ D A G 图 color{red}DAG图 D A G 图 (有向⽆环图)表示⼀个⼯程。顶点表示活动,有向边 V i , V j V_i, V_j V i ​ , V j ​ 表示活动Vi必须先于活动 V j V_j V j ​ 进⾏ 注:如果图中存在环路就不是 A O V 网 c

    2024年02月12日
    浏览(44)
  • 教学计划编制问题(数据结构 有向图 拓扑排序)

     本文对以下教学计划编制问题的解决作出实现,主要使用c语言(带一点cpp),开发环境为codeblocks 17.12,希望对各位读者有所帮助。(源码和数据文件可在主页获取,同时还有使用视频文件压缩包,数据文件需要和exe在同一目录下,结合某读者的意见同时放到github了 ) 地址如下

    2024年02月09日
    浏览(56)
  • python算法与数据结构(搜索算法和拓扑排序算法)---深度优先搜索

    了解树/图的 深度遍历,宽度遍历 基本原理; 会使用python语言编写 深度遍历,广度遍历 代码; 掌握 拓扑排序算法 搜索引擎 提到搜索两个子,大家都应该会想到搜索引擎,搜索引擎的基本工作步骤; 网页爬取 — 数据预处理 — 排序 — 查询 第一步,网页爬取,非常重要,

    2024年01月20日
    浏览(51)
  • 【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS)

    有向图(Directed Graph),也被称为有向图形或方向图,是一种图的类型。在有向图中,图中的边具有方向,从一个顶点指向另一个顶点。 在有向图中,每个顶点表示一个实体,而有向边则表示实体之间的关系或连接。这种有方向性的边表明了连接的起点和终点之间的单向关系

    2024年02月09日
    浏览(50)
  • 数据结构拓扑排序以及关键路径(出度邻接表)C语言 完整代码

    现实生活中一项工程通常会拆分成多个部分来进行,这些部分有些相互之间有发生的前提关系,还有些可以同时发生且不会互相打扰,但是合理且充分的利用时间来完成项目是一个问题。在项目完成的过程中,那些项目的完成时间被压缩可以压缩工程的总时间,以便于提高整

    2024年02月04日
    浏览(49)
  • 【数据结构】拓扑网络(AOE算法举例+源码)

    博主介绍:✌专研于前后端领域优质创作者、本质互联网精神开源贡献答疑解惑、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战,深受全网粉丝喜爱与支持✌有需要可以联系作者我哦! 🍅文末获取源码联系🍅 👇🏻 精彩专栏

    2024年02月22日
    浏览(48)
  • 图的拓扑排序

            拓扑排序是一个 有向无环图(有向图、弧不形成闭环) 的所有顶点的线性序列。该线性序列中,图的每个顶点只出现一次,若顶点A到顶点B之间存在有向弧v1,v2,则顶点A一定在顶点B前面。             图的拓扑排序实现很简单,基本操作思想:         1、开

    2024年02月13日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包