图的基本概念
图论的一些概念和细节一开始是上算法的时候看助教大大的教程学的。放个链接，这里是️不堪回首胆战心惊的算法课作业、资料github仓库，谢师生情。
-
G（V，E）
Vertex为点集，Edge为边集 -
有向图、无向图
-
顶点的度：出度、入度
-
点权、边权
-
DAG：Directed Acyclic Graph 有向无环图
-
子图
-
连通分量（极大连通子图）、连通图、非连通图
-
有向图 — 强连通分量（极大强连通子图）、强连通图、非强连通图
-
欧拉图、哈密顿图
-
图 vs 树：树是点数比边数多1的连通无向图（除了根结点，每个结点都有一条到父结点的边）
-
树的直径
树（即 无向无环无权、边数为 点数-1 的连通图，树可以以任何结点为根）上任意点对之间最短路径长度最大值，两个点一定都是叶子。
求法：两次DFS（或两次BFS）
b站大佬讲解CLRS 22.2-8 树的直径
图的存储
- 邻接矩阵：适于点数不太多的图，稠密图
- 邻接表：适于稀疏图，用stl的vector实现很方便
图的遍历
️注意设定visited bool数组，防止重复访问（在环里出不来啦！！！）
- DFS：递归
- BFS：queue ️一定要注意push的时候设置visited为true，而非pop时！！若不在入队时就设置为访问过，可能会重复入队
例
1076 Forwards on Weibo (30 分)
- 此题dfs做极其恶心，因为dfs最开始找到的路不一定是最少步数的。
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int nn, indirect_lvl, fl_cnt, levels[1001];
bool graph[1001][1001] = {false}; // 1 - N
bool visited[1001] = {false};
void BFS(int root) {
queue<int> mq;
levels[root] = 0;
mq.push(root);
visited[root] = true;
while (!mq.empty()) {
int curr = mq.front();
mq.pop();
for (int i = 1; i <= nn; ++i) {
if (graph[curr][i] && !visited[i] && levels[curr] < indirect_lvl) {
mq.push(i);
visited[i] = true;
levels[i] = levels[curr] + 1;
if (levels[i] > 0) fl_cnt++;
}
}
}
}
int main() {
scanf("%d%d", &nn, &indirect_lvl);
for (int i = 1; i <= nn; ++i) {
int tn, temp;
scanf("%d", &tn);
for (int j = 0; j < tn; ++j) {
scanf("%d", &temp);
graph[temp][i] = true;
}
}
int kk;
scanf("%d", &kk);
for (int i = 0; i < kk; ++i) {
int root;
scanf("%d", &root);
fl_cnt = 0;
fill(visited + 1, visited + nn + 1, false);
fill(levels + 1, levels + nn + 1, 0);
BFS(root);
printf("%d\n", fl_cnt);
}
return 0;
}
1013 Battle Over Cities (25 分)
求连通分量个数即可。
- DFS
由于要多次删掉一个点和相连的边，所以用了邻接矩阵。看了算法笔记，发现用vector也不算繁。
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int nn, mm, kk;
bool graph[1001][1001] = {false}, visited[1001];
void dfs(int root, int _ignore) {
visited[root] = true;
for (int i = 1; i <= nn; ++i) {
if (graph[root][i] && !visited[i] && i != _ignore) {
dfs(i, _ignore);
}
}
}
int main() {
scanf("%d%d%d", &nn, &mm, &kk);
int v1, v2;
for (int i = 0; i < mm; ++i) {
scanf("%d%d", &v1, &v2);
graph[v1][v2] = graph[v2][v1] = true;
}
int no;
for (int i = 0; i < kk; ++i) {
scanf("%d", &no);
int cnt = 0;
fill(visited, visited + nn + 1, false);
for (int j = 1; j <= nn; ++j) {
if (j != no && !visited[j]) {
dfs(j, no);
cnt++;
}
}
printf("%d\n", cnt - 1);
}
return 0;
}
- 并查集也可以很方便的解决！
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int nn, mm, kk;
bool graph[1001][1001] = {false};
int father[1001];
int _find(int curr) {
return father[curr] < 0 ? curr : father[curr] = _find(father[curr]);
}
void _union(int a, int b) {
a = _find(a);
b = _find(b);
if (a != b) {
father[a] += father[b];
father[b] = a;
}
}
int main() {
scanf("%d%d%d", &nn, &mm, &kk);
int v1, v2;
for (int i = 0; i < mm; ++i) {
scanf("%d%d", &v1, &v2);
graph[v1][v2] = graph[v2][v1] = true;
}
int no;
for (int i = 0; i < kk; ++i) {
scanf("%d", &no);
fill(father + 1, father + nn + 1, -1);
for (int j = 1; j <= nn; ++j) {
if (j != no) {
for (int k = 1; k <= nn; ++k) {
if (graph[j][k] && k != no)
_union(j, k);
}
}
}
for (int j = 1; j <= nn; ++j) {
if (j == no) continue;
_find(j); //小心啊啊啊啊啊 father[j] = _find[j]什么鬼
}
int cnt = 0;
for (int j = 1; j <= nn; ++j) {
if (j == no) continue;
if (father[j] < 0) cnt++;
}
printf("%d\n", cnt - 1);
}
return 0;
}
网友评论