当前课程知识点：数据结构（Data Structures） > 6. Graph > 6.3 Adjacency Matrix > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
接下来这节课中
我们将重点学习图的邻接矩阵的实现
我们前面已经学习过了
邻接矩阵的核心它是一个二维数组
数组中的元素记录了顶点之间连边的权重
对于有V个顶点的图来说
这个数组它是一个V×V的二维数组
下面我们来看一下邻接矩阵的实现类
Graphm
这个类继承了抽象类Graph
并且实现了图中的操作
首先我们这里定义一个动态二维数组
Matrix
数组中存储的数据元素是整数类型
用来表示连边的权重信息
另外 在前面我们定义的ADT中
我们定义了关于图上的顶点的标记操作
所以在这里面
我们定义一个一维动态数组 mark
用来去记录每个顶点的标记
此外为了记录图中顶点的数目
以及连边的数目
我们定义了两个整数变量
一个是numVertex
用来去记录顶点的数目
numEdge用来记录连边的数目
这样一个基本的邻接矩阵的存储结构
也就完成了
下面我们来看一下
在图上的一些基本操作的实现
首先我们来看一下邻接矩阵的初始化操作
这个是Graphm类的构造函数
在这里完成图的初始化
构造参数numVert
记录了图中的顶点的数目
初始化的时候
我们首先初始化顶点的数目 numVertex
然后将连边的数目设置为0
接着我们需要给前面
所定义的一些动态数组来分配空间
首先 我们给标记数组分配空间
数组的长度等于顶点的数目
然后我们对标记数组的值进行初始化
我们采用两种状态的标记
用来表示0点的访问状态
当取值为1的时候
表示这个顶点已经被访问过了
取值为0的时候表示没有访问过
这里我们将所有的标记
都初始化为未访问过的状态
最后是对邻接矩阵中的二维数组
matrix的初始化
首先我们需要对这个
动态的二维数组分配空间
这个数组的两个维度的长度
都是等于numVertex
然后我们要对数组中
所有的元素都要进行初始化
把它们设置为0
对应的是图上没有连边的情况
接下来
我们来看一组在图上的邻居关系的操作
首先是first函数
给定一个顶点 v
返回这个顶点的第一个邻居顶点
那么哪个顶点
我们称为叫第一个邻居顶点呢
我们这里把每一个顶点的邻居顶点
按照序号来进行从小到大的排序
序号最小的顶点我们称为第一个邻居顶点
在邻接矩阵中
如果我们要获得顶点为v的邻居顶点
我们只需要去查找第v行的数据元素
在这一行元素中
我们要去查找第一个非零元素
它所对应的列号
那么就是我们v的第一个邻居
所以我们可以看到在这里
我们会使用一个for循环
遍历邻接矩阵中的第v行元素
找到第一个非零元素
我们就可以返回对应的元素的列号
这个列号所对应的
就是第一个邻居顶点的序号
如果在第v行找不到非零元素
那么也就意味着
顶点v它是没有邻居顶点的
所以我们在这里返回-1
以表示它没有邻居
接下来是一个经常和first函数
搭配使用的next函数
这个函数获取下一个邻居结点
其中第一个参数v1是当前顶点的编号
v2是v1的某个邻居顶点的编号
next函数它会返回编号比v2大的
v1的下一个邻居的编号
例如在上面的例子中
0的第一个邻居它是1号顶点
而0的下一个邻居也就是next(0,1)
编号比1大的下一个邻居顶点
它是4号顶点
而因为没有编号比4更大的邻居顶点
所以我们可以让next(0,4)返回-1
我们来看一下next函数的代码的实现
要查找编号为v1的顶点的邻居
我们同样
也是要在邻接矩阵中的第v行
去查找不为零的顶点
不过因为要查找编号比v2大的邻居
所以这里的for循环中
迭代变量i
它是从v2+1来开始进行查找的
然后直到找到第一个非0元素
它所对应的列号
就是我们要找的邻居的编号
如果在后面我们找不到非0元素
我们就返回-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
