00:00
同学们,我们来继续学习数据结构的下面一种叫图。那首先我们还是老规矩,我们对图这个数据结构呢,做一个基本的介绍。那为什么要有图呢?对不对?先把这个问题给大家做一个解答,前面我们学习了线性表和数,是不是?大家大家都知道,线性表呢,它局限局限于有一个直接前驱和一个直接后继。就是我们所说的单链表,是不是它有一个全区最多呢,也只能有一个后G。节点,那么树呢?大家知道,数。它也只能有一个直接前驱,也就是一个负节点。他当然可以有多个,你比如说一个二叉树,它可以有。多个,呃,可以有两个子节点,但是对于一个节点而言呢,它的前驱节点其实也只有一个,是这样子的吧,那有时候呢,我们需要处理多对多的关系,这个时候我们发现呢。
01:02
诶,前面两种数据结构就不好使了,这时我们就会用到图,图就是这样子的,换言之就是当我们需要处理多对多的关系时呢,我们就可以用到图。那么我们来看一下图的举例说明,同学们看那么图它首先要确定它是一种数据结构。其中节点可以具有零个或者多个相邻的元素,两个节点之间连接,我们称之为边,你比如说这个,大家看,这就是一个图,这个图有ABCDE5个节点。那么我们所说的边就是这个,也就是说他们的连接我们就称之为边,那么在现实生活中,我们这个图其实挺多,你比如说地图,像我们这种。这个叫做。这个叫做这个城市交通的一个地铁,地铁的一个分布图,地铁站的一个分布图,它就是一个图,看到没有那一个节,一个站就一个,一个地铁站它可以连接多个。
02:04
它可以连接多个其他的地铁站,那么这就是一个图的一个实际,那下面这边呢,同学们看到的这个呢,就是在我们编程里面的一种图,你看abcde就是五个五个节点,五个节点呢我们也叫顶点,它的相邻连接我们就称之为边。好,这就是图的一个概念,大家先有一个基本的认识,那下面呢,我们既然要学图,我们就要看这个图有哪些常用的概念需要同学们了解的。第一个概念我们需要了解,顶点叫vertex。那么顶点其实就是节点,就是同学们看到在刚才看到的这个图结构里面呢,Abcde都是节点,同时呢,我们也可以称之为顶点,这是第一个概念,边H哪个是边呢?这个就是边,明白了吧,路径是什么呢?看这边路径,呃,路径这个地方呢,跟跟这个跟它是有像图还是无像图相关的,什么是无像图,什么是有相图,待会我们再讲。
03:08
先先这样子,先看一下啊,先看一下路径,你比如说D。到C的路径有哪个,我们我们从这面看,目前我们看到的这个图其实是一个无像图。那为什么是一个无相图呢?大家看顶点之间连接没有方向。我们把这种图就称之为无像图,你比如说A和B之间,你看AA和BA可以到BB,也可以到A,也就是说A到BB到A都可以,这个就称之为无像路,它没有。没有方向。没有说谁到谁的问题,没有方向,所以说这就是五象图。那么路径在在这个无像图的情况下呢,比如说我们说D到C,它的路径就有几条呢?它就有两条,你比如说同学们看这里。同学们看这里,我们D到C可以这样走。
04:03
是不是可以这样走啊,就是DBC,我们也可以这样走。是不是也可以到C啊,那就是DAC,就是我这写的DAABC,这个呢,也是一条路径,这就是路径的概念,那接接紧接着呢,我们再来看一看下面的概念,什么叫做有相图,有相图听听其名而知其意,就是说它这个图两个顶点之间呢,诶,它是有方向的。你打个比方,像大家看到的这张图。这张图你比如说顶点之间,它是有方向的,比如说我们A和B之间的关系就只能是A到B,不能是B到A了,因为它的方向是这样指向的,明白,那顶点和边的概念仍然是没有变化,我们再来看有一个概念叫做带全图,带全图看这边。看这边所谓带全图,就是它的这个边呢,它是有全职的,打个比方我们说这有。
05:03
这么四个城市,北京到上海。北京到台北,台北京到香港,他们之间也有关系,那么大家看到北京到上海他们的连接线呢,有一个数叫1463,这个可能是表示他们的距离,比如说我们要表示北京和上海的距离是是1463公里,这里呢就可以用一个值来表示。同样其他也是一样的道理,我就不一个个的讲了,那也就是说,当我们这个图的边,它带有全值呢,我们就叫做带全图,同时呢,也叫王。这是也就叫网了,网的概念也就出来了,好,那这是我们图的常用概念,接着我们再来看图的表示方式有几种。那么在我们这个数据结构里面呢,表示图主要有两种方式,第一种呢,我们叫做临接矩阵。大家只要听到矩阵,一般来讲呢,是用二维数组来表示的,也就是说如果我们要用临接矩阵来表示,那就需要二维数组,还有一种表示方法呢,叫做临接表。
06:08
那临接表呢,我们一般是用链表来表示,当然一般也也有可能是数组加列表,呃,这样是数组加列表的形式来表示临接表好。好,那么我们先来看一个具体的具体的案例,什么叫临界矩阵呢?所以临界矩阵是表示图中顶点之间相邻关系的矩阵,如果对于N个景点而言呢,矩阵就应该是有绕有行有列,它一共有N个点,那比如说我们就看一个案例,比如说这大家看这是个什么图。这个图它是一个无像图,因为他们没有只没有方向,就是连接是没有方向的,这就是一个无像图,那针对这个无像图,如果我们用这个临界矩阵来表示的话呢,这个就是它的临界矩阵。大家能看懂吗?你看这个地方它是这样表示的,零和零之间用零表示。啊,就代表这两个之间呢,我们认为是不连的,因为自己跟自己连嘛,这也没有什么意义,他就用零表示,有些地方呢,用拉姆达用这个无穷大来表示啊。
07:10
无穷大表示这个,反正就是表示这么一个意思,表示这么一个意思,零就代表不连通,那么大家看零和一之间。零和一之间它用一表示,诶这个就表示零和一,它是可以连通的。那么我们再看零和二之间呢,也用一表示,表示零和二也是可以连通的,看到没有。好,我们再看零和三,零和三之间呢,也是可以连通的,看到没有,好,我们再看零和这个点,零和四一也是可以连通的,的确也可以连通,那么零和五呢,诶你看零和五就是一个零,就代表不可以连通,因为零和五呢,它不能直接连,看到没有,它这里所所谓的连通指的是不能直接连啊,并不是说哦,我通过一个节,一个顶点再过来,不是那样子的,它表示是否直接。
08:01
所以说如果零和五这标了一个零,就代表零和五并没有直连的一个关系,明白这意思吧,但是它并不是说哦,你这零我就不能到达你,因为如果有个路径的话,还是可以过来的,这表示值是否能够直连,其他的含义一样的,我就不一个讲了,你你你再看一和零。一和零是不是也是一样?对一和二,你看大家看这里一。这个点和这个顶点和这个顶点一号二支烟是不是零了,一号二支烟是不是不通啊,你看这这这没有连线,好,那其他我就不一个讲了,同学们好吧,我们再来看第二种表示方式,叫临界表,那么相对刚才我们讲的临界矩阵而言呢,大家有没有发现临界矩阵呃,它的特点是这样子的,它需要每为每个顶点都分配N个边的空间,是这样子吧。其实有很多边,它是不存在的。它是不存在的,也就是说他们根本就没有关系,但是实际上呢,你也要把这个边表示出来,你用零表示的吗。
09:02
这样子吧,那么这样就会造成空间的一定损失。也就是说你实际上可能用不了这么多点,但是呢,你你把这个不存在的这个边也表示出来了,所以说它这边就会造成空间的损失,那么临界表就不一样了,如果用临接表表示呢,它只关心存在的边,不关心不存在的边,也就说如果不存在的边,它就不表示了。因此呢,它就没有空间浪费,那临接表呢,大家看它是由数组加链表构成的。比如说我们要表示多个点。一个点当然用一一条链表,那多个点呢,就要用多条链表,然后再用数组把它管理起来,你比如说同学们看。我们还是以刚才这个无像图来表示,同学们看这里这个零,注意听啊,这个零代表标号为零的这个节点。这个一代表标号为一的这个节点看清楚了啊,那么我们看一个大家就看懂了。
10:00
那大家怎么来看这个临界表呢?非常的简单,同学看。这条线。这一条线就代表。标号为零的这个节点顶点或者叫节点都可以标号为零的这个顶点,它跟一、二、三、四这四个顶点是相连的。你看零是不是跟这四个零关联,0102030405没有。但是大家不要不要这样认为啊,说诶是不是一到二,二到三,三到四不是这样子的,那它这个并这个并不表示一个一个顺序,它只是表示零,这个顶点可以跟1234相连,只是它它写的时候呢,是按这个顺序从小到大写的,仅此而已。好吧,那么同样下面这个是不是大家也看懂了,这个就代表。标号为一的这个顶点,它跟D标号为零的节点和标号为四的这个顶点是连通的,你看是这样子,一它只跟零是连通的,跟是是连通的,跟其他点都没有连通,所以这只表示了这两个点,明白吧,下面以此类推。
11:18
你看我这也做了注释,标号为零的,比如说这个这个标号为零的节点的相邻的关,相关联的节点是1234,好吧,就是这样子,按照从小到大它辩论号写出来的。那下面也是一样的道理,呃,你再看一个五也可以看出来,五这个标号为五的这个顶点,它跟234是相关联的,你看市面上的我。五跟几啊,五跟二连,五跟三连,五跟四连,那跟零和一是没有直连的关系的好,那么这就是我们所说的临界表,大家大体应该明白了吧。好,同学们。那关于。这个图的最基本的这么一个呃概念,我们就先跟大家聊到这里,那现在我们把讲的内容呢,做一个简单的板书来看一看。
12:09
好,那刚才我们讲的东西呢,比较简单,就是图,对不对,先把这个图的概念给各位朋友抛出来了,那么我们捋一捋刚才讲的思路,首先呢,我先讲了图的基本介绍。我先给同学们说一下图的基本介绍。那图的基本介绍呢?我分成了两个部分,先给同学们说一下为什么要图。既然我们学了。既然我们已经学了线性表和数,为什么还要学学这个图呢?其根本原因就是你这个线性表和数在某些情况下是不能够满足我们实际需求的,你比如说当我们要表示多对多的关系的时候呢?诶,这个时候我们就可能用到这个图,明白这意思吧,诶,用到这个图了,把它标出来。就要用到这个土。
13:00
这是为什么要有图?那么有了这个图的基本介绍过,呃,这个为什么有的话呢,我们就举了一个实际的例子来来说这个图长什么样子。好,这是图的一个举例。对吧,首先大家要明白,图呢,它是一种数据结构,它不是就说如果单纯的说图它不是算法,它就是数据结构,跟我们前面讲的排序不一样,排序就真的是算法了,而图它其实是一种数据结构,OK,它是一个数据结构,它长的是什么样子的呢?好,我给同学们画了。两我给大家提供了两个图,一个这个图是我们在后边编程的时候要实现的这种图,这个图是我们现实生活中遇到的这种地铁图,明白好,这是。一个图的举例。好,当我们把这个说完了以后呢,我们紧接着给同学们说一下图的一些常用的概念,那么这时呢,我们就直接用一个图来描述的,首先说了什么叫顶点vertex edge路径无像图,好,我把这个给大家拿过来,好吧,比较简单嘛,概念的东西呢,还是比较简单的,后面呢,我们举例的时候还要再说,好吧,顶点无像图,那我把这个这个图给他拿过来,大家放,这就比较形象的知道是什么概念了。
14:24
好,我把这一部分先给大家放这对不对,这就是一个五项图,好,紧接着我们看第五点。第五点。好,第五点我们又给同学们说了什么呢?我给大家说了这个有向图和带全图的概念,对不对?那什么是有向图,什么是带权图,我们说一下。有向图和带全图呢,我直接就给大家画,直接让让大家看了两个,大家看这里,这个就是一个有向图。为什么它是有向呢?因为它的顶点之间是有一个方向的,你比如说A到B,那反过来B到A呢就不可以,什么叫做带全图呢?带全图就是它的边呢,已经有直了,有全职。
15:09
啊,有全职这样的一个概念,这就是我们这个有相图和这个带权图的一个概念,带权图呢,我们也把它称之为王。接着我们继续往下看,那下面事说完了过后,我们就给大家说一下,既然你图是一种数据结构对吧,那图是用数据结构,它具体用什么来表示呢?来表示这个图呢?那有两种方式,就好比我们前面学这个队列是吧?队列它是怎么实现的呀?它是用数组,也可以用链表实现,那么我们这个图呢,它是怎么实现的呢?诶,它是二维数组。或者是链表,当然一般的是数组加链表,对不对,我们主要用呃,主要这个矩阵或者是临界表来表示,那这样子呢,我先给同学们直接就说了一个案例,好把这个选图的表示方式。
16:03
好,图的表示方式呢,我们说先。可以是临界表,把这个放到这临界表,那临界表它怎么去表示一个图呢?好,我这里就直接给同学们画了一个图,大家一看就明白了,你看这,这是有五个顶点的图,那么如果我们用这个二维数组来表示,它就长这个样子,一表示它们是可以直连的,连通的,零表示它们不连通,OK,这是这么一个意思。好了,这就是它的一个临接矩阵的描述,那紧接着呢,我们又给同学们讲了一下临接表,那临界表呢,我们先让先讲临界表的时候,我们让它跟临界矩阵做了一个比对,临界矩阵呢,它因为它这个不这个不存在的边,它也描述出来了,所以说呢,它会有空间的一定损失,临界表呢,它不关心。
17:04
不存在,这边硬是没有空间浪费,比如说下面这个案例就能说说明这个问题,好,这里举例说明。举例说明,具体来说就只要看上这张图就可以了,好吧,就是这么一张图。好,我把这个图呢给各位朋友板书到笔记中,好,同学们,那关于图的基本介绍我们就先聊到这里,下面呢,我们准备用代码来一个快速入门。
我来说两句