圖的拓?fù)渑判?AOV網(wǎng)絡(luò))

這篇具有很好參考價值的文章主要介紹了圖的拓?fù)渑判?AOV網(wǎng)絡(luò))。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

拓?fù)渑判?/h3>

概念

拓?fù)渑判蚴菍τ邢驘o環(huán)圖的頂點(diǎn)的一種排序.

AOV網(wǎng)絡(luò) : 在有向圖中, 用頂點(diǎn)表示活動或者任務(wù), 弧表示活動或者任務(wù)間的優(yōu)先關(guān)系, 則此有向圖稱為用頂點(diǎn)表示活動的網(wǎng)絡(luò)(Activity On Vertex簡稱AOV網(wǎng)絡(luò)).
拓?fù)湫蛄?Topolagical Order) : 在有向無環(huán)圖中, 若存在頂點(diǎn)v_i到頂點(diǎn)v_j的路徑, 那么在序列中頂點(diǎn)v_i就排在頂點(diǎn)v_j的前面, 稱此序列為拓?fù)渑判?
拓?fù)渑判?Topological Sort) : 將有向無環(huán)圖的頂點(diǎn)按照它們之間的優(yōu)先關(guān)系排成一個拓?fù)湫蛄械牟僮鞣Q為拓?fù)渑判?

拓?fù)渑判蚩梢越鉀Q先決條件問題, 即以某種線性順序來組織多項(xiàng)任務(wù), 使任務(wù)順序完成.

拓?fù)湫蛄袘?yīng)該滿足 : 如果有向無環(huán)圖G存在頂點(diǎn)v_i到v_j的一條路徑, 那么在序列中頂點(diǎn)v_i必在頂點(diǎn)v_j之前.

aov網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),排序算法,圖論,拓?fù)渑判?c++,數(shù)據(jù)結(jié)構(gòu)

實(shí)現(xiàn)

拓?fù)渑判虻牟襟E如下 :

在有向圖中任選一個入度為0的頂點(diǎn)(即沒有前驅(qū)的頂點(diǎn))并輸出它.

刪除該頂點(diǎn)以及該頂點(diǎn)的所有出邊, 將其鄰接頂點(diǎn)的入度減一, 重復(fù)上述步驟, 最后結(jié)果可能有兩種情況 : (1) 當(dāng)輸出了全部頂點(diǎn)時, 拓?fù)渑判虺晒? 得到該圖的拓?fù)渑判? (2) 當(dāng)圖中還有頂點(diǎn)沒有輸出時, 拓?fù)渑判蚴? 說明該圖中含有環(huán), 剩余頂點(diǎn)的入度均不為零.

如何計(jì)算和存儲頂點(diǎn)的入度?
定義一個整形數(shù)組inDegreeSize, 數(shù)組元素表示的各頂點(diǎn)的入度, 隨圖中邊數(shù)的減少而減少. 從邏輯上刪除某頂點(diǎn)以及該頂點(diǎn)的所有出邊的操作, 可通過對該頂點(diǎn)的后繼頂點(diǎn)的入度減一來實(shí)現(xiàn). 此外, 為了便于查找入度為零的頂點(diǎn), 可以另設(shè)一個存儲空間來暫存入度為零的頂點(diǎn) (可以用?；蛘哧?duì)列, 當(dāng)度為零的頂點(diǎn)出棧或者出隊(duì)時, 將對應(yīng)的后繼頂點(diǎn)的入度減一, 再將新的入度為零的頂點(diǎn)入?；蛘呷腙?duì)) .

拓?fù)渑判蛩惴枋鋈缦?:

計(jì)算每一個頂點(diǎn)的入度, 存入inDegreeSize數(shù)組, 遍歷inDegreeSize數(shù)組并將所有入度為零的頂點(diǎn)入隊(duì)列或者棧.

若隊(duì)列或者棧非空, 從隊(duì)頭或者棧頂取出一個入度為零的頂點(diǎn)并輸出它, 將以該頂點(diǎn)為弧尾的所有鄰接頂點(diǎn)(弧頭)的入度減一, 若此時某個鄰接頂點(diǎn)的入度為零, 便將其入隊(duì)或者入棧.

重復(fù)步驟2, 直到隊(duì)列或者棧為空. 此時, 若所有頂點(diǎn)均被輸出, 拓?fù)渑判虺晒τ幸饬x返回true; 否則, 還有頂點(diǎn)未被輸出表示圖中有環(huán), 拓?fù)渑判蚴]有意義返回false.

注意:在下面的鄰接表與鄰接矩陣中有寫法一與寫法二, 比較推薦編寫寫法一因?yàn)榇鷥r更低. 之所以有寫法一與寫法二只是想說明拓?fù)渑判虿晃ㄒ?

鄰接表(隊(duì)列)

namespace AdjacentList
{
	template<typename W>
	struct Edge
	{	
		int _dsti; // 終點(diǎn)頂點(diǎn)的下標(biāo)
		W _weight; // 邊的權(quán)值

