快捷導航

C++圖論基礎(chǔ)之圖的遍歷與最小生成樹算法詳解

更新時間：2026年02月23日 10:57:46 作者：落羽的落羽

這篇文章主要介紹了C++圖論基礎(chǔ)之圖的遍歷與最小生成樹算法,它是學習更復雜圖算法的基石,我們將通過代碼模板與圖解,幫助你掌握如何高效地遍歷圖結(jié)構(gòu),需要的朋友可以參考下

一、圖的遍歷

遍歷一個圖，針對的是遍歷所有頂點。主要是兩種思路：廣度優(yōu)先（BFS）和深度優(yōu)先（DFS）
上一篇文章講過了圖可以用領(lǐng)接矩陣和領(lǐng)接表存儲邊，我們以領(lǐng)接矩陣的模版進行講解

1. BFS

圖的廣度優(yōu)先遍歷思路是：從起始頂點出發(fā)，先訪問當前頂點的所有直接鄰接頂點（一層），再依次訪問這些鄰接頂點的鄰接節(jié)點（下一層），以此類推，直到遍歷完所有可達頂點。
曾經(jīng)我們講二叉樹的廣度優(yōu)先遍歷時，是利用了隊列結(jié)構(gòu)，這里也是一樣的。每次隊頭元素出隊列時，隊頭元素頂點的所有領(lǐng)接頂點全部入隊列。為了防止一個頂點多次遍歷，還需要一個數(shù)組用于標記。

// 參數(shù)是遍歷的起始頂點
void BFS(const V& src)
{
	// 得到起始頂點的下標
	size_t srcindex = GetVertexIndex(src);
	// 防止一個頂點被多次遍歷，用一個數(shù)組標記被遍歷過的下標
	vector<bool> visited;
	visited.resize(_vertexs.size(), false);

	// 起點入隊列
	queue<int> q;
	q.push(srcindex);
	visited[srcindex] = true;

	cout << "BFS遍歷: ";
	while (!q.empty())
	{
		size_t front = q.front();
		// 打印出當前遍歷頂點
		cout << _vertexs[front] << ' ';

		// 隊頭元素出隊列
		q.pop();

		// 隊頭元素頂點所有沒遍歷過的相鄰頂點入隊列，在領(lǐng)接矩陣中查詢相鄰頂點
		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			if (visited[i] == false && _matrix[front][i] != MAX_W)
			{
				// 遍歷過的頂點標記為true
				visited[i] = true;
				q.push(i);
			}
		}
		
	}
	
	// 如果該圖不是連通圖，這種方法會使某些頂點沒遍歷到
	for (bool check : visited)
	{
		if (check == false)
		{
			cout << "該圖不是連通圖，還有未遍歷到的頂點";
		}
	}
	cout << endl;
}

2. DFS

圖的深度優(yōu)先遍歷核心思想是 “一條路走到黑”：從起始頂點出發(fā)，沿著一條路徑盡可能深地探索，直到無法繼續(xù)（遇到已訪問節(jié)點或無鄰接頂點），再回溯到上一個頂點，繼續(xù)探索其他未走的分支。為了防止一個頂點多次遍歷，也需要一個數(shù)組用于標記。

void _DFS(size_t srcIndex, vector<bool>& visited)
{
	// 當前遍歷頂點
	cout << _vertexs[srcIndex] << ' ';
	visited[srcIndex] = true;

	// 找srcIndex的相鄰頂點，遍歷下去
	for (size_t i = 0; i < _vertexs.size(); ++i)
	{
		if (visited[i] == false && _matrix[srcIndex][i] != MAX_W)
		{
			_DFS(i, visited);
		}
	}
}

void DFS(const V& src)
{
	// 得到起始頂點的下標
	size_t srcindex = GetVertexIndex(src);

	// 防止一個頂點被多次遍歷，用一個數(shù)組標記被遍歷過的下標
	vector<bool> visited;
	visited.resize(_vertexs.size(), false);

	cout << "DFS遍歷: ";
	_DFS(srcindex, visited);
	cout << endl;
}

3. 測試

我們用這張圖進行測試：

完整代碼：

#pragma once
#include<iostream>
#include<vector>
#include<map>
#include<queue>
using namespace std;

