文章目录
- 图的定义和基本术语
- 图的存储
-
- 邻接矩阵
- 邻接表
- 图的遍历
-
- 深度优先遍历
- 广度优先遍历
图的定义和基本术语
文章图片
图的存储 邻接矩阵
文章图片
图论中的建表小技巧:最大值为0x3f,最小值为0xc0。以下是常见的数组初始化技巧:
如果是int数组:
int类型范围:-2147483648~2147483647
memset(a,127,sizeof(a)),全部初始化为int的较大值,即2139062143(int 最大值为2147483647);
memset(a,0,sizeof(a)),全部初始化为0;
memset(a,-1,sizeof(a)),全部初始化为-1;
memset(a,128,sizeof(a)),全部初始化为一个很小的数,比int最小值略大,为-2139062144。
如果是double数组:
double类似范围为:-1.7e+308~1.7e+308
memset(a,127,sizeof(a)),全部初始化为一个很大的数1.38e+306;
memset(a,0,sizeof(a)),全部初始化为清0;
memset(a,128,sizeof(a)),全部初始化为一个很小的数-2.93e+306。
以上都是常用的最大值,最小值赋值,其他赋值请不要轻易使用,为了验证是否初始化正确,可以初始化后输出其中的一个数进行查看。
邻接表
文章图片
我们建立邻接表当下比较流行且常用的方法是链式前向星
文章图片
代码:
#include
using namespace std;
const int M = 1e6 + 10;
const int N = 1e6 + 10;
struct e {
int to, w, next;
}E[M];
//E数组存储边的信息,下标为边的编号 int tot;
//tot记录边的总数,也是当前边的编号
int head[N];
//head[i]表示顶点i出发的第一条边的编号,例如head[i] = a,表示顶点i出发的第一条边的编号是a
int n, m;
void addEdge(int u, int v, int w) {
//完善边的信息
E[tot].to = v;
E[tot].w = w;
//头插
E[tot].next = head[u];
head[u] = tot;
tot++;
}void output() {
for (int i = 1;
i <= n;
i++) {
for (int j = head[i];
j != -1;
j = E[j].next) {
printf("%d -> %d,边权为 %d\n",i, E[j].to, E[j].w);
}
}
} int main()
{
//n代表点数,m代表边数
cin >> n >> m;
//初始化head表
memset(head, -1, sizeof(head));
//将边逐条地加入到head表上
for (int i = 1;
i <= m;
i++) {
int u, v, w;
//起点,终点,边权
cin >> u >> v >> w;
addEdge(u, v, w);
}
//输出
output();
return 0;
}
图的遍历 深度优先遍历
文章图片
文章图片
广度优先遍历 【麦克算法|第12节课 图】
文章图片
推荐阅读
- acm算法学习|4/5 逆元+深搜+bfs
- 寒假刷题特辑|【第五章】 C语言之牛客网刷题笔记 【点进来保证让知识充实你一整天】
- linux|ubuntu20.04安装微信和QQ,腾讯会议,以及一些其他实用软件
- java|教你代码实现抢红包功能
- 面经|任拓数据科技 软件开发工程师 一面 万兴科技 前端开发工程师 一二面hr面
- 高性能|高性能软件系统设计中应该考虑的问题
- #|Spark优化总结(二)——代码编写
- 学习|使用IOS快捷指令打开任意支付宝小程序
- 笔记|单调栈详解-基于LeetCode的题目