-
Notifications
You must be signed in to change notification settings - Fork 16
Expand file tree
/
Copy path图的遍历 从某个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且只访问一次。.html
More file actions
20 lines (19 loc) · 2.94 KB
/
图的遍历 从某个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且只访问一次。.html
File metadata and controls
20 lines (19 loc) · 2.94 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<html>
<head>
<title>图的遍历: 从某个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且只访问一次。</title>
<basefont face="微软雅黑" size="2" />
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="exporter-version" content="Evernote Windows/307425 (zh-CN, DDL); Windows/10.0.0 (Win64);"/>
<style>
body, td {
font-family: 微软雅黑;
font-size: 10pt;
}
</style>
</head>
<body>
<a name="464"/>
<h1>图的遍历: 从某个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且只访问一次。</h1>
<div>
<span><div>图的遍历: 从<span style="color: rgb(255, 0, 0);">某个顶点</span>出发，沿着某条搜索路径对图中的所有<span style="color: rgb(255, 0, 0);">顶点进行访问且只访问一次</span>。</div><div>深度优先搜索: 类似于树的先跟遍历，</div><div>广度搜索：引入<font style="color: rgb(255, 0, 0);">队列来保存</font>已访问过的顶点序列。</div><div><br/></div><div><br/></div><div>最小生成树</div><div><br/></div><div> 普利姆算法: 时间复杂度 n平方 与图中的边数无关。适合求边的稠密网</div><div> 克鲁斯卡尔：时间复杂度 e loge 与图中顶点无关 适合求边的稀疏的网</div><div><br/></div><div><br/></div><div><span style="box-sizing: border-box; outline: 0px; font-size: 16px; color: rgb(78, 161, 219); line-height: 26px; word-break: break-all; font-family: "PingFang SC", "Microsoft YaHei", SimHei, Arial, SimSun; font-variant-ligatures: normal; font-variant-caps: normal; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); font-weight: bold; cursor: pointer;">优先队列是一种常用的数据结构，通常用堆实现。</span></div><div><span style="box-sizing: border-box; outline: 0px; font-size: 16px; color: rgb(78, 161, 219); line-height: 26px; word-break: break-all; font-family: "PingFang SC", "Microsoft YaHei", SimHei, Arial, SimSun; font-variant-ligatures: normal; font-variant-caps: normal; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; cursor: pointer;">对应于大顶堆和小顶堆，存在最大优先队列和最小优先队列。以最大优先队列为例，优先队列除了具有堆上的一些操作， 如调整堆、构建堆之外，还有获得优先队列的最大元素，抽取出优先队列的最大元素， 向优先队列插入一个元素和增大优先队列中某个元素的值。其中除了获得优先队列的最大元素的时间复杂度为(Θ1)之外，其他几个操作的时间复杂度均为二叉树的高度，即Θ(lgn)。</span></div></span>
</div></body></html>