22.7.24 树和图的深度优先遍历

1、树和图的存储

​ 树是一种特殊的图，无环连通图，所以图和树一样的存储。图有两种，分为有向图和无向图。由于bool (a–> b &&a<-- b == a – b) = 1,所以，无向图就是一种特殊的有向图，即无向图可以存储为a–> b &&a<-- b的有向图。所以只用考虑有向图的处理与存储。
​ 有向图的两种存储方式：

  1. 邻接矩阵

    用一个二维矩阵来存储 g[a][b]表示a --> b的一条路

    无权重为0 or 1的bool值，

    有权重为权值

    用的比较少，浪费空间，空间复杂度O(n^2),适合稠密的图

  2. 邻接表

    每一个节点都是一个单链表，存储这个点可以走到哪一个点

    主要的存储方式

2、树和图的遍历

​ 有深度优先遍历（bfs）和宽度优先遍历（dfs）两种。

邻接表

dfs模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010, M = N*2;
int h[N],e[N],en[N],idx;
//存储
void add(int a,int b)
{
    e[idx] = b;
    en[idx ] =  h[a];
    h[a] = idx++;
}
//搜索
void dfs(int u)
{
    st[u] = true;//标记一下已经走过了
    for(int i = h[u]; i != -1; i = en[i])
    {
        int j = e[i];
        if(!st[j]) dfs(j);
    }
}

//add的解释看图 -- 邻接表 图上

int main()
{
    
    //添加
    memset(h,-1,sizeof h);
    return 0;
}

//通过数组来模拟邻接表

22.7.25 dfs 深度优先搜索算法

1、什么是深搜

2、模板 不像bfs不用队列

1
2
3
4
5
6
7
8
9
10
11
12
int h[N],e[N],en[N],idx; //邻接表队列

void dfs(int u)
{
    st[u] = true;//标记一下已经走过了
    for(int i = h[u]; i != -1; i = en[i])
    {
        int j = e[i];
        if(!st[j]) dfs(j); // 递归往深处走
    }
}

3、要点解释

4、Q&A总结