当前课程知识点:Data Structures and Algorithm Design Part I > 06.Graph > B1.Adjacency_Matrix > 06B1-6
返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表
返回《Data Structures and Algorithm Design Part I》慕课在线视频列表
按照这种实现方式
我们可以简明实现顶点操作中的
大部分基本操作
比如直接返回顶点所对应的信息
以及它的入度和出度
它的状态 它的时间标签
在遍历树中的父节点
以及在遍历过程中
动态维护的优先级树等等
当然 并非所有的顶点操作
都能如此直截了当地
一蹴而就地实现
比如在图的遍历过程中
需要反复地使用这样一个接口
也就是说 站在当前
顶点 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
因此整个算法所需要的运行时间
累计不过是线性
当然如果你对这个效率
还不甚满意
可以借助我们稍后介绍的
邻接表结构进行改进
你将会看到 在如此改进之后
整个过程累计所需要的时间
将线性正比于
当前顶点的出度
-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
-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
-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
-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
-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
-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
-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
-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