当前位置:网站首页>树与图的深度优先遍历模版原理
树与图的深度优先遍历模版原理
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);
}
边栏推荐
- Win11 control panel shortcut key win11 multiple methods to open the control panel
- Different meat customers joined hands with Dexter to launch different hamburgers in some stores across the country
- 这项15年前的「超前」技术设计,让CPU在AI推理中大放光彩
- How to open win11 remote desktop connection? Five methods of win11 Remote Desktop Connection
- Golang compresses and decompresses zip files
- What is CGI, IIS, and VPS "suggested collection"
- 图灵诞辰110周年,智能机器预言成真了吗?
- sscanf,sscanf_s及其相关使用方法「建议收藏」
- Kotlin compose text supports two colors
- Golang calculates constellations and signs based on birthdays
猜你喜欢
测试/开发程序员怎么升职?从无到有,从薄变厚.......
Win11远程桌面连接怎么打开?Win11远程桌面连接的五种方法
[written to the person who first published the paper] common problems in writing comprehensive scientific and Technological Papers
Ssm+jsp realizes enterprise management system (OA management system source code + database + document +ppt)
【线段树实战】最近的请求次数 + 区域和检索 - 数组可修改+我的日程安排表Ⅰ/Ⅲ
SSM+jsp实现仓库管理系统,界面那叫一个优雅
Practice Guide for interface automation testing (middle): what are the interface testing scenarios
科兴与香港大学临床试验中心研究团队和香港港怡医院合作,在中国香港启动奥密克戎特异性灭活疫苗加强剂临床试验
NFT meta universe chain diversified ecosystem development case
Deeply cultivate the developer ecosystem, accelerate the innovation and development of AI industry, and Intel brings many partners together
随机推荐
Intel and Xinbu technology jointly build a machine vision development kit to jointly promote the transformation of industrial intelligence
高薪程序员&面试题精讲系列120之Redis集群原理你熟悉吗?如何保证Redis的高可用(上)?
SSM+JSP实现企业管理系统(OA管理系统源码+数据库+文档+PPT)
[team learning] [34 sessions] Alibaba cloud Tianchi online programming training camp
Gpt-3 is a peer review online when it has been submitted for its own research
ACL2022 | 分解的元学习小样本命名实体识别
jvm是什么?jvm调优有哪些目的?
超越Postman,新一代国产调试工具Apifox,用起来够优雅
GPT-3当一作自己研究自己,已投稿,在线蹲一个同行评议
Data security -- 12 -- Analysis of privacy protection
Food Chem | in depth learning accurately predicts food categories and nutritional components based on ingredient statements
未婚夫捐5亿美元给女PI,让她不用申请项目,招150位科学家,安心做科研!
2022 electrician cup question B analysis of emergency materials distribution under 5g network environment
各路行业大佬称赞的跨架构开发“神器”,你get同款了吗?
The most complete security certification of mongodb in history
[ArcGIS tutorial] thematic map production - population density distribution map - population density analysis
[written to the person who first published the paper] common problems in writing comprehensive scientific and Technological Papers
食堂用户菜品关系系统(C语言课设)
Formation continue en robotique (automatisation) - 2022 -
What if win11 pictures cannot be opened? Repair method of win11 unable to open pictures