// 鄰接矩陣 圖
namespace Matrix
{
	// V頂點類型 W邊權(quán)值類型 MAX_W表示邊不存在的值 Direction表示圖是否有向
	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
	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;
			}

			// MAX_W 作為不存在邊的標識值
			// 初始化時默認沒有邊，邊需要一條一條手動添加，用AddEdge函數(shù)
			_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;
			}
		}

		// 添加一條邊，src和dst代表兩端頂點，w是權(quán)值
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);

			_matrix[srci][dsti] = w;
			//如果是無向圖，則[dsti][srci]也需添加邊
			if (Direction == false)
			{
				_matrix[dsti][srci] = w;
			}
		}

		// 參數(shù)是遍歷的起始頂點
		void BFS(const V& src)
		{
			// 得到起始頂點的下標
			size_t srcindex = GetVertexIndex(src);
			// 防止一個頂點被多次遍歷，用一個數(shù)組標記被遍歷過的下標
			vector<bool> visited;
			visited.resize(_vertexs.size(), false);

			// 起點入隊列
			queue<int> q;
			q.push(srcindex);
			visited[srcindex] = true;

			cout << "BFS遍歷: ";
			while (!q.empty())
			{
				size_t front = q.front();
				// 打印出當前遍歷頂點
				cout << _vertexs[front] << ' ';

				// 隊頭元素出隊列
				q.pop();

				// 隊頭元素頂點所有沒遍歷過的相鄰頂點入隊列，在領(lǐng)接矩陣中查詢相鄰頂點
				for (size_t i = 0; i < _vertexs.size(); ++i)
				{
					if (visited[i] == false && _matrix[front][i] != MAX_W)
					{
						// 遍歷過的頂點標記為true
						visited[i] = true;
						q.push(i);
					}
				}
				
			}

			// 如果該圖不是連通圖，這種方法會使某些頂點沒遍歷到
			for (bool check : visited)
			{
				if (check == false)
				{
					cout << "該圖不是連通圖，還有未遍歷到的頂點";
				}
			}
			cout << endl;
		}


		void _DFS(size_t srcIndex, vector<bool>& visited)
		{
			// 當前遍歷頂點
			cout << _vertexs[srcIndex] << ' ';
			visited[srcIndex] = true;

			// 找srcIndex的相鄰頂點，遍歷下去
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				if (visited[i] == false && _matrix[srcIndex][i] != MAX_W)
				{
					_DFS(i, visited);
				}
			}
		}

		void DFS(const V& src)
		{
			// 得到起始頂點的下標
			size_t srcindex = GetVertexIndex(src);

			// 防止一個頂點被多次遍歷，用一個數(shù)組標記被遍歷過的下標
			vector<bool> visited;
			visited.resize(_vertexs.size(), false);

			cout << "DFS遍歷: ";
			_DFS(srcindex, visited);
			cout << endl;
		}

	private:
		map<V, size_t> _vIndexMap;   // 每個頂點映射一個下標
		vector<V> _vertexs;			 // 頂點集合
		vector<vector<W>> _matrix;   // 領(lǐng)接矩陣 存儲邊
	};

}

int main()
{
	char arr[] = {'C','A','D','B','E'};
	Matrix::Graph<char, int> graph(arr, sizeof(arr)/sizeof(char));
	// 添加邊，權(quán)值不用管隨便寫的
	graph.AddEdge('A', 'D', 1);
	graph.AddEdge('D', 'B', 2);
	graph.AddEdge('D', 'E', 3);
	graph.AddEdge('B', 'E', 4);
	graph.AddEdge('B', 'C', 5);

	graph.BFS('A');
	graph.BFS('B');

	graph.DFS('A');
	graph.DFS('B');

	return 0;
}

結(jié)果分析，符合BFS與DFS的規(guī)則：

二、圖的最小生成樹算法

連通圖的每一棵生成樹，都是原圖的一個極大無環(huán)子圖。最小生成樹，就是指所有邊的權(quán)值加起來總權(quán)最小的生成樹，可以理解為用最小的成本構(gòu)成的生成樹。
最小生成樹也是生成樹，要符合：

要包括原圖的所有頂點，只能使用原圖中的邊來構(gòu)造
只能使用恰好n-1條邊來連接圖中n個頂點
選擇的n-1條邊不能構(gòu)成回路
邊的總權(quán)值要最小

構(gòu)造最小生成樹一般有兩種算法：克魯斯卡爾（Kruskal）算法、普里姆（Prim）算法，都是用了逐步求解的貪心策略。

1. Kruskal算法

這種算法的思路是“從小到大選邊”：將所有邊按權(quán)值從小到大排序，依次選擇最小的邊，若這條邊連接的兩個頂點不在同一個已連通集合中，就將這條邊加入生成樹；否則跳過，避免形成環(huán)。重復此過程，直到選夠n−1條邊。

判斷兩個頂點是否在一個已連通集合，可以利用并查集！詳見：并查集的原理與使用

