图的存储结构
邻接矩阵
边和边之间关系通过矩阵数组来保存关系
- 邻接矩阵适合稠密图(复杂的顶点关系)
- 邻接矩阵可以O（1）判断顶点的连接关系
- 不适合查看一个顶点连接的所有边O(N)
A,B之间相连所以matrix[A][B]=1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| template <class V, class W, W MAX_W = INT32_MAX, bool Direct = false>
class Graph
{
typedef Graph<V, W, MAX_W, Direct> Self;
private:
vector<V> _vertex;
map<V, int> _indexmap;
vector<vector<W>> _matrix;
public:
Graph() = default;
Graph(const V *a, size_t n)
{
_vertex.reserve(n);
for (size_t i = 0; i < n; i++)
{
_vertex.push_back(a[i]);
_indexmap[a[i]] = i;
}
_matrix.resize(n);
for (size_t i = 0; i < n; i++)
{
_matrix[i].resize(n, MAX_W);
}
}
size_t GetVertexIndex(const V &v)
{
auto it = _indexmap.find(v);
if (it != _indexmap.end())
{
return it->second;
}
else
{
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 (Direct == false)
{
_matrix[dsti][srci] = w;
}
}
|
邻接表
邻接表：使用数组表示顶点的集合，使用链表来表示边的关系类似 hashtable
- 适合稀疏的图（顶点之间关系比较简单）
- 方便查找一个节点的所有边
- 不适合判断两个节点之间是否相连
添加边关系：通过src顶点找到对应的数组，进行 头插元素来进行 添加边
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| template <class W>
struct Edge
{
W _w;
int _dsti;
Edge<W> *_next;
Edge(W w, int dsti)
: _w(w), _dsti(dsti), _next(nullptr)
{
}
};
template <class V, class W, bool Direct = false>
class Graph
{
typedef Table::Edge<W> Edge;
private:
vector<V> _vertex;
map<V, int> _indexmap;
vector<Edge *> _table;
public:
Graph(const V *a, size_t n)
{
_vertex.reserve(n);
for (size_t i = 0; i < n; i++)
{
_vertex.push_back(a[i]);
_indexmap[a[i]] = i;
}
_table.resize(n, nullptr);
}
size_t GetVertexIndex(const V &v)
{
auto it = _indexmap.find(v);
if (it != _indexmap.end())
{
return it->second;
}
else
{
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(w, dsti);
eg->_next = _table[srci];
_table[srci] = eg;
if (Direct == false)
{
Edge *eg = new Edge(w, srci);
eg->_next = _table[dsti];
_table[dsti] = eg;
}
}
|
图的遍历
DFS
DFS:深度优先搜索：先往深处遍历，深处遍历完了再回溯，查看上层未边俩的元素
使用一个 visited数组,来标记元素访问与否,用递归来进行遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void _DFS(size_t srci, vector<bool> &visited)
{
visited[srci] = true;
cout << srci << ":" << _vertex[srci] << " ";
for (int i = 0; i < _vertex.size(); i++)
{
if (_matrix[srci][i] != MAX_W && visited[i] == false)
{
_DFS(i, visited);
}
}
return;
}
void DFS(const V &src)
{
size_t srci = GetVertexIndex(src);
vector<bool> visited(_vertex.size(), false);
_DFS(srci, visited);
}
|
BFS
BFS：广度优先搜索，一层一层的遍历元素,直到遍历到最后一层的元素
思路
使用一个队列和一个visited数组,元素入队列的时候，标记他对应的visited数组=true，元素出队列的时候，代入他连接的未入队列的所有节点,直到队列为空，遍历结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
void BFS(const V &src)
{
int srci = GetVertexIndex(src);
queue<int> q;
q.push(srci);
vector<bool> visited(_vertex.size(), false);
visited[srci] = true;
int levelsize = 1;
while (!q.empty())
{
for (int i = 0; i < levelsize; i++)
{
int front = q.front();
q.pop();
cout << front << ":" << _vertex[front] << " ";
for (size_t i = 0; i < _vertex.size(); i++)
{
if (_matrix[front][i] != MAX_W)
{
if (visited[i] == false)
{
q.push(i);
visited[i] = true;
}
}
}
}
cout << endl;
levelsize = q.size();
}
}
|
最小生成树
构成最小生成树的原则
- 只能使用图中的边来构成最小生成树
- 只能使用n-1条边来连接图中的n个顶点
- 选用的n-1边不能构成回路
Kruskal
全局贪心的方法，每次在全局查找最小的边，同时判断这个边连接的两个顶点是否会形成环，如果不会形成环，就添加到最小生成树中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
struct Edge
{
size_t _srci;
size_t _dsti;
W _w;
Edge(size_t srci, size_t dsti, W w)
: _srci(srci), _dsti(dsti), _w(w)
{
}
bool operator>(const Edge &e) const
{
return _w > e._w;
}
};
W Kruskal(Self &mintree)
{
mintree._vertex = _vertex;
mintree._indexmap = _indexmap;
mintree._matrix.resize(_vertex.size());
for (size_t i = 0; i < _vertex.size(); i++)
{
mintree._matrix[i].resize(_vertex.size(), MAX_W);
}
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
for (size_t i = 0; i < _vertex.size(); i++)
{
for (size_t j = 0; j < _vertex.size(); j++)
{
if (i < j && _matrix[i][j] != MAX_W)
{
Edge e(i, j, _matrix[i][j]);
pq.push(e);
}
}
}
W total = W();
int n = _vertex.size();
int size = 0;
ufs2::UnionFindSet ufs(n);
while (!pq.empty())
{
Edge min = pq.top();
pq.pop();
if (!ufs.Inset(min._dsti, min._srci))
{
cout << _vertex[min._dsti] << "-" << _vertex[min._srci] << "->" << min._w << endl;
mintree.AddEdge(_vertex[min._srci], _vertex[min._dsti], min._w);
ufs.Union(min._dsti, min._srci);
++size;
total += min._w;
}
}
if (size == n - 1)
{
return total;
}
else
return W();
}
|
Prim
局部贪心的方法，通过已经进入最小生成树的顶点和未进入最小生成树的顶点中，查找最小的边
通过优先级队列来记录所有已经进入树中延伸出去的所有边，每次查找里面最小的边，找到了判断是否已经在树中，如果已经在了，说明成环了，就继续，没有成环就添加入树中，同时把该顶点未添加到树中的所有边添加入队列中，进行下一次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
W Prim(Self &mintree, const V &src)
{
int n = _vertex.size();
int srci = GetVertexIndex(src);
mintree._vertex = _vertex;
mintree._indexmap = _indexmap;
mintree._matrix.resize(_vertex.size());
for (size_t i = 0; i < _vertex.size(); i++)
{
mintree._matrix[i].resize(_vertex.size(), MAX_W);
}
vector<bool> X(n, false);
vector<bool> Y(n, true);
X[srci] = true;
Y[srci] = false;
priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
for (size_t i = 0; i < n; i++)
{
if (_matrix[srci][i] != MAX_W)
{
minq.push(Edge(srci, i, _matrix[srci][i]));
}
}
int size = 0;
W total = W();
while (!minq.empty())
{
Edge min = minq.top();
minq.pop();
if (X[min._dsti])
{
continue;
}
mintree.AddEdge(_vertex[min._srci], _vertex[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();
}
|
最短路径
在带权有相图G中的某个顶点出发，找到通往另一个顶点的最短路径，最短也就是路径的权值总和最短
Djkstra
单源最短路径:一个源顶点到每个顶点之间的最短路径
如源顶点为S，图中的顶点有A，B，C，D
计算S-D,S-B,S-A,S-C这些路径的最短路径
使用一个dist数组来记录最小路径，ppath来记录自己的父亲是谁
从一个已经确定最小路径进行查找他延伸出去的边，进行更性这些顶点的路径最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
void Dijkstra(const V &src, vector<W> &dist, vector<int> &pPath)
{
size_t srci = GetVertexIndex(src);
size_t n = _vertex.size();
dist.resize(n, MAX_W);
pPath.resize(n, -1);
dist[srci] = 0;
pPath[srci] = srci;
vector<bool> s(n, false);
for (int j = 0; j < n; j++)
{
int u = 0;
W min = MAX_W;
for (size_t i = 0; i < n; i++)
{
if (s[i] == false && dist[i] < min)
{
u = i;
min = dist[i];
}
}
s[u] = true;
for (size_t v = 0; v < n; v++)
{
if (s[v]==false&&_matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v])
{
dist[v] = dist[u] + _matrix[u][v];
pPath[v] = u;
}
}
}
}
|