00:00
同学们,我们对图有了一个基本的认识过后呢,下面我们来一个图的快速入门案例,大家看到这里呢,我们就以前面讲的这个图给大家来创建。刚才我们讲的这个图呢,一共有五个顶点,它对应的这一个矩阵,临界矩阵应该长得是这样子的,OK,大家可以看到我们这写的很清楚,一表示能够直连。那么零表示不能指令,我这里就是自己跟自己呢,我表示我我是用零表示的啊,有些地方,有些这个课程里面呢,呃,他他用一表示也是可以的,这主要是根据程序员的编程思路来决定的,这点大家理解一下。好的,我们来做一个思路分析,那同学们想一想,你要去完成这个图,首先你的存储,你你这些顶点,这个没问题吧,我们这个顶点呢,假如就用字符串表示就可以了,所以说你首先得有得要保存。
01:07
你你是不是首先都要用一种,用一个属性来存储。要存储这些顶点。对不对,顶点呢,现在我们是时钟类型的,比如说abcde呢,我abcde我们就用时针来表示,那这个时候我用一个R注意听,而用一个r list保存就可以了,理解就是说我存储顶点呢,使用是r list这个集合。使用。Or list,那第二个呢,大家有发现我们需要去保存图的。我们要存储这个图,其本质是用的这个矩阵,那矩阵是不是就是一个二维数组,对不对,所以说呢,我要还要保存。保存什么呢?保存这一个矩阵对不对,那矩阵呢,我就用一个二维数组,比如说我用age。
02:05
这个edges是ED edges就是表表示它的一个边,就是临接矩阵,就是用边来表示的,比如说A和A,我们就用零对不对,A和B就用一,它的这个元素用一,所以说用一个临界矩阵来表示边的关系。同时也就是我们这个图的关系,好,那分析完毕了,过后呢,我们就来直接上代码,打开我们的eclipse,在这里我们新建一个包。我们新建一个包,这个包的名字呢,咱们就叫G。OK graph。那这里呢,我们就写一个名字吧,同学们写一个类。这个类呢,我们就叫grara。Graph。OK,先给他一个总方法勾上。那大家想一想,我们刚才已经知道了,作为一个图来讲呢,我们首先要有一个r list,对不对?来存储什么呀,存储我们的顶点,那顶点我们叫ver text。
03:13
Vertex list没问题吧?Ver text list这个我写个注释,就是存储什么呀,存储顶点。存储我们的顶点的顶点。的一个集合。对不对,呃,这是,诶我们到时间要需要引包对不对,取包把包引进去,紧接着我们是不是还有一个矩阵,这个矩阵呢,是一个二维数组,对不对,那就叫EEDES,这个是干什么呢?这个是存储。存储什么呀,存储。存储这个图的对应的对应的连接。临临接矩阵。
04:00
临街矩阵?对不对?临接矩阵A是用这个来表示的,那下一步我们该干什么呢?我们再用一个属性来表示,当前我有多少个多多少多少条边。Number of edges对,这个表示什么呢?表示。表示边的。边的这个个数或者数目。好,这个。属性我们就先定到这儿,那下面呢,我们应该怎么写了呢?首先我们要写一个构造器,是不是先写一个构造器。那构造器要对我们这些属性进行一个初始化的工作,那么现在呢,我们来写一个构造器,构造器的时候你给我传一个什么进来呢?大家想一想。你如果要构建这个图,你首先要告诉我你有多少个顶点,所以说我用一个N来描述,那就有了。当我们有了这个顶点的。
05:04
个数过后呢,我们就可以来创建好,我们来写初始化初始,诶初始化初始化什么呢?初始化我们的矩阵和这一个r list。是不是很简单,那开始写,首先这个矩阵呢,我们刚才已经有一个属性,名叫H等于六,一个int里面是N和N,我们刚才讲过,如果你的顶点有N个,那么它对应的这个矩阵就是N乘以N。那同时我们还得把这个vertex存储我们顶点的这个链表也进行一个初始化,是不是a list?写上去2LIST,那这里面我们放的是时俊就可以了。就搞定,那这个时候我们可以事先就写个N对吧,就代表我们放这么N个数据进去。
06:01
好,紧接着下一步我们该做什么事情了呢?把这个number。Of age给它设置一下,诶对,现在是这样子,因为这个边呢,我们不知道有多少条,所以初始化为为零,其实你不写也是零,对吧,你不写也是零,这个就是写到这也可以,这就是默认为零。那么现在我们紧接着应该写哪些方法呢?同学们想。我们是不是首先要去完成这样几个方法,就是你到时间会来加,就是插入节点。也就是我们所说的顶点,你要超出一个顶点的话呢,我们写个VO什么呀,In shirt ver text。Ver,那你操作这个顶点的时候,其实你给我传的是什么呢?同学们,实际上你传的就是顶点的对应的这个字字符串是不是,所以说我用字符串来接收,我叫ver text。
07:01
好,那我就把它放进去,放到哪里啊,同学们就直接放在我们的这一个list里面就可以了。Ver搞定。对,这是插入这个节点,那还有一个特别重要的,是不是要添加这个边呢。你你超出这个节点,你还要贴着这个边,那想一想我们这个边。怎么表示这个B和C有边呢,是不是通过。这个对应的矩阵。它的这个元素是零还是一来描述的,因此呢,我们实际上要这么去玩,怎么去玩呢?来咱们写一下,就是呃,Public。我就写了啊,Public void insert。EDGE,那你唯一给我。V2给我是不是,然后呢,还要把这个全值给我。
08:04
那么这个什么叫全值呢?全值就是你这个边它对应的,它这个对应的这个值,也就是说要么是一,要么是零。是不是样子的关系就要么是一,要么是零,如果说你不给,那默认当然就是就是零了,好,那这里应该怎么写呢?非常简单非常简单,你看啊,我这样写。Y值,所以说我这样写,大家看能不能理解V1。V等于V。然后呢,反过来把这个关系,因为我们是无相图,所以说你还要反过来呢,也要把它写一遍。好,不着急,我把这个。改一下。Ages。A级,然后这边呢是V2。诶,这边是V2。这边是V1,没有没问题吧,同样把这个位也给他。
09:01
好,当我们明白这个道理过后呢,同学们,我们可以把这个边的数目加加就可以了,我把这做一个简单的注释。那么这个V1表示什么呢?V表示点。点的这个下标。下标就是这个点在哪个地方下标呢?在我们这就是第相当于说说你是第几个,你是第几个顶点及。级是第几个顶点?啊,第一个点,我举个再熟悉的例子,比如说我们现在是按abcd来来看,那么A呢就代表第零个顶点,B就代表第一个顶点,啊第A代表第一个顶点,但是它的下标为零,B代表第二个顶点,但是它的下标为一,就这意思理解吧,那我这举个例子就可以了,比如说你你要给我。描述A和B之间的关系,对,那么这个A,这个A呢?它对应的这个V1,它的对应这个V。
10:07
就是它对应的这个呢,就是零。这个B这个这个顶点,它对应的就是一,就这意思。OK,那也就是说当时你要描描述A和B有关系,应该怎么填呢?你这边写个零,这边写个一,然后这个全值为一就可以了。理解我的意思吧,好,V2是一样的,V2就是第二个顶点的就是D,这个是。因为因为你是传两个顶点嘛,所以说这个V2代表你的第二个顶点,对应的这个下标啊,表示第二个。第二个顶点,顶点对应的这个下标。下标,也就是说你在描述这两个顶点的关系的时候,V1代表第一个顶点的下标,第2VR代表第二个顶点,下标到底是第几个?那你根据这个实际情况看,比如你是C,那就是下标为二了,以此类推。全值表示什么呢?这个weight表示它们的这个值,或者说就是你认为你你这个矩矩阵里面你想用什么来表示它们是关联的?
11:10
就这意思,OK,好,那这个就写完了,写完过后,写完过后其实一个最基本的这个就做完了。其实最基本的这个就做完了,就是一个是呃添加。节点一个是添加我们的边,实际上这个时候就做完了,那这里呢,我们顺带把它一些常用的方法也给它写进去,好,我这一开始写几个常用的方法啊,各位同学看一下哪些方法是我们常用的呢?老师给大家捋一捋,我们写出这样几个常用的方法。就是图中,图中常用的方法,我们写几个,第一个呢,我们写一个就是返回,对返回节点的个数。就你现在到底有多少个节点,这个图里面有多少节点,那么int,我们写个get number of什么呀,Ver。
12:08
是不是这个很好很好解决,就直接一个return什么呢?Ver list.size就可以了。这是有时候会经常用到的,我们再写一个方法,得到边的数目,就是你现在这个图有几条边呢?我们也写一个方法好吧,Get number of什么呢?Ages。有多少条边,这个边的数目其实就是刚才我们一直在去加,加的哪一个呀,是不是我们每加一个边,是不是把它加加了,把它返回去就可以了。哎,这是有时候会用到的,我们再写一个。重要的方法就是返回节点I,这个I代表它的下标。代表它下标对应的值,或者叫数据,你比如说你如果给我传一个零,那么我就返回A啊,类似于这样一个感觉啊,零返回的就是A,一返回的就是B,二返回的就是C,以此类推,就是这个跟你的。
13:21
跟你这个加入节点的顺序是有关系的。那现在呢,我们就把它写一下呗,Public你返回一个什么呢?OK,我们返回string,因为目前呢,呃,我是按照呃按照这个字符串去添加的,我就是个value。Value by什么呢?通过索引你给我传一个I,我就给你返回明白,那就谁呀,就是ver。它的,呃,应该怎么写啊,点get,用get按索引来返回就可以了。好,这是我们的又一个方法,那么有时候我们还需要一个方法干什么呢?就是返回啊,返回谁呢?V1和V2的全值。
14:06
全值,也也就是说这个这个值你在加这个V1和V2的时候,你认为他们这两条边它的一个值是什么样子的?对我们现在默认,我们现在认为就是一对吧,我们现在认为就是一,那么我把这个方法也给他写一下。那怎么写呢?就public int get weight全职,那你要拿到全职,你要给我一个下标,就是这两个点或者顶点的下标就可以给你返回,怎么返回呢?非常的简单,就edge。找一个把V1放这把V2放这就可以了。好,同学们,这个方法我们又写完了,那最后是不是我们还应该有个方法能够把我把我们这个图给显示一把呀。就是你你能把这个矩阵显示出来,是这意思吧,好,我再写一个方法啊,也是经常使用到的,我们再写一个显示。
15:06
图对应的矩阵,也就是说如果待会儿我们这个没问题,我们显示的矩阵长得就是这个样子的。长得就这样子的,OK。那显示这个句子分非常简单,Public void show。Graph就完事,诶,Graph。啊,那其实你要显示这个矩阵,其本质就是去便利我们这个。二维数组是不是啊,那就很简单了,同学们,我给他写一遍就行,诶在哪去了,刚才。在。在这儿好,在这儿我们其实就是变上,那就for循环,我们取出来一个。取出来这个呢,就是相当于是一个连接是吧,它是一个一位数组。因为你二位数组进行一个负循环增强的话,它先取出的是一个一位数组,是这样子的吧,所以A。
16:00
好,然后这边呢,我就简单一点,直接用一个a list的工具把它打出来就可以了。对,点to string,谁呢,就是link。好,那那到时候就是一排一排的就给我们输出来了,输一输上一一排一排数据啊,一行数据再输出下一行,好同学们,现在这个图就行完了,现在呢,我们来测试一把,看看我们这个图到底是否正确,测试一把。代码测试一把图是否创建OK,那么怎么来玩这个事情呢?首先同学们都知道,我们先把这个N定下来,这是边的数目,比如说现在啊,节点的个数。这个地方是五,我这写一个就是就是节点的个数,我们现在一共有几个节点呢?数一数。一共五个好,N就是五。那这个节点有了功能,现在呢,我们还要把这些顶点的值拿到,比如说我就写个叫做呃labels吧,或叫做呃,Ver ver ver的一个值。
17:11
好,这个值呢,我们用一个数组时均数组来写就完事了,好吧,简单一点,那这个数组怎么写走我们第一,我们按顺序来,第一个是A,第二个是B,第三个是C,第四个是D,没问题吧,同学们,下一个是E啊,我按照这个顺序来添加的。我按照这个顺序来添加的,OK,那有这个东西过后,是不是我们非常轻松的就可以把它搞定,因为你现在数据都有了。有了这个数据过后,我们直接来一个for,直接就创建,创建什么呀,创建这个图对象六一个。把这个图对象N代进去了,N代进去了,现现在告诉我别人说我们有五个顶点,好,现在我分配一个局部变量。
18:02
就变量好graph,那就有了这个图过后我们干什么呢?我们就循环到。循环的添加我们的顶点。OK,那就for循环呗,那么就for循环,使菌我取出来一个值value。从哪里取呢?从我们这一个。数组里面去。好,每取出来一个,我就像我们这个图形里面添加,怎么添加,刚才已经帮法写了,叫insert vertex。好,这就是这个值。就是我们这个顶点对应的字放进去了,对吧,所以说你你要写的更清楚一点,也可以写个,也可以写个ver。Takes也可以,好,也可以叫vertex,呃,我这面写个。干脆这样就不叫值了吧,就叫vertex,这样是不是更好一点,对不对,这样更好一点。
19:00
这样子好吧,这样子vertex有很多顶点,那么取出来一个就是一个顶点,再把这个顶点放到这里面去,只是大家明白这个顶点呢,是一个字符串就可以了,加进去了,那加进去过后这个事儿没有结束啊,你还要去,是不是要添加边呢?如果你现在没有添加边同学们可以看到你便利的话呢,这个。这个矩阵它其实是全零的,是不是现在呢,我们要添加边,那添加边呢,我们这儿只有一步一步的写了,各位同学,因为这个边的关系呢,我们没有办法做负循环了,叫insert edge,我们先来描述一下这个边的关系,我们看一看。目前的关系是A。Abba abba a和B连,A和C连好先把这两个连起来,我把这写写啊,就A和B是连的,A和C是连的,再看一下。再看BB和C是连的,B和A我们刚才已经这个关系已经有了,因为它是无相的,你连一次就可以了,B和C是连的,B和DB和E是连的,好,那大致已经出来,B和C是连的。
20:16
B和D是连的。B和E是连的,一共五条线,同学们是不是不是五条线,那我就按这个顺序来写了啊同学们,那V1我们先描述A和B的关系,A呢,它是下标为零,对不对,B下标为一,全值我们认为是一,好第一条线就连起了,也就说这句话呢,就代表A和B已经搞定,其他的我就快速的写一下,好吧,我就不写不一个个的注释了。我就不一个个注释了。我就不一个个做事了,OK。这边就去掉。去掉,那我们我看A和CA和CA应该是零和二的关系,是不是B和C呢?B下标为一,而C为二,没问题吧,B和DB显然是一。
21:09
没问题吧,B是一,D是几呢?D是三好的,这个是D是一,E是几呢?E是四好,这个就添加边就完成了,我们来显示一把,显示一把这个临接。临街的矩阵。临接矩阵,现在看看这个临界矩阵跟我们想的是否一样,Graph。点show我们的graph,来,朋友们运行一把。运行一把好的,运行完了过后,我们可以看到这个图跟我们想的诶是一样的,大家看到没有。呃,前面是零。11100看对不对。011100好,下面是10111。10111好,这边是一一一两个一,后面三个零。
22:00
两个一后面三个零,第第四行是零一后面三个0013个零,再下面这一行在下面也跟上面是一样的,0101后面三个零,好了,同学们,那这样子呢,我们已然把我们这个图创建起来了,大家看看能不能理解并不难对不对,并不难,并不难,OK,那关于图的一个创建。包括它的分析,我们就说到这儿,待会儿呢,我们继续讲图的遍历。
我来说两句