当前课程知识点:Data Structures and Algorithm Design Part I >  06.Graph >  B1.Adjacency_Matrix >  06B1-6

返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表

06B1-6 在线视频

下一节:06B1-7

返回《Data Structures and Algorithm Design Part I》慕课在线视频列表

06B1-6 课程教案、知识点、字幕

按照这种实现方式

我们可以简明实现顶点操作中的

大部分基本操作

比如直接返回顶点所对应的信息

以及它的入度和出度

它的状态 它的时间标签

在遍历树中的父节点

以及在遍历过程中

动态维护的优先级树等等

当然 并非所有的顶点操作

都能如此直截了当地

一蹴而就地实现

比如在图的遍历过程中

需要反复地使用这样一个接口

也就是说 站在当前

顶点 i 的位置

我们需要逐一地罗列

也就是枚举出

与之邻接的所有顶点

我们称这些顶点为

当前顶点的邻居 neighbor

为此我们首先需要实现一个

名为nextNbr的接口

它的功能语义是

如果我们现在已经枚举到

顶点 i 的编号为 j 的这个邻居

那么它将返回

接下来的下一个邻居

我们知道 与顶点 i 潜在的

可以相邻的点

无非就是它在邻接矩阵中

所对应的那一行

这个行向量中的元素

取值或0或1

而所有那些数值为1的单元

才各自己对应于

与i邻接的一个顶点

那么如果我们现在已经枚举到

编号为j的这个邻居

我们如何找到下一个有效的邻居

因此我们不难理解

这个算法为什么要从j开始

不断地通过减减

逆向地向前进行搜索

每抵达下一个潜在的邻居

都要通过exists接口

判断对应的这条边是否存在

只要不存在

我们就继续通过 j 减减

指向下一个潜在的邻居

直到最终发现一个有效的邻居

至此我们只需将

新发现的这个邻居返回即可

而接下来 如果我们再次调用

nextNbr这个接口

自然也就返回下一个邻居

以及再下一个有效邻居

以及再下一个

和再下一个

请注意 最终的特殊情况

也就是当我们试图

越过这个向量的左边界0

也就是试图抵达-1的时候

我们将终止这样一个搜索的过程

这也就是为什么

在这个短路求值的逻辑表达式中

首先需要检查j是否已经越界

那么第一个有效的邻居

又该如何确定呢?

为此我们需要准备另一个例程

我们可以看到

其实这个firstNbr

也是调用了nextNbr而已

不同的在于 它将顶点n

作为上一个有效的邻居

没错 n 你并没有听错

尽管编号为n的顶点压根就不存在

依然不妨将它视作是一个假想的哨兵

而且等效地认为

它会和包括 i 在内的

任何顶点都相邻

从而简明而有效地

启动整个搜索和枚举的过程

那么整个这样

从第一个有效的邻居

一直枚举到

最终的一个的过程

累计需要花费多少时间呢?

我们可以看到

尽管各自nextNbr所对应

while循环的长度不尽相同

但是累计而言

其总数不过是整个行向量的长度

我们讲过 这个长度恰好就是n

因此整个算法所需要的运行时间

累计不过是线性

当然如果你对这个效率

还不甚满意

可以借助我们稍后介绍的

邻接表结构进行改进

你将会看到 在如此改进之后

整个过程累计所需要的时间

将线性正比于

当前顶点的出度

Data Structures and Algorithm Design Part I课程列表:

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--(a)计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-(xd):LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

06B1-6 笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。