第15课：图的概念
进度 0/24
🕸️
图的概念
点与线，织出万物相连的世界！
📖知识引入
🔵顶点与边
图=顶点集合+边集合，城市是点、道路是边
➡️有向与无向
单行道是有向边，双向路是无向边，看清楚再建图
📊度数
与顶点相连的边数叫度，所有点度数之和=2×边数
🧩连通块
互相能到达的点组成一伙，用并查集一数便知有几伙
💡
n个顶点的无向完全图有n(n-1)/2条边——图稠不稠密，决定你选哪种存法
🔍用并查集数连通块
#include <iostream>
using namespace std;
int fa[105];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int main() {
int n = 5; // 5 个点
for (int i = 1; i <= n; i++) fa[i] = i;
fa[find(1)] = find(2); // 加边 (1,2)
fa[find(3)] = find(4); // 加边 (3,4)
int blocks = 0;
for (int i = 1; i <= n; i++)
if (find(i) == i) blocks++; // 根的个数=连通块数
cout << blocks << endl; // 输出 3：{1,2} {3,4} {5}
return 0;
}每加一条边就合并一次，最后数一数有几个根就有几个连通块。
🎯小测验
第1题：图由什么组成？
第2题：无向图所有顶点度数之和与边数的关系？
第3题：统计连通块个数可以用什么数据结构？
📝本课知识点
- ✓图=顶点+边
- ✓度数和=2×边数
- ✓并查集数连通块
第15课完成！继续探索下一课吧 🚀