当前课程知识点：数据结构（Data Structures） > 6. Graph > 6.4 Adjacency List > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
接下来这节课我们将重点学习
图的另外一种实现方式 邻接表
前面我们已经学习过
邻接表的基本结构它是一个链表的集合
每一个顶点它所相关联的连边
我们采用一条链表来进行表示
并且我们采用一个指针去指向这个链表
在图中我们有多少个顶点
那么这个数组
里面就会保存多少个链表指针
下面我们来仔细分析一下链表的结构
链表中每个结点对应的是一条连边的信息
其中包含连边的顶点的编号
以及连边的权重
因此我们可以为这个结构定义一个类 Edge
类中包含有顶点的编号 vertex
以及权重 weight
基于这个结点的类型我们可以采用
之前我们所定义的链表类LList
来去实现这个链表
其中链表中的数据元素的类型
就是这里所定义的Edge类型
所以我们采用Edge作为模板参数
另外为了方便访问
我们还可以让链表中的结点
按照顶点的编号进行从小到大的排序
编号较小的排在链表的前面
比较大的排在后面
基于链表结构的定义
下面我们来定义邻接表类 Graphl
因为每个链表的类型是LList类型
所以链表的指针也就是LList指针类型
而我们这里面
应该要有一个链表指针的数组
来去存放这些指针
所以在Graphl类里面
我们定义了一个
LList指针类型的动态数组 graph
在后面的构造函数中
我们将会对这个数组来分配空间
此外类似于邻接矩阵中的定义
我们还定义了一个标记数组 mark
以及顶点的个数 numVertex
和连边的个数 numEdge
下面我们来看一下邻接表的构造函数
构造参数numVert记录的是顶点的个数
我们根据这个顶点的数目
来去初始化邻接表的成员属性
首先 我们会将顶点数目numVertex
初始化为numVert
将连边数目numEdge初始化为0
因为初始化的时候图中是没有连边的
然后我们将初始化标记数组
将数组中每个顶点的状态
都设置为UNVISITED
也就是零的状态 来表示没有访问过
最后我们将为指针数组graph分配空间
这个数组的大小等于顶点的数目 numVertex
同时我们要给指针数组的
每一个指针进行初始化
让它指向一个新创建的LList链表
接下来我们来看一下邻居关系的操作
首先我们学习一下first函数的实现
这个函数输入一个顶点的编号v
返回它的第一个邻居顶点
例如在这个例子中
0号顶点
它的第一个邻居的编号是1号顶点
所以first(0) = 1
由于所有的邻居
我们都记录在对应的链表中
所以我们只需要找到
链表中的第一个结点就可以了
这些我们可以通过链表的操作来进行实现
因为我们要访问的是
编号为v的顶点的邻居
所以我们首先要找到
第v个顶点它的邻居链表的指针 graph[v]
然后去调用它的setStart函数
通过这个调用
我们将把栅栏移动到链表的开始的位置
然后我们再通过getValue函数
就可以获取第一个结点的值
并且记录在参数it中
如果这个结点它是存在的
那么getValue函数将会返回true
我们可以通过读取it的vertex属性
来获得对应的邻居顶点的编号
如果链表是空的
那么getValue它会返回false
这个时候我们应当返回-1
来表示邻居顶点是不存在的
接下来我们来看一下Next函数的实现
这个函数的输入参数是两个顶点的编号
函数返回的是
v1顶点的下一个邻居的编号
而且这个邻居的编号要比v2大
我们知道v1顶点的邻居链表指针
它是在Graph v1这个地方
我们将通过调用这个链表的操作
来去获得v1的邻居的信息
我们首先通过getValue函数的操作
来去获取链表当前位置的结点的值
并且把它记录在it中
如果当前位置的结点
它所对应的顶点编号是v2
那也就说明编号比v2大的这个邻居
它应该记录在链表的下一个结点中
比如在这个例子中栅栏处在于这个位置
当前位置的邻居顶点编号它是1
如果我们这个时候调用的是next(0,1)
获取编号比1大的顶点编号
我们就只需要简单地去访问
链表的下一个结点就可以获得了
所以我们这里
可以通过调用链表的next操作
将栅栏移动到下一个位置
然后去调用getValue获得这个结点的值
并且读取其中记录的顶点编号 vertex
那么如果当前位置的顶点它不是v2
怎么办呢
因为我们要找的是
编号比v2大的邻居顶点
所以我们只能从头开始
在链表中进行逐个逐个地去检查
每个邻居顶点
所以在这里面
我们首先通过调用setStart函数
将栅栏调整到链表的最开始的位置
然后通过一个循环语句
不断地去读取当前位置的值
并且判断当前的顶点的编号是否大于v2
如果小于等于v2就要不断地运行
继续通过next操作去移动这个栅栏
比如在这个例子中
我们要获得的是比4大的顶点编号
所以我们从头开始不断地去移动栅栏
寻找比4大的顶点
这个循环的终止有两种情况
一种是在调用getValue的时候返回了false
这就意味着我们找到了链表的末尾
都还没有找到合适的顶点
图中的例子就是这种情况
另外一种就是当前顶点的序号要大于v2
这就说明了
我们成功找到了满足条件的邻居顶点
最后我们通过getValue操作
读取当前顶点的编号
如果getValue失败
说明我们找不到合适的顶点 返回-1
好的 我们这节课就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
