#创作计划#图论基础
2025-08-19 11:13:09
发布于：浙江
噢噢噢噢噢噢噢噢噢噢噢噢噢噢噢噢被加精力！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
感谢@AC君谢谢谢谢谢谢谢谢谢谢
小萌新发帖，望大佬支持
孩子们这并不好笑，但谁知道我有一天心血来潮作死想把近1000字的笔记打到电脑上去
正文：
图论基础
一，图的概念
1，定义：图是一种由顶点和边组成的非线性数据结构，顶点表示数据内容，边表示关系
2，分类：(1),无向图(或称为“无向网络”“无向图形”)：由没有方向的边组成的图
(2),有向图：由有方向的边组成的图
(3),权图：边上带有权值的图（权值：边的权重(weight)）
3，简单图和多重图：
(1),自环和重边：
①，自环：边的两端是同一个节点
②，重边：连接同两个结点的多条边
(2),简单图：不存在自环和重边的图
(3),多重图：存在自环和重边的图
4，图的度：指与一个结点相连的边的数量
(1),无向图：与目标节点相连的边数
(2),有向图：
①，入度：指向该节点的边数
②，出度：从该节点出发的边数
5，路径：
(1),定义：从一个结点到另一个结点的连续边构成的序列
(2).路径长度：一路径中经过边的数量(或权值和)
(3),分类：
①，简单路径：从一个节点到另一个结点的不重复序列
②，非简单路径：从一个节点到另一个结点的可重复序列
注意：有向图的路径必须遵循边的方向
6，环路：
(1),定义：起点和终点相同的路径
(2),分类：
①，简单环路：起点和终点相同的不重复路径
②，非简单环路：起点和终点相同的可重复路径
注意：不包括任何环路的图叫无环图
7，连通图：
(1),定义：任意两点间都存在路径的图(可以不是直接路径)
(2),分类：①强连通图；②若连通图；③非连通图。
注意：强连通图和弱连通图是相对的
8，完全图：
(1),无向完全图(UCG)：
①定义：图中任意两点间均存在一条无向边
②边数：n(n-1)/2
(2),有向完全图(DCG):
①定义：图中任意两点间均存在方向相反的两条边
②边数：n(n-1)
9，稠密图和稀疏图(相对概念)
(1),稀疏图：图中边较少，边之间连接相对稀疏
(2),稠密图：图中边较多，边之间连接相对稠密
二，图的存储
1，目标：存储图的顶点信息和边信息
2，方法：
(1),邻接矩阵：一维数组+二维数组
①一维数组V[i]：存储i顶点的信息
②二维数组G[i][j]：存储边的信息(如:权值，端点，这个需要用到结构体进行绑定)，G[i][j]表示从顶点i到j这条边
③优点：时间复杂度低(仅为O(1))
④缺点：需求的空间过大
有向图单项存储，无向图双向存储
适用于稠密图
例：(无向图)
输入：5 5 | 1 2 | 2 3 | 3 4 | 4 5 | 5 1 ("|"表示换行)
特殊性质：无向图的邻接矩阵关于x = y对称
(2),邻接表：vector数组，结构体(常用)
①vector数组：存储顶点的所有邻接点和边的数据
②结构体：将边与权值绑定
③优点：省空间
适用于稀疏图
例：(无向图)
输入：5 5 | 1 2 | 2 3 | 3 4 | 4 5 | 5 1 ("|"表示换行)
三，图的遍历
1，图的深度优先遍历：
例：
给定一个无向图，
第一行输入两个数字n,m，分别代表无向图的顶点数和边数
接下来m行，输入两个数字u,v代表u,v间有一条无向边，保证该图是连通图
遍历所有节点并输出
#include<iostream>
#include<vector>
using namespace std;
int n,m;
bool flag[100010];//标记数组
vector<int> pic[100010];//邻接表(动态二维数组)：统计无向边
void dfs(int x){//深度优先搜索
flag[x] = 1;//初始化
cout << x << " ";//输出
for(int i = 0;i < pic[x].size();i++){//遍历所有邻接点
if(flag[pic[x][i]] == 0){
flag[pic[x][i]] = 1;
dfs(pic[x][i]);//递归
}
}
}
int main(){
cin >> n >> m;
while(m--){
int u,v;
cin >> u >> v;
pic[u].push_back(v);
pic[v].push_back(u);//无向图双向存储
}
dfs(1);//从1开始遍历
return 0;
}
2，图的广度优先遍历：(个人比较喜欢用这个，因为手贱想多打点更习惯广搜的逻辑)
例：
给定一个无向图，
第一行输入两个数字n,m，分别代表无向图的顶点数和边数
接下来m行，输入两个数字u,v代表u,v间有一条无向边，保证该图是连通图
遍历所有节点并输出
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m;
bool flag[100010];//标记数组
vector<int> pic[100010];//邻接表(动态二维数组)：统计无向边
void bfs(int x){
queue<int> q;
q.push(x);
flag[x] = 1;//初始化
while(!q.empty()){
int t = q.front();
q.pop();
cout << t << " ";
for(int i = 0;i < pic[t].size();i++){
if(flag[pic[t][i]] == 0){
flag[pic[t][i]] = 1;
q.push(pic[t][i]);
}
}
}
}
int main(){
cin >> n >> m;
while(m--){
int u,v;
cin >> u >> v;
pic[u].push_back(v);
pic[v].push_back(u);//无向图双向存储
}
bfs(1);//从1开始遍历
return 0;
}
四，推荐题目
图的题单
个人觉得比较基础的题与较难的题都在这里面了，欢迎各位大佬们来尝尝咸淡
来道题吧
这道题很简单，就是遍历一遍看谁没有被标记就进去广搜并计数即可
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m,cnt = 0;
bool flag[110];
vector<int> pic[110];
void bfs(int x){//广度优先搜索
queue<int> q;
q.push(x);//初始化
while(!q.empty()){//在队列不空时继续搜索
int k = q.front();//临时变量
q.pop();
for(int j = 0;j < pic[k].size();j++){
if(flag[pic[k][j]] == 0){
q.push(pic[k][j]);
flag[pic[k][j]] = 1;//标记
}
}
}
}
int main(){
cin >> n >> m;
while(m--){
int u,v;
cin >> u >> v;
pic[u].push_back(v);
pic[v].push_back(u); //无向图
}
for(int i = 1;i <= n;i++){
if(flag[i] == 0){
flag[i] = 1;
bfs(i);
cnt++;//计数
}
}
cout << cnt;
return 0;
}
再来一个
这个稍难一点，那也只需在队列弹出后计数即可
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m,cnt = 0;
bool flag[100010];
vector<int> pic[100010];
void bfs(int x){//广度优先搜索
queue<int> q;
q.push(x);
flag[x] = 1;
while(!q.empty()){
int k = q.front();
q.pop();
cnt++;//在队列弹出后计数
for(int j = 0;j < pic[k].size();j++){
if(flag[pic[k][j]] == 0){
q.push(pic[k][j]);
flag[pic[k][j]] = 1;
}
}
}
}
int main(){
cin >> n >> m;
while(m--){
int u,v;
cin >> u >> v;
pic[u].push_back(v);
pic[v].push_back(u); //无向图
}
int x,y;
cin >> x >> y;
bfs(x);//从x开始搜
if(flag[y] == 0) cout << 0;
else cout << cnt;
return 0;
}
(看看我这个小透明吧码字好累)求赞@AC君
全部评论 24
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
1周前 来自 浙江
0dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
2025-08-19 来自 浙江
0dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
2025-08-19 来自 浙江
0dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
2025-08-18 来自 浙江
0dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
2025-08-18 来自 浙江
0那我要是把我的笔记打上去......我先比个如：
家用PC操作系统：Windows 9X、2000、XP、7、8、10、vista。；
苹果操作系统：Mac、OS X。；
手机：iOS,Android。；......
不打了不打了，有点头疼。
2025-08-18 来自 浙江
0
有帮助，赞一个