圖的概念
圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系組成的一種數(shù)據(jù)結(jié)構(gòu)：G = (V， E)
圖分為有向圖和無向圖
- 在有向圖中，頂點(diǎn)對(duì)<x, y>是有序的，頂點(diǎn)對(duì)<x，y>稱為頂點(diǎn)x到頂點(diǎn)y的一條邊(弧)，<x, y>和<y, x>是兩條不同的邊。
- 在無向圖中，頂點(diǎn)對(duì)(x, y)是無序的，頂點(diǎn)對(duì)(x,y)稱為頂點(diǎn)x和頂點(diǎn)y相關(guān)聯(lián)的一條邊，這條邊沒有特定方向，(x, y)和(y，x)是同一條邊
就像第一幅圖中，<V1,V2>頂點(diǎn)構(gòu)成有向圖，邊 E1和邊E2是不同指向的
在第二幅圖中，<V3,V4>構(gòu)成無向圖，E3就是連接二者關(guān)系的唯一邊。
在生活中的關(guān)系，例如微信里的朋友關(guān)系就是無向的，只有雙方都相連，才能發(fā)送消息
而類是與微博等就是單向的，你關(guān)注某人，就是一條邊。當(dāng)他也關(guān)注你時(shí)，才構(gòu)成倆條邊。
?
完全圖
- 有n個(gè)頂點(diǎn)的無向圖中，若有n * (n-1)/2條邊，即任意兩個(gè)頂點(diǎn)之間有且僅有一條邊，
- 則稱此圖為無向完全圖
- 在n個(gè)頂點(diǎn)的有向圖中，若有n * (n-1)條邊，即任意兩個(gè)頂點(diǎn)之間有且僅有方向相反的邊，則稱此圖為有向完全圖
下列的圖都是完全圖?
?
鄰接頂點(diǎn)
- 無向圖中，v-u 稱互為鄰接頂點(diǎn)
- 有向圖中，v->u? ?稱u是v的鄰接頂點(diǎn)
與頂點(diǎn)直接相鄰的頂點(diǎn)
例如：G1中 0和2 都是 1的鄰接頂點(diǎn)
0 1 2 3互為鄰接頂點(diǎn)
圖與樹的主要聯(lián)系與區(qū)別
樹是一種特殊的圖
圖不一定是樹
樹關(guān)注結(jié)點(diǎn)的存值，圖關(guān)注頂點(diǎn)和邊的權(quán)值。
圖的存儲(chǔ)結(jié)構(gòu)
本質(zhì)就是將邊和頂點(diǎn)，及其關(guān)系存儲(chǔ)起來。
用vector數(shù)組保存頂點(diǎn)
vector<V> _vertexs;利用map映射頂點(diǎn)和下標(biāo)的關(guān)系
map<V, int> _vIndexMap; 為了解決倆個(gè)頂點(diǎn)是否相連，相連的邊權(quán)值是多少的問題。
解決方法主要有鄰接矩陣，和鄰接表
鄰接矩陣
利用一個(gè)N*N的矩陣表示邊和權(quán)值的關(guān)系
如果想要找到頂點(diǎn)A相連的頂點(diǎn)，通過橫行找到A，在通過縱行?找到 內(nèi)容不為無窮大的 B D。
為了表示邊權(quán)之間的關(guān)系，修改 0和1為權(quán)值w和無窮
規(guī)定頂點(diǎn)自己到自己是不相連 ，不連通為無窮。
?
namespace Matrix
{
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{
typedef Graph<V, W, MAX_W, Direction> Self;
public:
Graph()
{
}
Graph(const V* a, size_t n)
{
_vertexs.reserve(n);
for (size_t i = 0; i < n; i++)
{
_vertexs.push_back(a[i]);
_vIndexMap[a[i]] = i;
}
_matrix.resize(n);
for (size_t i = 0; i < _matrix.size(); i++)
{
_matrix[i].resize(n, MAX_W);
}
}
//獲取下標(biāo)
size_t GetVertexIndex(const V& v)
{
auto it = _vIndexMap.find(v);
if (it != _vIndexMap.end())
{
return it->second;
}
else
{
throw invalid_argument("頂點(diǎn)不存在");
assert(false);
return -1;
}
}
void _AddEdge(size_t srci, size_t dsti, const W& w)
{
_matrix[srci][dsti] = w;
if (Direction == false)
{
_matrix[dsti][srci] = w;
}
}
//添加邊的關(guān)系
void AddEdge(const V& src, const V& dst, const W& w)
{
size_t srci = GetVertexIndex(src);
size_t dsti = GetVertexIndex(dst);
_AddEdge(srci, dsti, w);
}
private:
vector<V> _vertexs; //頂點(diǎn)集合
map<V, int> _vIndexMap; //頂點(diǎn)映射下標(biāo)
vector<vector<W>> _matrix; //鄰接矩陣
};關(guān)于圖的構(gòu)造，需要輸入頂點(diǎn)，并且手動(dòng)添加邊。
添加邊后，將鄰接矩陣v->u的位置置為權(quán)值，如果是無向圖，那么u->v也置上權(quán)值。
鄰接矩陣的優(yōu)缺點(diǎn)
- 鄰接矩陣的存儲(chǔ)方式非常適合稠密圖
- 它能做到O(1)的效率判斷倆個(gè)頂點(diǎn)的關(guān)系
- 不適合找出所有鄰接的邊
鄰接表
- 鄰接表：使用數(shù)組表示頂點(diǎn)的集合，使用鏈表表示邊的關(guān)系
- 鄰接表是指針數(shù)組，將所有鄰接的邊，都掛在vector下。
一般而言，鄰接表有入邊和出邊，我們只關(guān)心出邊。
邊的結(jié)構(gòu) dsti w next
對(duì)于鄰接表就是將有關(guān)聯(lián)的邊都掛載在數(shù)組上。
同樣需要vector數(shù)組保存頂點(diǎn)，map保存頂點(diǎn)和下標(biāo)的映射。
鄰接表的內(nèi)容是一個(gè)邊結(jié)構(gòu)，內(nèi)容包含srci(不一定有)，dsti,w權(quán)值，next指向下一個(gè)關(guān)聯(lián)的邊。
namespace LinkTable
{
template<class W>
struct Edge
{
int _dsti;//目標(biāo)點(diǎn)
W _w; //權(quán)值
Edge<W>* _next;
Edge() = delete;
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;
public:
Graph(const V* a, size_t n)
{
_vertexs.reserve(n);
for (size_t i = 0; i < n; i++)
{
_vertexs.push_back(a[i]);
_vIndexMap[a[i]] = i;
}
_tables.resize(n, nullptr);
}
//獲取下標(biāo)
size_t GetVertexIndex(const V& v)
{
auto it = _vIndexMap.find(v);
if (it != _vIndexMap.end())
{
return it->second;
}
else
{
throw invalid_argument("頂點(diǎn)不存在");
assert(false);
return -1;
}
}
void _AddEdge(const size_t srci, const size_t dsti, const W& w)
{
//1->2
Edge* eg = new Edge(dsti, w);
eg->_next = _tables[srci];
_tables[srci] = eg;
//2->1
if (Direction == false)
{
Edge* eg = new Edge(srci, w);
eg->_next = _tables[dsti];
_tables[dsti] = eg;
}
}
void AddEdge(const V& src, const V& dst, const W& w)
{
size_t srci = GetVertexIndex(src);
size_t dsti = GetVertexIndex(dst);
_AddEdge(srci, dsti, w);
}
void Print()
{
//打印下標(biāo)映射
for (size_t i = 0; i < (_vertexs.size()); i++)
{
cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
}
//打印邊
for (size_t i = 0; i < _tables.size(); i++)
{
cout << "[" << i << "] ";
Edge* cur = _tables[i];
while (cur)
{
cout << "- [ dsti->" << cur->_dsti << "| w:"<<cur->_w<<"] -";
cur = cur->_next;
}
cout << "null" << endl;
}
}
private:
vector<V> _vertexs; //頂點(diǎn)集合
map<V, int> _vIndexMap; //頂點(diǎn)映射下標(biāo)
vector<Edge*> _tables; //鄰接表（出邊表）
};?鄰接表的優(yōu)缺點(diǎn)
- 適合稠密圖
- 適合找頂點(diǎn)出去的邊
- 不適合用來確定倆個(gè)頂點(diǎn)的關(guān)系和權(quán)值
鄰接矩陣和鄰接表二者各有優(yōu)勢(shì)，相輔相成。在后續(xù)的最小生成樹和最短路徑中，鄰接矩陣更方便
圖的遍歷
從v0出發(fā)，根據(jù)某種規(guī)則沿著圖中各邊訪問圖的頂點(diǎn)，每一個(gè)都會(huì)被訪問到，且只被訪問到一次。
遍歷的方式分為廣度優(yōu)先BFS和深度優(yōu)先DFS
廣度優(yōu)先BFS
廣度優(yōu)先類似于二叉樹的層序遍歷，從左到右依次遍歷，一層到一層。
BFS的思路
- 要實(shí)現(xiàn)層序遍歷，就要維護(hù)一個(gè)隊(duì)列，A出隊(duì)列時(shí)候，帶A的相鄰B C D入隊(duì)列
- 當(dāng) A 出完之后，B再出 就會(huì)帶A進(jìn)，為了防止重復(fù)帶入，再維護(hù)一張vector的數(shù)組，出過了就標(biāo)記，只有當(dāng)標(biāo)記容器沒有被標(biāo)記時(shí)，才帶進(jìn)隊(duì)列。
void BFS(const V& src)
{
size_t srci = GetVertexIndex(src);
//隊(duì)列和標(biāo)記數(shù)組
queue<int> q;
vector<bool> visited(_vertexs.size(), false);
q.push(srci);
visited[srci] = true;
while (!q.empty())
{
size_t front = q.front();
q.pop();
cout << front << ":" << _vertexs[front] << endl;
for (size_t i = 0; i < _vertexs.size(); i++)
{
//入隊(duì)列
if (_matrix[front][i] != MAX_W)
{
if (visited[i] == false)
{
q.push(i);
//修改標(biāo)記
visited[i] = true;
}
}
}
}
}
深度優(yōu)先DFS
類似于二叉樹的先序遍歷，從上從往下，一直遍歷到最深，知道遇到訪問或結(jié)束，就返回。
DFS需要一個(gè)起始點(diǎn)，標(biāo)志從哪里開始遍歷，需要一個(gè)visited數(shù)組，標(biāo)記哪些頂點(diǎn)被訪問過了
void _DFS(size_t srci, vector<bool>& visited)
{
cout << srci << ":" << _vertexs[srci] << endl;
visited[srci] = true;
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);
}
文章來源：http://www.zghlxwxcb.cn/news/detail-836902.html
Gitee:提取完整代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-836902.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】圖的存儲(chǔ)與遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
