图图
目录
图的定义
图由两个集合组成:
- 点集 $V$
- 边集 $E$
边分为有向边和无向边，相应的图称为有向图和无向图
相关概念
入度和出度
入度是指直接指向该点的边的数量
出度是指直接从该点指出的边的数量
无向图的入度和出度都一样
表示方法
邻接表法
邻接表就是以点集为单位，每个点记录一个链表，链表中的元素是该点的直接邻居, 不考虑间接邻居
这种方法可以有很强的扩展性, 能表示很多图
例如, 如果边上有权值, 可以把记录的值改为一个自定义结构, 里面记录权值
优点: 能直接看出邻居个数, 空间复杂度低
缺点: 不能直接看出两点是否相连, 时间换空间
邻接矩阵法
邻接矩阵就是用一个正方形的矩阵, 记录每两个点的距离
- 同一个点的距离为0
- 不相连的点的距离为无穷大
优点: 能直接查得两点之间的关系, 时间复杂度低
缺点: 不能直接看出邻居个数
算法模板
定义类
Node
class Node {
public:
int val;
int in;
int out;
vector<Node> nexts;
vector<Edge> edges;
Node(int val) {
this->val = val;
in = 0;
out = 0;
nexts = vector<Node>();
edges = vector<Edge>();
}
};
Edge
class Edge {
public:
int weight;
Node from;
Node to;
Edge(int weight, Node from, Node to) {
this->weight = weight;
this->from = from;
this->to = to;
}
};
无向图的边可以看作是两个有向边拼在一起
Graph
class Graph {
public:
map<int, Node> nodes; // int是节点的编号
set<Edge> edges;
Graph() {
nodes = map<int, Node>();
edges = set<Edge>();
}
};
转化已知信息
用户给的描述方式千奇百怪, 但无外乎描述的是: 点和边
不妨设, 用户给的信息是一个数组:
- 发出点的编号 $from$
- 接收点的编号 $to$
- 权值 $weight$
那么转化为我们熟知的类型就很简单了:
-
检查graph.nodes中是否有这两个点, 没有就创建
cpp
if(!graph.nodes.count(from)) {
graph.nodes[from] = new Node(from);
} -
现在这两个点必然在graph.nodes中了, 所以直接取出来
cpp
Node fromNode = graph.nodes[from];
Node toNode = graph.nodes[to]; -
新建一个edge类, 添加信息, 加入graph.edges中
cpp
Edge newEdge = new Edge(weight, fromNode, toNode);
graph.edges.insert(newEdge); -
别忘了更新点的信息
cpp
fromNode.out++;
toNode.in++;
fromNode.nexts.push_back(toNode);
fromNode.edges.push_back(newEdge);
模板题
图的宽度优先遍历 BFS
上述模板直接使用类的实例传递数据
虽然理论正确, 且在Java中理应实现, 但笔者在C++实践中屡屡碰壁
为此, 之后的代码都采用指针传递(逻辑正确就不太会有错误)
类的定义
#include <bits/stdc++.h>
using namespace std;
class Node;
class Edge;
class Graph;
class Node
{
public:
int value;
int in; // 入度
int out; // 出度
vector<Node *> nexts;
vector<Edge *> edges;
Node()
{
this->value = 0;
this->in = 0;
this->out = 0;
this->nexts = vector<Node *>();
this->edges = vector<Edge *>();
}
Node(int x)
{
this->value = x;
this->in = 0;
this->out = 0;
this->nexts = vector<Node *>();
this->edges = vector<Edge *>();
}
};
class Edge
{
public:
int weight;
Node *from;
Node *to;
Edge()
{
this->weight = 0;
this->from = nullptr;
this->to = nullptr;
}
Edge(int weight, Node *from, Node *to)
{
this->weight = weight;
this->from = from;
this->to = to;
}
};
class Graph
{
public:
map<int, Node *> nodes;
set<Edge *> edges;
Graph()
{
this->nodes = map<int, Node *>();
this->edges = set<Edge *>();
}
Graph(map<int, Node *> nodes, set<Edge *> edges)
{
this->nodes = nodes;
this->edges = edges;
}
};
函数定义
Graph *createGraph(vector<vector<int>> matrix)
{
Graph *g = new Graph();
for (int i = 0; i < matrix.size(); i++)
{
int weight = matrix[i][0];
int fromIndex = matrix[i][1];
int toIndex = matrix[i][2];
if (g->nodes[fromIndex] == nullptr)
{
g->nodes[fromIndex] = new Node(fromIndex);
}
if (g->nodes[toIndex] == nullptr)
{
g->nodes[toIndex] = new Node(toIndex);
}
Node *fromNode = g->nodes[fromIndex];
Node *toNode = g->nodes[toIndex];
Edge *newEdge = new Edge(weight, fromNode, toNode);
g->edges.insert(newEdge);
fromNode->out++;
fromNode->nexts.push_back(toNode);
fromNode->edges.push_back(newEdge);
toNode->in++;
}
return g;
}
void BFS(Node *root)
{
queue<Node *> q;
set<Node *> s;
q.push(root);
s.insert(root);
while (!q.empty())
{
Node *cur = q.front();
q.pop();
cout << cur->value << " ";
for (auto next : cur->nexts)
{
if (!s.count(next))
{
q.push(next);
s.insert(next);
}
}
}
cout << endl;
}
main函数
int main()
{
vector<vector<int>> matrix = {
{1, 1, 2},
{2, 1, 3},
{3, 2, 3},
{4, 2, 4},
{5, 3, 5},
{6, 3, 6},
{7, 5, 2}};
Graph *g = createGraph(matrix);
BFS(g->nodes[1]);
}
图的结构:
输出结果:
1 2 3 4 5 6
图的深度优先遍历 DFS
思路是:
- 走到一个没走过的就处理
- 一条路走到头, 不行就退
- 如果岔路上没走过, 就接着走到底
- 循环, 直到全走过
void DFS(Node *root)
{
stack<Node *> st;
set<Node *> se;
st.push(root);
se.insert(root);
cout << root->value << " ";
while (!st.empty())
{
Node *cur = st.top();
st.pop();
for (auto next : cur->nexts)
{
if (!se.count(next))
{
st.push(cur);
st.push(next);
se.insert(next);
cout << next->value << " ";
break;
}
}
}
cout << endl;
}
main函数
int main()
{
vector<vector<int>> matrix = {
{1, 1, 2},
{2, 1, 3},
{3, 2, 3},
{4, 2, 4},
{5, 3, 5},
{6, 3, 6},
{7, 5, 2}};
Graph *g = createGraph(matrix);
DFS(g->nodes[1]);
}
输出结果:
1 2 3 5 6 4
图的拓扑排序
拓扑排序是从出发节点到被指向节点, 保证每个节点具备所有条件的顺序
拓扑的经典应用就是文件开发中的 依赖关系
A库要求importB,C,D, 相当于由B,C,D各有一个edge指向A
又因为不存在循环依赖的情况, 因此, 编译的实质是一个 有向图
编译器要通过拓扑排序才能正确找到编译的顺序
实现思路:
- 找到入度为0的点
- 处理ta
- 消除其影响
- 减去其nexts的入度
- 删除该点
- 循环
vector<Node *> sortedTopology(Graph *g)
{
map<Node *, int> m;
queue<Node *> zeroQ;
for (auto i : g->nodes)
{
if (i.second->in == 0)
{
zeroQ.push(i.second);
}
else
{
m[i.second] = i.second->in;
}
}
// for (int i = 1; i <= 6; i++)
// {
// cout << m[g->nodes[i]] << " ";
// }
// cout << endl;
// for (Node *q = zeroQ.front(); q != zeroQ.back(); q++)
// {
// cout << q->value << " ";
// }
// cout << zeroQ.back()->value << endl;
vector<Node *> ansList;
while (!zeroQ.empty())
{
Node *cur = zeroQ.front();
ansList.push_back(cur);
zeroQ.pop();
for (Node *next : cur->nexts)
{
if (--m[next] == 0)
{
zeroQ.push(next);
}
}
}
return ansList;
}
int main()
{
vector<vector<int>> matrix = {
{1, 1, 2},
{2, 1, 3},
{3, 2, 3},
{4, 2, 4},
{5, 3, 5},
{6, 3, 6},
// {7, 5, 2}, 拓扑排序不能出现环
};
Graph *g = createGraph(matrix);
vector<Node *> v = sortedTopology(g);
cout << v.size() << endl;
for (auto i : v)
{
cout << i->value << " ";
}
cout << endl;
}
注意这里遍历map的技巧:
for (auto i : g->nodes)
这里的i改成pair更好, 表示一个 键值对
而且该键值对是以指针的形式赋给i因此
- 调用键要用
i->first- 调用值要用
i->second
算法
以下两个算法适用于无向图, 效果是生成最小生成树
最小生成树是指, 在保证连通性的情况下
保留一些边, 且使得最终得到的各边权重累加和最小
图示:
Kruskal 算法
分析
逻辑是:
- 按照权值排序所有的
edge, 从小到大遍历 - 如果某个
edge置入新图后不产生环, 则该edge保留
关于对环的判断, 要用到对集合查询的机制来实现:
- 先不妨假设所有
node都是单元素的集合 - 对于一个
edge的两个端点, 查询两node所处在的集合是否为同一个 - 若集合为同一个则意味着会产生环, 弃之不要
- 反之, 保留
edge, 并合并两点所在集合
并查集替代写法1
对于集合的查询和合并, 有个机制叫 并查集结构
能做到又快又好, 但code逻辑较为复杂, 此处使用替代方法实现
class MySets
{
map<Node *, list<Node *>> setMap;
public:
void setUp(vector<Node *> nodes)
{
for (auto node : nodes)
{
list<Node *> l;
l.push_back(node);
setMap[node] = l;
}
}
bool isSameSet(Node *fromNode, Node *toNode)
{
list<Node *> fromSet = setMap[fromNode];
list<Node *> toSet = setMap[toNode];
return fromSet == toSet;
}
void mergeSet(Node *fromNode, Node *toNode)
{
list<Node *> fromSet = setMap[fromNode];
list<Node *> toSet = setMap[toNode];
for (auto from : fromSet)
{
setMap[from] = toSet;
toSet.push_back(from);
}
}
};
并查集替代写法2
但是笔者在mergeSet环节摸不着头脑地找不到错误!
可能是由于list的生存周期问题, 使得setMap并未按预期修改
因此作为替代, 笔者想出另一种替代:
class MySets
{
public:
map<Node *, Node *> setMap;
void setUp(map<int, Node *> nodes)
{
for (auto pair : nodes)
{
setMap[pair.second] = pair.second;
}
}
bool isSameSet(Node *fromNode, Node *toNode)
{
return setMap[fromNode] == setMap[toNode];
}
void mergeSet(Node *fromNode, Node *toNode)
{
Node *from = setMap[fromNode];
Node *to = setMap[toNode];
for (auto pair : setMap)
{
if (pair.second == from)
{
setMap[pair.first] = to;
}
}
}
};
思路是:
setMap的键值对代表这个节点听谁的:
- 键: 各个节点
- 值: “听谁的”
相当于, 连在一起的节点可以看做是一块地皮, 一块地皮上的所有节点只能听一个人的
那么isSameSet的逻辑就是看两个节点是不是听同一个人的
mergeSet的逻辑就是让一块地皮上所有人改为听从另一块地皮的老大
算法实现
有了以上的机制, 可以实现Kruskal算法
set<Edge *> KruskalMST(Graph *g)
{
MySets unionFind;
unionFind.setUp(g->nodes);
struct edgeCmp
{
bool operator()(Edge *e1, Edge *e2) const
{
return e1->weight > e2->weight;
}
};
priority_queue<Edge *, vector<Edge *>, edgeCmp> q;
for (auto edge : g->edges)
{
q.push(edge);
}
set<Edge *> ansSet;
while (!q.empty())
{
Edge *cur = q.top();
q.pop();
Node *from = cur->from;
Node *to = cur->to;
if (!unionFind.isSameSet(from, to))
{
ansSet.insert(cur);
unionFind.mergeSet(from, to);
}
}
return ansSet;
}
这里为了以权重从小到大考虑
edge
因此采用优先级队列, 注意其写法
使用实例
int main()
{
vector<vector<int>> matrix = {
{1, 1, 2},
{2, 1, 3},
{3, 2, 3},
{4, 2, 4},
{5, 3, 5},
{6, 3, 6},
{7, 5, 2},
};
Graph *g = createUndirectedGraph(matrix);
set<Edge *> kruskalEdgeSet = KruskalMST(g);
for (auto e : kruskalEdgeSet)
{
cout << e->weight << "\t"
<< e->from->value << "\t"
<< e->to->value << endl;
}
}
由于要使用无向图, 因此在原来的函数上做微调, 改为
createUndirectedGraph
其实有向和无向, 对于Edge而言不过是理解上的不同, 只要将两端节点一视同仁即可
而对于Node而言, 入度 / 出度 /nexts/edges要做出相应调整
cpp
Edge *newEdge = new Edge(weight, fromNode, toNode);
g->edges.insert(newEdge);
fromNode->out++;
fromNode->nexts.push_back(toNode);
fromNode->edges.push_back(newEdge);
toNode->in++;
toNode->out++;
toNode->nexts.push_back(fromNode);
toNode->edges.push_back(newEdge);
fromNode->in++;BTW, 时间复杂度为$O(ElogE)$, 适用于
E远小于V的情况, 即稀疏图
Prim 算法
该算法从Graph中一个Node开始, 且与从哪个节点开始无关
分析
逻辑如下:
- 从一个
Node开始, “解锁”其临边, 即, 直接连接的Edge加入一个集合中 - 选择所有已解锁的临边中 权值最小的那个
Edge, 这条边一定在答案中 - 将这个
Edge连接的Node作为对象继续上述操作, 解锁其所连接的Edge - 之后以权值从小到大考虑所有 已解锁的
Edge - 如果
Edge的两端的Node都被 访问 过, 那么不考虑 - 直到所有
Node都访问完为止
可以想象为”探岛”
已解锁的Edge就是可以走的路, 其权重可以想象为岛和岛间小怪的强度
如果两个岛都去过, 那么肯定不用去打中间那个怪了
然后如果要向外探索的话, 优先选择代价最小的那个Edge
算法实现
set<Edge *> PrimMST(Graph *g)
{
struct edgeCmp
{
bool operator()(Edge *e1, Edge *e2) const
{
return e1->weight > e2->weight;
}
};
priority_queue<Edge *, vector<Edge *>, edgeCmp> unlockedEdges;
set<Node *> visitedNodes;
set<Edge *> ansSet;
for (auto pair : g->nodes)
{
Node *cur = pair.second;
visitedNodes.insert(cur);
for (auto e : cur->edges)
{
unlockedEdges.push(e);
}
while (!unlockedEdges.empty())
{
Edge *curEdge = unlockedEdges.top();
unlockedEdges.pop();
bool flag = visitedNodes.count(curEdge->from) == 0;
if (!flag && visitedNodes.count(curEdge->to) != 0)
{
continue;
}
ansSet.insert(curEdge);
cur = flag ? curEdge->from : curEdge->to;
visitedNodes.insert(cur);
for (auto e : cur->edges)
{
unlockedEdges.push(e);
}
}
}
return ansSet;
}
既然该算法可以完整遍历所有节点, 为什么会有
for (auto pair : g->nodes)这一行?
这是为了兼容 “森林” 的情况
如果给出的是一个 非联通无向图, 那么要求就变为: 所有连通部分都为最小生成树该算法会将同一个
Edge重复两次, 但会因为不满足条件被直接排除
优化的方案是用一个set来去重, 这里实现方法在之前多个算法中都要类似情况, 不再赘述
使用实例
int main()
{
vector<vector<int>> matrix = {
{1, 1, 2},
{2, 1, 4},
{3, 1, 5},
{4, 3, 4},
{5, 3, 5},
{6, 4, 5},
{7, 6, 7},
{8, 6, 8},
{9, 6, 9},
{10, 7, 8},
{11, 8, 9},
};
Graph *g = createUndirectedGraph(matrix);
set<Edge *> kruskalEdgeSet = PrimMST(g);
for (auto e : kruskalEdgeSet)
{
cout << e->weight << "\t"
<< e->from->value << "\t"
<< e->to->value << endl;
}
}
图示:
Prim算法的时间复杂度为$O(n^2)$, 适用于稠密图
Di jkstra 算法
读作”迪J科斯拉”(雾)?
也称为 单元最短路径算法
不同于前面两个算法, 该算法还要求Edge权值不为负
该算法的效果是:
- 必须从一个点出发
- 返回一个表格, 表示该出发点到其他的各个点的最短距离(可以是多个边的权值的和)
其中, 特别的, 如果一个点无法到达, 则距离为正无穷(或者系统最大值)
之所以权值不能为负是因为:
如果存在这样的边, 那么在这个边上来回踱步就能让距离变成无穷小, 问题也就没有意义了
分析
首先, 初始化表格: 到自己距离为0, 其余为正无穷
接下来, 流程如下:
- 取距离最小的那个点
- 考察从该点出发(要加上出发点到该点的距离), 能否可以使到邻居的距离缩短
- 如果比现有情况好, 就更新
- 所有邻居考察完毕, 锁定现在的这个点
- 再从未锁定的点中找最小的距离, 重复, 直至所有点均被锁定
代码实现
map<Node *, int> DiJkstra(Graph *g, Node *startNode)
{
// 初始化
map<Node *, int> bufMap;
map<Node *, int> ansMap;
int nodeCount = 0;
for (auto pair : g->nodes)
{
bufMap[pair.second] = INT_MAX;
nodeCount++;
}
bufMap[startNode] = 0;
while (--nodeCount > 0) // 处理到最后一个节点的时候, 必定其余都锁定
{
// 选出表格中最小的
Node *cur = startNode;
int minDistance = INT_MAX;
for (auto pair : bufMap)
{
if (pair.second < minDistance)
{
cur = pair.first;
minDistance = bufMap[cur];
}
}
// 考察邻居能不能改进
for (Edge *e : cur->edges)
{
if (bufMap.count(e->to) && bufMap[e->to] > bufMap[cur] + (e->weight))
{
bufMap[e->to] = bufMap[cur] + (e->weight);
}
}
// 锁定该点
ansMap[cur] = bufMap[cur];
bufMap.erase(cur);
}
// 别落下最后一位
auto lastNodePair = bufMap.begin();
ansMap[lastNodePair->first] = lastNodePair->second;
return ansMap;
}
这里笔者的code思路是:
如果一个Node被锁定了, 相当于不再考虑了
那么与其额外做一个登记数组, 不如直接从考虑范围内摘出来
然后放到一个答案数组中
之后只要在现有的(也就是未锁定的)Node考虑即可另外, 到最后一位时, 其余全部被锁定, 也就可以直接跳
关于优化, 可以考虑用堆来实现
但是, 由于数据会变小(如果被更新了), 那么用系统自带的堆实现的话, 其代价和遍历相当
因此要考虑使用自定义的堆结构
使用实例
int main()
{
vector<vector<int>> matrix = {
{1, 1, 2},
{2, 1, 4},
{3, 1, 5},
{4, 3, 4},
{5, 3, 5},
{6, 4, 5},
{7, 6, 7},
{8, 6, 8},
{9, 6, 9},
{10, 7, 8},
{11, 8, 9},
{12, 3, 9},
};
Graph *g = createUndirectedGraph(matrix);
map<Node *, int> m = DiJkstra(g, g->nodes[1]);
for (int i = 1; i <= 9; i++)
{
cout << i << "\t";
}
cout << endl;
for (int i = 1; i <= 9; i++)
{
cout << m[g->nodes[i]] << "\t";
}
cout << endl;
}
这里的样例同上, 多加了一个
{12, 3, 9}将两个森林连在了一起ending
