图论是NOIP的一个非常重要的考点,换句话说,没有图论,NOIP的考纲就得少一大半(虽然很NOIP没有考纲)
图论这玩意吧,和数论一样是非常变态的东西,知识点又多又杂,但是好在一个事,他比较直观比较好想
图
对于一张图而言,我们定义图是一种由边和点构成的的一个玩意(其实是严谨定义我记不住了QWQ,但是不影响学习)
一般来说,图的存储难度主要在记录边的信息
无向图的存储中,只需要将一条无向边拆成两条即可
邻接矩阵:用一个二维数组 edg[N][N] 表示
edg[i][j] 就对应由
i 到 j 的边信息
edg[i][j] 可以记录 Bool,也可以记录边权
缺点:如果有重边有时候不好处理
空间复杂度 O(V^2)
点度等额外信息也是很好维护的
#include <bits/stdc++.h> using namespace std; const int N = ; int ideg[N], odeg[N], n, m, edg[N][N];
bool visited[N]; void travel(int u, int distance)
{
cout << u << " " << distance << endl; visited[u] = true;
for (int v = ; v <= n; v++)
if (edg[u][v] != - && !visited[v])//是否已经访问过
travel(v, distance + edg[u][v]); //if there is an edge (u, v) and v has not been visited, then travel(v)
}
int main()
{
cin >> n >> m;
memset(edg, -, sizeof edg);
memset(visited, false, sizeof visited);
for (int u, v, w, i = ; i <= m; i++)
cin >> u >> v >> w, edg[u][v] = w, odeg[u]++, ideg[v]++;//出度和入度
for (int i = ; i <= n; i++)
cout << ideg[i] << " " << odeg[i] << endl;
for (int i = ; i <= n; i++)
if (!visited[i]) travel(i, );
} /*
Given a graph with N nodes and M unidirectional edges.
Each edge e_i starts from u_i to v_i and weights w_i
Output a travelsal from node 1 and output degree of each node.
*/
其实这个英文注释也还蛮不错的啊
邻接矩阵本质上其实就是一个二维数组,它在存储一个稠密图的时候效率比较好,但是稀松图的话就非常浪费空间
所以我们就没有必要用二维数组记录信息,我们只需要对每一个点记录他的出边就行
这样记的话,复杂度就是他的边数
对每一个点 u 记录一个 List[u],包含所有从 u 出发的边
直接用数组实现 List[u]?读入边之前不知道 List[u] 长度
手写链表(链式前向星)
用 STL 中的 vector 实现变长数组,当然你想要手写指针也没问题
只需要 O(V + E) 的空间就能实现图的存储(边数加点数)
其实写这个链表存储0有很多方式啊,你可以用指针,手写指针,也可以用vector ,还可以用数组毛模拟
我们详细理解一下代码
#include <bits/stdc++.h> using namespace std; const int N = ; struct edge {
int u, v, w; edge *next;//next指针指向
edge(int _u, int _v, int _w, edge *_next):
u(_u), v(_v), w(_w), next(_next) {}
};
edge *head[N]; //List[u] 最前面的节点是谁
int ideg[N], odeg[N], n, m;
bool visited[N]; void add(int u, int v, int w)
{
edge *e = new edge(u, v, w, head[u]);
head[u] = e;
}
void travel(int u, int distance)
{
cout << u << " " << distance << endl; visited[u] = true;
for (edge *e = head[u]; e ; e = e -> next)
if (!visited[e -> v])
travel(e -> v, distance + e -> w); //if there is an edge (u, v) and v has not been visited, then travel(v)
}
int main()
{
cin >> n >> m;
memset(visited, false, sizeof visited);
memset(head, , sizeof head);
for (int u, v, w, i = ; i <= m; i++)
cin >> u >> v >> w, add(u, v, w), odeg[u]++, ideg[v]++;
for (int i = ; i <= n; i++)
cout << ideg[i] << " " << odeg[i] << endl;
for (int i = ; i <= n; i++)
if (!visited[i]) travel(i, );
} /*
Given a graph with N nodes and M unidirectional edges.
Each edge e_i starts from u_i to v_i and weights w_i
Output a travelsal from node 1 and output degree of each node.
*/
但是我个人是不用指针的,因为可能还是不习惯的原因吧,而且指针的写法并没有什么特别的优点
还有一个数组模拟版本
#include <bits/stdc++.h> using namespace std; const int N = ; struct edge {
int u, v, w, next;
}edg[N];
int head[N]; //List[u] stores all edges start from u
int ideg[N], odeg[N], n, m, cnt; //cnt: numbers of edges
bool visited[N]; void add(int u, int v, int w)
{
int e = ++cnt;
edg[e] = (edge){u, v, w, head[u]};
head[u] = e;
}
void travel(int u, int distance)
{
cout << u << " " << distance << endl; visited[u] = true;
for (int e = head[u]; e ; e = edg[e].next)
if (!visited[edg[e].v])
travel(edg[e].v, distance + edg[e].w); //if there is an edge (u, v) and v has not been visited, then travel(v)
}
int main()
{
cin >> n >> m; cnt = ;
memset(visited, false, sizeof visited);
memset(head, , sizeof head);
for (int u, v, w, i = ; i <= m; i++)
cin >> u >> v >> w, add(u, v, w), odeg[u]++, ideg[v]++;
for (int i = ; i <= n; i++)
cout << ideg[i] << " " << odeg[i] << endl;
for (int i = ; i <= n; i++)
if (!visited[i]) travel(i, );
} /*
Given a graph with N nodes and M unidirectional edges.
Each edge e_i starts from u_i to v_i and weights w_i
Output a travelsal from node 1 and output degree of each node.
*/
但是数组模拟必然是逃不开浪费时间过多的,这个事就很讨厌了,邻接矩阵以其优秀的可读性以及构造性换来了不少空间,唉
我个人现在是这样的,判断变数和点数的值,如果差别较大,那么出题人可能是想构造菊花树之类的,差别较小就意味着稠密,那么写邻接矩阵更节省时间(前提是你两个都能用)
还有一种写法是用vector
抛去邻接矩阵不讲,如果我们用edg[u][i]表示从u出发的第i条边,这样实际上还是O(n^2)的,所以我们要用一个能够自己改变长度的STL,这样能让空间最大化
#include <bits/stdc++.h> using namespace std; const int N = ; struct edge {
int u, v, w;
};
vector<edge> edg[N]; //edge记录变长数组记录的是什么类型
int ideg[N], odeg[N], n, m, cnt; //cnt: numbers of edges
bool visited[N]; void add(int u, int v, int w)
{
edg[u].push_back((edge){u, v, w});//一个强制类型转换
}
void travel(int u, int distance)
{
cout << u << " " << distance << endl; visited[u] = true;
for (int e = ; e < edg[u].size(); e++)//遍历边
if (!visited[edg[u][e].v])//以u出发的第e条出边
travel(edg[u][e].v, distance + edg[u][e].w); //if there is an edge (u, v) and v has not been visited, then travel(v)
}
int main()
{
cin >> n >> m; cnt = ;
memset(visited, false, sizeof visited);
for (int u, v, w, i = ; i <= m; i++)
cin >> u >> v >> w, add(u, v, w), odeg[u]++, ideg[v]++;
for (int i = ; i <= n; i++)
cout << ideg[i] << " " << odeg[i] << endl;
for (int i = ; i <= n; i++)
if (!visited[i]) travel(i, );
} /*
Given a graph with N nodes and M unidirectional edges.
Each edge e_i starts from u_i to v_i and weights w_i
Output a travelsal from node 1 and output degree of each node.
*/
要注意的是,c++的STL数组默认都是以0为结尾的、
vector是这样构造的
<>里面写的是变量类型,可以是int 或者float或者结构体
生成树
我们考虑一个联通的无向图,我们考虑找出这个图当中的子图(点的数量是一样的,可以删掉边)
给定一个连通无向图 G = (V; E)
E′ ⊂ E
G′ =
(V; E′) 构成一棵树
G′ 就是 G 的一个生成树
而且我们可以发现生成树不是唯一的,而且我们可以知道的是生成树的数量是指数级别的
那么最小生成树其实就是生成树当中最大边权的值最小
怎么求呢?
Algorithms for Minimal Spanning Tree:
Kruskal
Prim
Kosaraju
Kruskal
克鲁斯卡尔的思想是贪心加上并查集
我们只把所有的边的信息存下来,而不用存图(因为最小生成树只问你最小边权和之类的问题,而不文)
,对于所有的边权进行排序,找到当前边权最小的边 e : (u; v)
如果 u 和 v 已经连通,则直接删除这条边(这里的判断就是用并查集的思想,如果最终并查集的指向指到了一个同一个点,那么就是联通的啊)
如果 u 和 v 已经未连通,将之加入生成树
重复上述过程
这个称为Rigorous proof(消圈算法)
Kruskal的证明方法很迷啊,就感性理解一下就好
毕竟贪心这东西证明正确性还是挺困难的。
Prim的做法是,我们找一个连通块,我们把和这个连通块最短的点加到连通块当中去(这俩都可以用堆优化)
Kosaraju的做法是,我们有很多连通块,然后第一轮的时候对于每一个连通块找到和它相连的最短的边,就把这两个集合连接起来