当前位置:网站首页>树与图的深度优先遍历模版原理

树与图的深度优先遍历模版原理

2022-07-06 22:04:00 _刘小雨

树是一个特殊的图 (无环连通)

所以只用知道图就行了

图 : 又分为 有向图 和 无向图

图的存储
有向图:(a–>b)

  • 邻接矩阵 g[][], 无权重直接等于bool, 有权重直接将权重赋值给它
  • 邻接表 (用链表存储)(也可以用vector存,只是效率差一点)

邻接表的存储代码实现:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 2;

int n,m;
// h 表示n 个单链表
int h[N], e[M], ne[M], idx;

void add(int a, int b)
{
    
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int main()
{
    
    meset(h, -1, sizeof h);
}

图的遍历
深度优先遍历: 一条路走到结束, 然后在回溯看有没有其他节点没有遍历

在这里插入图片描述
深度优先遍历代码实现:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 2;

int n,m;
int h[N], e[M], ne[M], idx;
bool st[N];

void add(int a, int b)
{
    
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    
    st[u] = true;
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
    
        int j = e[i];
        if(!st[j]) dfs(j);
    }
}

int main()
{
    
    memset(h, -1, sizeof h);
}
原网站

版权声明
本文为[_刘小雨]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_39486027/article/details/125642937

随机推荐