图论(一)

发表于 2019-09-13  215 次阅读


在计算机编程里面,算法几乎无处不在,今天来讲一讲算法当中的图论,我第一次接触的时候: 尼玛,这是什么鬼??? 看懂基础操作以后: 看来还挺简单的,下面是我学习图论的感想

我Wzl就算从这里跳下去,也不会学习图论!
1个月后...
唉呀,这么简单,真香!

好了,废话不多说,
首先,来说一说什么是图:图,就是有顶点(结点)有边的东西,具体样纸百度搜索。

其中又有有向图和无向图。

有向图:有方向的图,有的话,它的边上就会有箭头
无向图:反之(原谅我懒)

老夫一看你们那个样纸,就没去搜,所以在电脑给你们画了出来
先来一份儿图:

再来一份儿有向图:

有向图

下面也就是无向图了:

无向图

啊,我被我的画风惊呆了,应该可以“获奖”了吧!嘻嘻~

下面呢,来给大家讲一讲图论的矩阵表示,也就是邻接矩阵(尼玛,这有事啥玩意儿???),额,这个我第一次学的时候,感觉很懒,但是后面学起来发现其实很简单,就是一个二维表而已

就拿上面的有向图来说吧

有向图的邻接矩阵图

先说一下这个“游戏”的规则,从自己本身的点到自己本身,标记为0,有边的话标记为1,如果两点之间没有距离的话,那么就标记成无穷大(∞),细心的博友也许会发现,正对角线为0,那么怎么看呢,例如,从1到2,有边,所以(1,2)为1,说实话,画这个图有点后悔了,因为这个的话,除了本身到本身以外都有边,(艹皿艹 ),先前咋没想到,难得重新画了,说一下吧,在这里,我们把1到4的边去掉,那么1也就不能到达4,因此(1,4)就应该改为∞,而不应该为1,这样做,第一排也应该变成0 1 1 ∞,现在再说一下这个0是咋回事儿的呀,因为从1到它本身,你不需要经过任何一点,所以我们规定,从一个点到达他本身,那么就是0,所以(1,1)、(2,2)、(3,3)、(4,4)这几个点,都为0.

那么现在再来看一看无环图的吧:

无向图的邻接矩阵图

无向图,正因为它无向,所以它就是单行道,而有向图,就是单行道。(PS:这都理解不到的话,你可以这样认为有向图,你跨出了门,但是没带了钥匙,门又锁住了,就回不去了,只能够去其他地方,再试一试能不能够走回来;而无向图,就像是你带了钥匙时,在一个门面前一样,你随时可以出去,也随时可以进来)

这个地方,我也就不说多了,应该都看得懂吧,另外再说一下,有向图不一定关于正对角线对称, 而无向图则一定关于正对角线对称,并且正对角线都为0(特么感觉像看生物里面遗传与变异那个图一样,正对角线都是纯合子[流汗~]),你有多少个顶点,那么就画多少的平方大的邻接矩阵图,开二维数组空间的话至少都要开f[n][n]这么大(n代表顶点个数,若画邻接矩阵图,那么就画长为n,宽为n的图,就像我画的这样,好吧我也画的不大标准,具体的自行百度,懒得画标准的)

纯属手打!!!!!!
以后我会试着自己写一篇关于排序的,到时候再看吧!

本站文章基于国际协议BY-NA-SA 4.0协议共享;
如未特殊说明,本站文章皆为原创文章,请规范转载。

2

撰写漫天的星辰,只为站在海那边的你