麦克算法|第12节课 图


文章目录

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

图的定义和基本术语 麦克算法|第12节课 图
文章图片

图的存储 邻接矩阵 麦克算法|第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。
以上都是常用的最大值,最小值赋值,其他赋值请不要轻易使用,为了验证是否初始化正确,可以初始化后输出其中的一个数进行查看。
邻接表 麦克算法|第12节课 图
文章图片
我们建立邻接表当下比较流行且常用的方法是链式前向星
麦克算法|第12节课 图
文章图片
代码:
#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节课 图
文章图片
麦克算法|第12节课 图
文章图片

广度优先遍历 【麦克算法|第12节课 图】麦克算法|第12节课 图
文章图片

    推荐阅读