typedef Graph<V, W, MAX_W, Direction> Self;
struct Edge
{
	V _srci;
	V _dsti;
	W _w;
	Edge(const V& srci, const V& dsti, const W& w)
		:_srci(srci)
		, _dsti(dsti)
		, _w(w)
	{ }
	bool operator<(const Edge& eg) const
	{
		return _w < eg._w;
	}
	bool operator>(const Edge& eg) const
	{
		return _w > eg._w;
	}
};
Graph() = default;
// 傳遞一個圖，作為構(gòu)造最小生成樹的結(jié)果。返回總權(quán)值
W Kruskal(Self& minTree)
{
	// 所有頂點拷貝，初始不帶任何邊
	minTree._vertexs = _vertexs;
	minTree._vIndexMap = _vIndexMap;
	minTree._matrix.resize(_vertexs.size());
	for (auto& e : minTree._matrix)
	{
		e.resize(_vertexs.size(), MAX_W);
	}
	// priority_queue用于按照權(quán)值排序邊
	priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
	for (size_t i = 0; i < _matrix.size(); ++i)
	{
		for (size_t j = 0; j < _matrix[i].size(); ++j)
		{
		    // 無向圖，只要判斷領(lǐng)接矩陣一半的邊
			if (i < j && _matrix[i][j] != MAX_W)
			{
				pq.push(Edge(i, j, _matrix[i][j]));
			}
		}
	}
	// 記錄總權(quán)值
	W total = W();
	// 貪心算法，從最小的邊開始選，將選出的邊兩端頂點放入一個集合
	// size記錄已選出邊數(shù)
	int size = 0;
	UnionFindSet ufs(_vertexs.size());
	while (!pq.empty())
	{
		Edge min = pq.top();
		pq.pop();
		// 邊兩端頂點不在一個集合，說明不會構(gòu)成環(huán)，則添加這條邊到最小生成樹，兩個頂點放到一個集合
		if (ufs.FindRoot(min._srci) != ufs.FindRoot(min._dsti))
		{
			minTree.AddEdge(min._srci, min._dsti, min._w);
			total += min._w;
			size++;
			ufs.Union(min._srci, min._dsti);
		}
	}
	// 若size不等于n-1，說明構(gòu)建最小生成樹失敗，返回一個默認值W()
	if (size == _vertexs.size() - 1)
	{
		return total;
	}
	else
	{
		return W();
	}
}

2. Prim算法

Prim算法，是按點貪心：X集合存放已連入生成樹的點，Y集合存放未連入生成樹的點。一開始所有頂點都在Y中，首先將參數(shù)起點放入X并從Y中刪除。從X中所有點連出的邊中選出“權(quán)最小的且有一端頂點在Y中的邊”，插入到最小生成樹中，再把這條邊的端點放入X中并從Y中刪除。如此循環(huán)往復，直到所有頂點都在X中。

這種算法天然避免了環(huán)的發(fā)生！

// 給一個起點
W Prim(Self& minTree, const V& src)
{
	size_t srci = GetVertexIndex(src);
	size_t n = _vertexs.size();
	minTree._vertexs = _vertexs;
	minTree._vIndexMap = _vIndexMap;
	minTree._matrix.resize(n);
	for (size_t i = 0; i < n; ++i)
	{
		minTree._matrix[i].resize(n, MAX_W);
	}
	// X和Y集合
	vector<bool> X(n, false);
	vector<bool> Y(n, true);
	X[srci] = true;
	Y[srci] = false;
	// 從X->Y集合中連接的邊里面選出最小的邊
	priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
	// 先把srci連接的邊添加到隊列中
	for (size_t i = 0; i < n; ++i)
	{
		if (_matrix[srci][i] != MAX_W)
		{
			minq.push(Edge(srci, i, _matrix[srci][i]));
		}
	}
	size_t size = 0;
	W total = W();
	while (!minq.empty())
	{
		Edge min = minq.top();
		minq.pop();
		if (!X[min._dsti])
		{
			minTree.AddEdge(min._srci, min._dsti, min._w);
			X[min._dsti] = true;
			Y[min._dsti] = false;
			++size;
			total += min._w;
			if (size == n - 1)
				break;
			for (size_t i = 0; i < n; ++i)
			{
				if (_matrix[min._dsti][i] != MAX_W && Y[i])
				{
					minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
				}
			}
		}
	}
	if (size == n - 1)
	{
		return total;
	}
	else
	{
		return W();
	}
}

以上就是C++圖論基礎(chǔ)之圖的遍歷與最小生成樹算法詳解的詳細內(nèi)容，更多關(guān)于C++圖的遍歷與最小生成樹的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: