数据结构--图的遍历

时间：2023-07-06 21:22:39浏览次数：45

标签：优先遍历 -- DFS 邻接矩阵邻接深度数据结构

图的遍历

遍历的定义

遍历实质:找每个顶点的邻接点的过程.

图的特点

图可能存在回路所以我们需要设置辅助数组来标记访问过的节点,防止多次访问.

遍历方法

深度优先搜索(DFS)

方法:

深度优先遍历可能有很多种方式

连通图的深度优先遍历类似于树的先根遍历.

邻接矩阵的深度优先遍历

DFS结果

2->1->3->5->4->6

算法实现

邻接表的深度优先搜索

DFS算法效率分析

结论:

稠密图适合在邻接矩阵上进行深度遍历

稀疏图适合在邻接表上进行深度遍历

非连通图的遍历

标签：优先,遍历,--,DFS,邻接矩阵,邻接,深度,数据结构
From： https://www.cnblogs.com/harper886/p/17533378.html

7.6
今天上午呢,有吹哨的七点起床,但是因为我还没有分配班级,而且又没有新生入学,尽管我七点就起床但是压根就没事干,在宿舍就躺了一上午.不得不说啥也不干把钱挣了的感觉就是好.接着就是中午吃饭,还行吧今天的菜是最让我有胃口的,哐哐选了六块饼,来折磨久第一次吃的饱饱的感觉幸福感......
C# 替换字典的键或值
因为ElementAt(index)方法是只读的，不能改动键或值，需要通过ToDictionary方法usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;classMainClass{publicstaticvoidMain(){Dictionary<string,int>testDict=newDictionary<string,......
7.5
循环高级综合练习：回文数的判断：无限循环：for（；；）{ Syetem.out.println()；}while（true）{ System.out.println()；}无限循环后不能接其他代码，循环不停，代码不运行跳转控制语句：在循环的过程中，跳到其他语句上执行......
Vue（十）：监视属性——watch
1.监视属性的基本用法<!DOCTYPEhtml><html><head><metacharset="utf-8"><title>天气案例-监视属性</title><scripttype="text/javascript"src="../js/vue.js"></script>......
魔法值问题
一、什么是魔法值魔法值，也叫做魔法数值、魔法数字，通常是指在代码编写时莫名出现的数字，无法直接判断数值代表的含义，必须通过联系代码上下文分析才可以明白，严重降低了代码的可读性。除数字之外，代码中作为key值的常量字符串也被认为是魔法值，尽管其表示含义比数值较为清晰，但是仍然会......
【WALT】scale_exec_time() 代码详解
@目录【WALT】scale_exec_time()代码详解代码展示代码逻辑：为什么归一化？⑴ 将CPUcycles转换为CPU当前频率⑵ 归一化delta【WALT】scale_exec_time()代码详解代码版本：Linux4.9android-msm-crosshatch-4.9-android12代码展示staticinlineu64scale_exec_time(u64delt......
7月6日
7月6日早上六点半起床，上了个厕所之后就看了看pta上的题，做了几道五分的简单题，这玩意就是白送分，建议多来点。之后，早上还是要看着我弟写作业，写完之后要检查他作业，然后让他改。他写作业我就在旁边玩手机，小时候淋过雨，现在就要给我弟撕伞。中午吃完饭之后打了一会儿游戏，刷到了永劫无间......
盘点那些 FZQOJ 被 ban 掉的功能
原链接在【洛谷博客】。目录前言初\(2023\)届（c2023）1.犇犇（卒于2021/07/27）2.一言（和犇犇同时挂的）3.评论（卒于2021/07/28）初\(2024\)届（c2024）1.Python2.7（卒于2022/03/15）2.难度标签（卒于2022/07/21）3.HTML（卒于2023/01/04）初\(2025\)届（c2025）前言身为FZOIer的我们十分的......
Logistic回归模型，python
代码参考https://blog.csdn.net/DL11007/article/details/129204192?ops_request_misc=&request_id=&biz_id=102&utm_term=logistic%E6%A8%A1%E5%9E%8Bpython&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-129204192.142^v......
230706 // 换根 DP 复习
菌：园什是我笋子元首：我是你打野我：元首耳朵得治G.求树的重心http://222.180.160.110:1024/contest/3744/problem/7我们知道，重心的定义是，将其切除后，每个连通块的大小不超过\(\dfracn2\)。连通块分为其子树和整棵树减去该结点引导的子树，所以我们记录size，在每次搜索结束后......