		struct Edge<W>* _next; // 下一個結(jié)點(diǎn)的指針

		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; // 頂點(diǎn)的集合
		std::map<V, int> _vertexIndex; // 頂點(diǎn)映射下標(biāo)
		std::vector<Edge*> _table; // 出度頂點(diǎn)表
    }
}

寫法一:

aov網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),排序算法,圖論,拓?fù)渑判?c++,數(shù)據(jù)結(jié)構(gòu)

	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網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),排序算法,圖論,拓?fù)渑判?c++,數(shù)據(jù)結(jié)構(gòu)

寫法二:

aov網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),排序算法,圖論,拓?fù)渑判?c++,數(shù)據(jù)結(jié)構(gòu)

鄰接矩陣(棧)

namespace AdjacentMatrix
{
	template<class V,class W=int,W W_MAX=INT_MAX,bool Directed=false>
	class Graph
	{
	private:
		std::vector<V> _vertexs; // 頂點(diǎn)集合，下標(biāo)找頂點(diǎn)

		std::vector<vector<W>> _matrix; // 鄰接矩陣，頂點(diǎn)與頂點(diǎn)之間的權(quán)值

		YX::RedBlackTree<V, int> _findIndexTree; // 頂點(diǎn)與下標(biāo)的映射，頂點(diǎn)找下標(biāo)
    }
}

寫法一:

aov網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),排序算法,圖論,拓?fù)渑判?c++,數(shù)據(jù)結(jié)構(gòu)

	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網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),排序算法,圖論,拓?fù)渑判?c++,數(shù)據(jù)結(jié)構(gòu)

寫法二:

aov網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),排序算法,圖論,拓?fù)渑判?c++,數(shù)據(jù)結(jié)構(gòu)

總結(jié)

與圖的遍歷相同:

圖的每條邊弧處理一次
圖的每個頂點(diǎn)訪問一次

采用鄰接表表示時, 時間復(fù)雜度為O(n+e).

采用鄰接矩陣表示時, 時間復(fù)雜度O(n²).

空間復(fù)雜度都為O(n).文章來源地址http://www.zghlxwxcb.cn/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; // 頂點(diǎn)的集合
		std::map<V, int> _vertexIndex; // 頂點(diǎn)映射下標(biāo)
		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);

			// 頂點(diǎn)不在圖中,添加邊失敗
			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;

		//	// 記錄頂點(diǎn)的入度大小
		//	std::vector<int> inDegreeSize(_vertexSet.size(), 0);
		//	// 記錄頂點(diǎn)是否被訪問過(即是否入過隊(duì)或者棧)
		//	std::vector<bool> visited(_vertexSet.size(), false);

		//	// 頂點(diǎn)個數(shù)
		//	int n = static_cast<int>(_vertexSet.size());

		//	// 獲取圖中所有頂點(diǎn)對應(yīng)的入度大小
		//	for (int i = 0; i < n; i++)
		//	{
		//		Edge* curr = _table[i];

		//		while (curr != nullptr)
		//		{	
		//			inDegreeSize[curr->_dsti]++;
		//			curr = curr->_next;
		//		}
		//	}
		//	
		//	// 記錄入度為零的頂點(diǎn)
		//	std::queue<int> q;

		//	// 將入度為零的頂點(diǎn)下標(biāo)入隊(duì)或者入棧
		//	for (int i = 0; i < n; i++)
		//	{
		//		if (inDegreeSize[i] == 0 && !visited[i])
		//		{
		//			q.push(i);
		//			visited[i] = true;
		//		}
		//	}

		//	while (!q.empty())
		//	{
		//		// 先遍歷某入度為零的頂點(diǎn)
		//		int front = q.front();
		//		q.pop();
		//		std::cout << _vertexSet[front] << "--->";// << std::endl;

		//		// 再將該頂點(diǎn)對應(yīng)的后繼頂點(diǎn)的入度減一
		//		Edge* curr = _table[front];

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

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

		//		// 最后將沒有入過隊(duì)或者棧的入度為零的頂點(diǎn)入隊(duì)
		//		for (int i = 0; i < n; i++)
		//		{
		//			if (inDegreeSize[i] == 0 && !visited[i])
		//			{
		//				q.push(i);
		//				visited[i] = true;
		//			}
		//		}
		//	}

		//	// 判斷是否還有頂點(diǎn)沒有訪問到
		//	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;

			// 記錄頂點(diǎn)的入度大小
			std::vector<int> inDegreeSize(_vertexSet.size(), 0);

			// 頂點(diǎn)個數(shù)
			int n = static_cast<int>(_vertexSet.size());

			// 獲取圖中所有頂點(diǎn)對應(yīng)的入度大小
			for (int i = 0; i < n; i++)
			{
				Edge* curr = _table[i];

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

			// 記錄入度為零的頂點(diǎn)
			std::queue<int> q;

			// 將入度為零的頂點(diǎn)下標(biāo)入隊(duì)或者入棧
			for (int i = 0; i < n; i++)
			{
				if (inDegreeSize[i] == 0)
				{
					q.push(i);
				}
			}

			while (!q.empty())
			{
				// 先遍歷某入度為零的頂點(diǎn)
				int front = q.front();
				q.pop();
				std::cout << _vertexSet[front] << "--->";// << std::endl;

				// 再將該頂點(diǎn)對應(yīng)的后繼頂點(diǎn)的入度減一
				Edge* curr = _table[front];

				while (curr != nullptr)
				{
					// 如果有頂點(diǎn)的入度被減為零時,則該頂點(diǎn)入隊(duì)或者入棧
					if (--inDegreeSize[curr->_dsti] == 0)
					{
						q.push(curr->_dsti);
					}
					curr = curr->_next;
				}
			}

			// 判斷是否還有頂點(diǎn)沒有訪問到
			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)
		{
			// 頂點(diǎn)存在不需要繼續(xù)增加
			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);

			// 頂點(diǎn)不在圖中,添加邊失敗
			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)
		{
			// 頂點(diǎn)不在圖中,添加邊失敗
			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;

		//	// 記錄頂點(diǎn)的入度大小
		//	std::vector<int> inDegreeSize(_vertexSet.size(), 0);
		//	// 記錄頂點(diǎn)是否被訪問過(即是否入過隊(duì)或者棧)
		//	std::vector<bool> visited(_vertexSet.size(), false);

		//	// 頂點(diǎn)個數(shù)
		//	int n = static_cast<int>(_vertexSet.size());
		//	
		//	// 統(tǒng)計(jì)圖中所有頂點(diǎn)的入度數(shù)
		//	for (int i = 0; i < n; i++)
		//	{
		//		for (int j = 0; j < n; j++)
		//		{
		//			if (_matrix[i][j] != W_MAX)
		//			{
		//				inDegreeSize[j]++;
		//			}
		//		}
		//	}

		//	// 將入度為零的頂點(diǎn)壓入棧中
		//	std::stack<int> st;
		//	for (int i = 0; i < n; i++)
		//	{
		//		if (inDegreeSize[i] == 0 && !visited[i])
		//		{
		//			st.push(i);
		//			visited[i] = true;
		//		}
		//	}
		//	// 棧不為空時,將存儲在棧中入度為零的頂點(diǎn)輸出
		//	while (!st.empty())
		//	{
		//		int top = st.top();
		//		st.pop();
		//		// 輸出棧頂元素
		//		std::cout << _vertexSet[top] << "--->";

		//		// 將以該頂點(diǎn)為弧尾的邊對應(yīng)頂點(diǎn)的入度減一
		//		for (int i = 0; i < n; i++)
		//		{
		//			if (top != i && _matrix[top][i] != W_MAX)
		//			{
		//				inDegreeSize[i]--;
		//			}
		//		}

		//		// 最后將沒有入棧的入度為零的頂點(diǎn)入棧
		//		for (int i = 0; i < n; i++)
		//		{
		//			if (inDegreeSize[i] == 0 && !visited[i])
		//			{
		//				st.push(i);
		//				visited[i] = true;
		//			}
		//		}
		//	}

		//	// 判斷是否還有頂點(diǎn)沒有訪問到
		//	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;

			// 記錄頂點(diǎn)的入度大小
			std::vector<int> inDegreeSize(_vertexSet.size(), 0);
			// 頂點(diǎn)個數(shù)
			int n = static_cast<int>(_vertexSet.size());

			// 統(tǒng)計(jì)圖中所有頂點(diǎn)的入度數(shù)
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (_matrix[i][j] != W_MAX)
					{
						inDegreeSize[j]++;
					}
				}
			}

			// 將入度為零的頂點(diǎn)壓入棧中
			std::stack<int> st;
			for (int i = 0; i < n; i++)
			{
				if (inDegreeSize[i] == 0)
				{
					st.push(i);
				}
			}
			// 棧不為空時,將存儲在棧中入度為零的頂點(diǎn)輸出
			while (!st.empty())
			{
				int top = st.top();
				st.pop();
				// 輸出棧頂元素
				std::cout << _vertexSet[top] << "--->";

				// 將以該頂點(diǎn)為弧尾的邊對應(yīng)頂點(diǎn)的入度減一
				for (int i = 0; i < n; i++)
				{
					if (top != i && _matrix[top][i] != W_MAX)
					{
						// 如果有頂點(diǎn)的入度被減為零時,則該頂點(diǎn)入隊(duì)或者入棧
						if (--inDegreeSize[i] == 0)
						{
							st.push(i);
						}
					}
				}
			}

			// 判斷是否還有頂點(diǎn)沒有訪問到
			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();
	}
}

到了這里，關(guān)于圖的拓?fù)渑判?AOV網(wǎng)絡(luò))的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！