前言
圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系組成的一種數(shù)據(jù)結(jié)構(gòu)：G = (V， E)，其中：
頂點(diǎn)集合V = {x|x屬于某個(gè)數(shù)據(jù)對(duì)象集}是有窮非空集合；
E = {(x,y)|x,y屬于V}或者E = {<x, y>|x,y屬于V && Path(x, y)}是頂點(diǎn)間關(guān)系的有窮集合，也叫
做邊的集合。
完全圖：在有n個(gè)頂點(diǎn)的無(wú)向圖中，若有n * (n-1)/2條邊，即任意兩個(gè)頂點(diǎn)之間有且僅有一條邊，
則稱此圖為無(wú)向完全圖，比如上圖G1；在n個(gè)頂點(diǎn)的有向圖中，若有n * (n-1)條邊，即任意兩個(gè)
頂點(diǎn)之間有且僅有方向相反的邊，則稱此圖為有向完全圖
1.圖的存儲(chǔ)結(jié)構(gòu)
因?yàn)閳D中既有節(jié)點(diǎn)，又有邊(節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系)，因此，在圖的存儲(chǔ)中，只需要保存：節(jié)點(diǎn)和
邊關(guān)系即可。
節(jié)點(diǎn)保存比較簡(jiǎn)單，只需要一段連續(xù)空間即可，那邊關(guān)系該怎么保存呢？
1.鄰接矩陣
因?yàn)楣?jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系就是連通與否，即為0或者1，因此鄰接矩陣(二維數(shù)組)即是：先用一
個(gè)數(shù)組將定點(diǎn)保存，然后采用矩陣來(lái)表示節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系。
2.鄰接表
一、鄰接矩陣
主要思想就是，先建立頂點(diǎn)與數(shù)組下標(biāo)的映射關(guān)系，我們通過(guò)這個(gè)兩個(gè)頂點(diǎn)對(duì)應(yīng)的下標(biāo)，確定其在二維數(shù)組（鄰接矩陣）中的位置，然后將鄰接矩陣對(duì)應(yīng)位置修改為權(quán)值（找頂點(diǎn)與下標(biāo)關(guān)系之所以還要一個(gè)函數(shù)來(lái)控制而不用哈希表是因?yàn)槲覀円业捻旤c(diǎn)可能不存在，如果用哈希表就會(huì)直接將這個(gè)不存在的頂點(diǎn)插入進(jìn)去）
namespace matrix {
//V為頂點(diǎn)類型，W為邊權(quán)值類型，MAX_W為權(quán)值最大值也就是無(wú)效值
//Direction用來(lái)判斷是不是有向圖，false為無(wú)向圖
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph {
public:
Graph(const V* a, size_t n) {
_vertexs.reserve(n);
for (size_t i = 0; i < n; i++) {
_vertexs.push_back(a[i]);
_indexMap[a[i]] = i;
//將頂點(diǎn)存入_vertexs，下標(biāo)映射存進(jìn)map
}
_matrix.resize(n);
for (size_t i = 0; i < _matrix.size(); i++) {
_matrix[i].resize(n, MAX_W);
//鄰接矩陣默認(rèn)初始值為無(wú)效值
}
}
size_t GetVertexIndex(const V& v) {
//獲得對(duì)應(yīng)頂點(diǎn)在數(shù)組中的下標(biāo)
auto it = _indexMap.find(v);
if (it != _indexMap.end()) {
return it->second;
//有這個(gè)頂點(diǎn)返回其下標(biāo)
}
else {
throw("頂點(diǎn)不存在");
return -1;
}
}
void _AddEdge(size_t srci, size_t dsti, const W& w) {
//存入權(quán)值
_matrix[srci][dsti] = w;
if (Direction == false) {
_matrix[dsti][srci] = w;
//無(wú)向圖要兩個(gè)方向都存
}
}
void AddEdge(const V& src, const V& dst, const W& w) {
//添加邊與頂點(diǎn)的關(guān)系。從src到dst方向的關(guān)系
size_t srci = GetVertexIndex(src);
size_t dsti = GetVertexIndex(dst);
//先獲取其對(duì)應(yīng)的下標(biāo)
_AddEdge(srci, dsti, w);
}
void Print() {
for (size_t i = 0; i < _vertexs.size(); i++) {
cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
}//打印頂點(diǎn)集
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) {
printf("%4c", '*');
}
else {
printf("%4d", _matrix[i][j]);
}
}
cout << endl;
}
}
private:
vector<V>_vertexs;//頂點(diǎn)集合
map<V, int>_indexMap;//存頂點(diǎn)與數(shù)組下標(biāo)的映射關(guān)系
vector<vector<W>>_matrix;//鄰接矩陣
};
}
用鄰接矩陣存儲(chǔ)圖的有點(diǎn)是能夠快速知道兩個(gè)頂點(diǎn)是否連通，缺陷是如果頂點(diǎn)比較多，邊比
較少時(shí)，矩陣中存儲(chǔ)了大量的0成為系數(shù)矩陣，比較浪費(fèi)空間，并且要求兩個(gè)節(jié)點(diǎn)之間的路
徑不是很好求。
二、鄰接表
namespace link_table {
template<class W>
struct Edge {//Edge用來(lái)保存邊的關(guān)系，當(dāng)作結(jié)點(diǎn)來(lái)使
int _dsti;//目標(biāo)頂點(diǎn)對(duì)應(yīng)下標(biāo)
W _w;//權(quán)值
Edge<W>* _next;
Edge(int dsti, const W& w)
:_dsti(dsti),
_w(w),
_next(nullptr)
{}
};
template<class V, class W, bool Direction = false>
class Graph {
typedef Edge<W> Edge;//注意這里typedf要傳參
public:
Graph(const V* a, size_t n) {
_vertexs.reserve(n);
for (int i = 0; i < n; i++) {
_vertexs.push_back(a[i]);
_indexMap[a[i]] = i;
//將頂點(diǎn)放入數(shù)組，并建立頂點(diǎn)與下標(biāo)的映射關(guān)系
}
_tables.resize(n, nullptr);
}
size_t GetVertexIndex(const V& v) {
//查找頂點(diǎn)對(duì)應(yīng)的下標(biāo)，這里不直接用哈希表
//來(lái)查是因?yàn)轫旤c(diǎn)可能不存在
auto it = _indexMap.find(v);
if (it != _indexMap.end()) {
return it->second;
}
else {
throw ("頂點(diǎn)不存在");
return -1;
}
}
void AddEdge(const V& src, const V& dst, const W& w) {
size_t srci = GetVertexIndex(src);
size_t dsti = GetVertexIndex(dst);
Edge* eg = new Edge(dsti, w);
eg->_next = _tables[srci];
_tables[srci] = eg;
if (Direction == false) {//如果為無(wú)向圖，兩個(gè)頂點(diǎn)都要加權(quán)值記錄
Edge* eg = new Edge(srci, w);
eg->_next = _tables[dsti];
_tables[dsti] = eg;
}
}
void Print() {
for (size_t i = 0; i < _vertexs.size(); i++) {
cout << "[" << i << "]" << _vertexs[i] << endl;
}//打印頂點(diǎn)集合
cout << endl;
//打印鄰接表
for (size_t i = 0; i < _tables.size(); i++) {
cout << _vertexs[i] << "[" << i << "]->";
Edge* cur = _tables[i];
while (cur) {
cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << endl;
cur = cur->_next;
}
cout << "nullptr" << endl;
}
}
private:
vector<V>_vertexs;//頂點(diǎn)數(shù)組
vector<Edge*>_tables;//鄰接表
map<V, int> _indexMap;//頂點(diǎn)與下標(biāo)的映射關(guān)系
};
}
二、圖的遍歷
1.DFS
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-764244.html
void _DFS(size_t srci, vector<bool>& visited) {
cout << srci << ":" << _vertexs[srci] << endl;
visited[srci] = true;//標(biāo)記這個(gè)頂點(diǎn)被訪問(wèn)過(guò)了
for (size_t i = 0; i < _vertexs.size(); i++) {
if (_matrix[srci][i] != MAX_W && visited[i] == false) {
_DFS(i, visited);
}
}
}
void DFS(const V& src) {
size_t srci = GetVertexIndex(src);
vector<bool>visited(_vertexs.size(), false);
_DFS(srci, visited);
}
2.BFS
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-764244.html
void BFS(const V& src) {
size_t srci = GetVertexIndex(src);
queue<int>q;
q.push(srci);
vector<bool>visited(_vertexs.size(), false);
visited[srci] = true;//標(biāo)記這個(gè)頂點(diǎn)被訪問(wèn)過(guò)了
int levelSize = 1;
while (!q.empty()) {
//levelSize為當(dāng)前層的大小
for (size_t i = 0; i < levelSize; i++) {
int front = q.front();
q.pop();
cout << front << ":" << _vertexs[front]<<" ";
for (size_t i = 0; i < _vertexs.size(); i++) {
if (_matrix[front][i] != MAX_W && visited[i] == false) {
q.push(i);
visited[i] = true;//標(biāo)記這個(gè)頂點(diǎn)被訪問(wèn)過(guò)了
}
}
}
levelSize = q.size();//更新當(dāng)前層的數(shù)量
cout << endl;
}
cout << endl;
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】圖的創(chuàng)建（鄰接矩陣，鄰接表）以及深度廣度遍歷（BFS,DFS）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
