第12节课 图

文章目录

• 图的定义和基本术语
• 图的存储
• • 邻接矩阵
  • 邻接表
• 图的遍历
• • 深度优先遍历
  • 广度优先遍历

图的定义和基本术语

图的存储 邻接矩阵

图论中的建表小技巧：最大值为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;
}

图的遍历 深度优先遍历

广度优先遍历