??作者：@阿亮joy.
??專欄：《數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué)》
??座右銘：每個優(yōu)秀的人都有一段沉默的時光，那段時光是付出了很多努力卻得不到結(jié)果的日子，我們把它叫做扎根
??圖的基本概念??
圖是由頂點集合及頂點間的關(guān)系組成的一種數(shù)據(jù)結(jié)構(gòu)：G = (V， E)，其中：頂點集合V = {x|x屬于某個數(shù)據(jù)對象集}是有窮非空集合；E = {(x,y)|x, y 屬于 V}或者E = {<x, y> |x ,y 屬于 V && Path(x, y)} 是頂點間關(guān)系的有窮集合，也叫做邊的集合。注：(x, y) 表示 x 到 y 的一條雙向通路，即 (x, y) 是無方向的；Path(x, y) 表示從 x 到 y 的一條單向通路，即 Path(x, y) 是有方向的。
頂點和邊：圖中結(jié)點稱為頂點，第 i 個頂點記作 vi。兩個頂點 vi 和 vj 相關(guān)聯(lián)稱作頂點 vi 和頂點 vj 之間有一條邊，圖中的第 k 條邊記作 ek，ek = (vi，vj) 或 <vi，vj>。
有向圖和無向圖：在有向圖中，頂點對 <x, y> 是有序的，頂點對 <x，y> 稱為頂點 x 到頂點 y 的一條邊(弧)，<x, y> 和 <y, x> 是兩條不同的邊，比如下圖 G3 和 G4 為有向圖。在無向圖中，頂點對 (x, y) 是無序的，頂點對 (x,y) 稱為頂點 x 和頂點 y 相關(guān)聯(lián)的一條邊，這條邊沒有特定方向，(x, y) 和 (y，x) 是同一條邊，比如下圖 G1 和 G2 為無向圖。注意：無向邊 (x, y) 等于有向邊 <x, y> 和 <y, x>。
注：數(shù)是一種特殊（無環(huán)聯(lián)通）的圖，圖不一定是樹。樹關(guān)注的是節(jié)點（頂點）中存的值，圖關(guān)注的是頂點及邊的權(quán)值。完全圖：在有 n 個頂點的無向圖中，若有 n * (n - 1) / 2 條邊，即任意兩個頂點之間有且僅有一條邊，則稱此圖為無向完全圖，比如上圖 G1；在 n 個頂點的有向圖中，若有 n * (n - 1)條邊，即任意兩個頂點之間有且僅有方向相反的邊，則稱此圖為有向完全圖（最稠密的圖），比如上圖 G4。
鄰接頂點：在無向圖 G 中，若 (u, v) 是 E(G) 中的一條邊，則稱 u 和 v 互為鄰接頂點，并稱邊 (u,v) 依附于頂點 u 和 v；在有向圖 G 中，若 <u, v> 是 E(G) 中的一條邊，則稱頂點 u 鄰接到 v，頂點 v 鄰接自頂點 u，并稱邊 <u, v> 與頂點 u 和頂點 v 相關(guān)聯(lián)。
頂點的度：頂點v的度是指與它相關(guān)聯(lián)的邊的條數(shù)，記作deg(v)。在有向圖中，頂點的度等于該頂點的入度與出度之和，其中頂點 v 的入度是以 v 為終點的有向邊的條數(shù)，記作 indev(v)；頂點 v 的出度是以 v 為起始點的有向邊的條數(shù)，記作 outdev(v)。因此：dev(v) = indev(v) + outdev(v)。注意：對于無向圖，頂點的度等于該頂點的入度和出度，即 dev(v) = indev(v) = outdev(v)。
路徑：在圖 G = (V， E) 中，若從頂點 vi 出發(fā)有一組邊使其可到達(dá)頂點 vj，則稱頂點 vi 到頂點 vj 的頂點序列為從頂點 vi 到頂點 vj 的路徑。
路徑長度：對于不帶權(quán)的圖，一條路徑的路徑長度是指該路徑上的邊的條數(shù)；對于帶權(quán)的圖，一條路徑的路徑長度是指該路徑上各個邊權(quán)值的總和。
注：在交通網(wǎng)絡(luò)圖中，頂點可以表示城市，邊的權(quán)值可以表示城市之間的一個關(guān)系（高鐵距離、高鐵價格等）。在社交關(guān)系圖中，頂點可以表示人，邊表示兩個人是好友，權(quán)值表示親密度等等。微信和 QQ 上的好友等關(guān)系是無向圖，是強社交關(guān)系；微博和抖音上的博主和粉絲等關(guān)系是有向圖，是弱社交關(guān)系。簡單路徑與回路：若路徑上各頂點 v1，v2，v3，…，vm 均不重復(fù)，則稱這樣的路徑為簡單路徑。若路徑上第一個頂點 v1 和最后一個頂點 vm 重合，則稱這樣的路徑為回路或環(huán)。
子圖：設(shè)圖 G = {V, E} 和圖 G1 = {V1，E1}，若 V1 屬于 V 且 E1 屬于 E，則稱 G1 是 G 的子圖。
連通圖：在無向圖中，若從頂點 v1 到頂點 v2 有路徑，則稱頂點 v1 與頂點 v2 是連通的（可以直接相連，也可以間接相連）。如果圖中任意一對頂點都是連通的，則稱此圖為連通圖。如果不是連通圖，則會存在孤島。
強連通圖：在有向圖中，若在每一對頂點 vi 和 vj 之間都存在一條從 vi 到 vj 的路徑，也存在一條從 vj 到 vi的路徑，則稱此圖是強連通圖。
生成樹：在無向圖中，一個連通圖的最小連通子圖稱作該圖的生成樹。有 n 個頂點的連通圖的生成樹有 n 個頂點和 n - 1 條邊。
??圖的存儲結(jié)構(gòu)??
因為圖中既有節(jié)點，又有邊(節(jié)點與節(jié)點之間的關(guān)系)。因此，在圖的存儲中，只需要保存節(jié)點和邊關(guān)系即可。節(jié)點保存比較簡單，只需要一段連續(xù)空間即可，那邊關(guān)系該怎么保存呢？
鄰接矩陣
因為節(jié)點與節(jié)點之間的關(guān)系就是連通與否，即為 0 或者1，因此鄰接矩陣(二維數(shù)組)即是先用一個數(shù)組將定點保存，然后采用矩陣來表示節(jié)點與節(jié)點之間的關(guān)系。
注意：
- 無向圖的鄰接矩陣是對稱的，第 i 行(列)元素之和，就是頂點 i 的度。有向圖的鄰接矩陣則不一定是對稱的，第 i 行(列)元素之后就是頂點 i 的出(入)度。
- 如果邊帶有權(quán)值，并且兩個節(jié)點之間是連通的，上圖中的邊的關(guān)系就用權(quán)值代替，如果兩個頂點不通，則使用無窮大代替。
3. 鄰接矩陣的優(yōu)點：非常適合存儲稠密圖，用鄰接矩陣存儲圖的有點是能夠快速知道兩個頂點是否連通并取到權(quán)值。缺點：如果頂點比較多，邊比較少時，矩陣中存儲了大量的 0 成為系數(shù)矩陣，比較浪費空間，并且要求兩個節(jié)點之間的路徑不是很好求。相對而言，不適合查找一個頂點的所有邊，時間復(fù)雜度為 O(頂點個數(shù))。
鄰接矩陣的模擬實現(xiàn)
#pragma once
#include <vector>
#include <map>
#include <iostream>
using namespace std;
namespace matrix
{
// V是頂點,W是權(quán)值
// 默認(rèn)權(quán)值是INT_MAX,默認(rèn)是無向圖
template <class V, class W, W W_MAX = INT_MAX, bool Direction = false>
class Graph
{
public:
// 圖的創(chuàng)建
// 1.IO輸入 -- 不方便測試,OJ中更適合
// 2.圖的結(jié)構(gòu)關(guān)系寫到文件中,讀取文件
// 3.手動添加邊,方便測試
Graph(const V* a, size_t n)
{
// 將頂點集合的空間開好
_vertexs.reserve(n);
for (size_t i = 0; i < n; ++i)
{
// 建立映射關(guān)系
_vertexs.push_back(a[i]);
_indexMap[a[i]] = i;
}
// 將鄰接矩陣的空間開好
_matrix.resize(n);
for (size_t i = 0; i < n; ++i)
{
_matrix[i].resize(n, W_MAX);
}
}
// 獲得頂點對應(yīng)的下標(biāo)
size_t GetVertexIndex(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
return it->second;
else
{
//assert(false);
throw invalid_argument("頂點不存在");
return -1;
}
}
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;
// 無向圖
if (Direction == false)
_matrix[dsti][srci] = w;
}
void Print()
{
int n = _vertexs.size();
// 打印頂點及映射關(guān)系
for (size_t i = 0; i < n; ++i)
{
cout <<"[" << _vertexs[i] << "]" << "->" << i << endl;
}
cout << endl;
// 打印矩陣列標(biāo)
cout << " ";
for (size_t i = 0; i < _vertexs.size(); ++i)
{
cout << i << " ";
}
cout << endl;
// 打印權(quán)值
for (size_t i = 0; i < n; ++i)
{
cout << i << " "; // 打印矩陣行標(biāo)
for (size_t j = 0; j < n; ++j)
{
if (_matrix[i][j] != W_MAX)
cout << _matrix[i][j] << " ";
else
cout << "*" << " ";
}
cout << endl;
}
cout << endl << endl;
}
private:
vector<V> _vertexs; // 頂點集合
map<V, int> _indexMap; // 頂點映射的下標(biāo)
vector<vector<W>> _matrix; // 鄰接矩陣
};
void GraphTest()
{
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();
}
}
鄰接表
鄰接表：使用數(shù)組表示頂點的集合，使用鏈表表示邊的關(guān)系。
- 無向圖鄰接表存儲
注意：無向圖中同一條邊在鄰接表中出現(xiàn)了兩次。如果想知道頂點 vi 的度，只需要知道頂點 vi 邊鏈表集合中結(jié)點的數(shù)目即可。
- 有向圖鄰接表存儲
注意：有向圖中每條邊在鄰接表中只出現(xiàn)一次，與頂點 vi 對應(yīng)的鄰接表所含結(jié)點的個數(shù)，就是該頂點的出度，也稱出度表。想要得到 vi 頂點的入度，必須檢測其他所有頂點對應(yīng)的邊鏈表，看有多少邊頂點的 dst 取值是 i。鄰接表適合存儲稀疏圖，適合查找一個頂點連接出去的邊，鄰接表不適合確定兩個頂點是否相連及邊的權(quán)重。一般情況下，有向圖存儲出邊表即可。
鄰接表的實現(xiàn)
#pragma once
#include <vector>
#include <map>
#include <iostream>
#include <string>
using namespace std;
namespace linkTable
{
template<class W>
struct LinkEdge
{
// 只關(guān)心出邊
//int _srcIndex; // 起始點下標(biāo)
int _dstIndex; // 目標(biāo)點下標(biāo)
W _w; // 權(quán)值
LinkEdge<W>* _next;
LinkEdge(int dstIndex, const W& w)
: _dstIndex(dstIndex)
, _w(w)
, _next(nullptr)
{}
};
// V是頂點,W是權(quán)值
// 默認(rèn)是無向圖
template <class V, class W, bool Direction = false>
class Graph
{
typedef LinkEdge<W> Edge;
public:
Graph(const V* a, size_t n)
{
// 將頂點集合的空間開好
_vertexs.reserve(n);
for (size_t i = 0; i < n; ++i)
{
// 建立映射關(guān)系
_vertexs.push_back(a[i]);
_indexMap[a[i]] = i;
}
// 將鄰接表的空間開好
_tables.resize(n, nullptr);
}
// 獲得頂點對應(yīng)的下標(biāo)
size_t GetVertexIndex(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
return it->second;
else
{
//assert(false);
throw invalid_argument("頂點不存在");
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)
{
eg = new Edge(srci, w);
eg->_next = _tables[dsti];
_tables[dsti] = eg;
}
}
void Print()
{
int n = _tables.size();
// 頂點
for (size_t i = 0; i < n; ++i)
{
cout << "[" << i << "]:" << _vertexs[i] << "->";
Edge* cur = _tables[i];
while (cur)
{
cout << "[" << cur->_dstIndex << ":" << _vertexs[cur->_dstIndex] << ":" << cur->_w << "]" << "->";
cur = cur->_next;
}
cout << "nullptr" << endl;
}
cout << endl;
}
private:
vector<V> _vertexs; // 頂點集合
map<V, int> _indexMap; // 頂點映射的下標(biāo)
vector<Edge*> _tables; // 鄰接表
};
void GraghTest()
{
string a[] = { "張三", "李四", "王五", "趙六", "田七" };
Graph<string, int, true> g1(a, sizeof(a) / sizeof(string)); // 無向圖
//Graph<string, int, true> g1(a, sizeof(a) / sizeof(string)); // 有向圖
g1.AddEdge("張三", "李四", 100);
g1.AddEdge("張三", "王五", 200);
g1.AddEdge("王五", "趙六", 30);
g1.AddEdge("王五", "田七", 30);
g1.Print();
}
}
??圖的遍歷??
給定一個圖 G 和其中任意一個頂點 v0，從 v0 出發(fā)，沿著圖中各邊訪問圖中的所有頂點，且每個頂點僅被遍歷一次。遍歷即對結(jié)點進(jìn)行某種操作的意思。
圖的廣度優(yōu)先遍歷
圖的廣度優(yōu)先遍歷和樹的層序遍歷相似，需要借助隊列。當(dāng)前節(jié)點出隊列，需要將與其相連的節(jié)點入隊列。如果相連節(jié)點已經(jīng)遍歷過了，該節(jié)點不能再入隊列，所以需要將已遍歷過的節(jié)點（即入隊列的節(jié)點）標(biāo)記一下。
namespace matrix
{
// ...
class Graph
{
public:
void BFS(const V& src)
{
size_t srci = GetVertexIndex(src);
// 隊列和標(biāo)記數(shù)組
vector<bool> visited(_vertexs.size(), false);
queue<int> q;
q.push(srci);
visited[srci] = true;
size_t n = _vertexs.size();
while (!q.empty())
{
int front = q.front();
q.pop();
cout << "[" << front << ":" << _vertexs[front] << "]" << endl;
// front的鄰接頂點入隊列
for (size_t i = front + 1; i < n; ++i)
{
if (_matrix[front][i] != W_MAX)
{
if (visited[i] == false)
{
q.push(i);
visited[i] = true;
}
}
}
}
}
}
// ...
}
思路：和二叉樹的層序遍歷一層一層打印的思路類似，找出一個人的 n 度好友也需要控制一層一層地打印。
namespace matrix
{
// ...
class Graph
{
public:
void BFS(const V& src)
{
size_t srci = GetVertexIndex(src);
// 隊列和標(biāo)記數(shù)組
vector<bool> visited(_vertexs.size(), false);
queue<int> q;
q.push(srci);
visited[srci] = true;
int levelSize = 1;
size_t n = _vertexs.size();
while (!q.empty())
{
for (int i = 0; i < levelSize; ++i)
{
int front = q.front();
q.pop();
cout << "[" << front << ":" << _vertexs[front] << "]" << " ";
// front的鄰接頂點入隊列
for (size_t i = front + 1; i < n; ++i)
{
if (_matrix[front][i] != W_MAX)
{
if (visited[i] == false)
{
q.push(i);
visited[i] = true;
}
}
}
}
cout << endl;
levelSize = q.size();
}
}
}
// ...
}
圖的深度優(yōu)先遍歷
namespace matrix
{
// ...
class Graph
{
public:
void DFS(const V& src)
{
size_t srci = GetVertexIndex(src);
vector<bool> visited(_vertexs.size(), false);
_DFS(srci, visited);
}
private:
void _DFS(size_t srci, vector<bool>& visited)
{
cout << "[" << srci << ":" << _vertexs[srci] << "]" << endl;
visited[srci] = true;
// 找一個與srci相鄰的沒有訪問過的頂點,進(jìn)行深度遍歷
for (size_t i = srci + 1; i < _vertexs.size(); ++i)
{
if (_matrix[srci][i] != W_MAX && visited[i] == false)
{
_DFS(i, visited);
}
}
}
// ...
}
注：對于稀疏圖來說，鄰接矩陣的廣度優(yōu)先遍歷和深度優(yōu)先遍歷是比較吃虧的，因為比較多的位置是空的，但還需要去檢查是否為空。而鄰接表的廣度優(yōu)先遍歷和深度優(yōu)先遍歷是比較復(fù)雜的，所以還是采用了鄰接矩陣的廣度優(yōu)先遍歷和深度優(yōu)先遍歷。
如果給出的圖不是連通圖，那么以某個頂點為起點就無法遍歷完整個圖的頂點，那如何保存遍歷完剩下的頂點呢？visited 數(shù)組中記錄著頂點的是否遍歷過了的信息，只要將沒有遍歷過的頂點遍歷就行了。
文章來源：http://www.zghlxwxcb.cn/news/detail-757835.html
??總結(jié)??
本篇博客主要講解了圖的基本概念、鄰接矩陣和鄰接表、圖的廣度優(yōu)先遍歷和深度遍歷等。那么以上就是本篇博客的全部內(nèi)容了，如果大家覺得有收獲的話，可以點個三連支持一下！謝謝大家！??????文章來源地址http://www.zghlxwxcb.cn/news/detail-757835.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】圖的基本概念 | 鄰接矩陣和鄰接表 | 廣度優(yōu)先遍歷和深度優(yōu)先遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[入門必看]數(shù)據(jù)結(jié)構(gòu)6.1：圖的基本概念](https://imgs.yssmx.com/Uploads/2024/02/464522-1.png)
