龙空技术网

有趣的图(一)(55)

和猫妹学Python 24

前言:

当前咱们对“画无向图的邻接矩阵”大概比较注重,姐妹们都想要分析一些“画无向图的邻接矩阵”的相关知识。那么小编在网上收集了一些有关“画无向图的邻接矩阵””的相关内容,希望看官们能喜欢,朋友们快快来学习一下吧!

小朋友们好,大朋友们好!

我是猫妹,一名爱上Python编程的小学生。

和猫妹学Python,一起趣味学编程。

今日主题

咱们今天的内容比较抽象,也比较有趣。

这里的图是指计算机中的图,确切地说,是一种数据结构。

在解决实际问题时,经常会用到。

我们举个生活中的例子:

一个人要把大陆31个省会城市自驾游一遍,最短路径是多少公里?

一个人能在一个省份只经过一次的情况下把大陆31个省会城市自驾游一遍吗?

今天的主题有:

图的定义

图的分类

图的接口

图的Python表示

图的定义

图G由两个集合组成,顶点集合和边集合。

一个由顶点(vertex)构成的有穷非空集合和一个由边(edge)构成的有穷允空集合。

比如上图:

顶点集合有:1,2,3,4,5,6,7

边集合有:有10条,带权值

比如上图:

顶点结合有:0,1,2,3,4,5

边集合有:共9条,不带权值

图的分类

图根据边是否有方向,分为有向图和无向图。

(a)为有向图,(b)为无向图

图根据边是否有权值,分为边无权值的图,边有权值的图。

如下图:

节点的度

无向图中结点的度:顶点引出的边数和。

有向图中结点的度:分为入度和出度。入度为指向该顶点的边数和,出度为该顶点向外指向的边数和。

图的接口

addVertex(v)添加顶点

deleteVertex(v)删除顶点

vertexes(v)获取所有顶点

addEdge(v1,v2)添加一条边

deleteEdge(v1,v2)删除一条边

edges()获取所有边

adjacent(v)获取v的所有邻接顶点

isEmpty()判断图是否为空

Python中的图

可以使用Python自带的列表、集合、字典来表示图,也可以使用第三方库networkx。

可以使用邻接矩阵、邻接列表、邻接集合、邻接加权字典来表示图。

邻接矩阵

设无向图G=(V,E),其中顶点集V=v1,v2,…,vn,边集 E=e1,e2,…,eε。用aij表示顶点vi与顶点vj之间的边数,可能取值为0,1,2,…,称所得矩阵A=A(G)=(aij)n×n为图G的邻接矩阵。

邻接矩阵可以描述有向图和无向图。

邻接矩阵的存储特点:

(a)无向图的邻接矩阵是一个对称矩阵,有向图不一定是。

(b)邻接矩阵所需的存储空间值域只与顶点数有关系。

(c)用邻接矩阵存储图,容易判断两个点之间是否有边。

(d)如果一个有向图的邻接矩阵为三角矩阵(主对角线为0),则它的拓扑排序一定存在。

(e)小技巧:

无向图:邻接矩阵的第i行或者第i列的非零元素的个数正好是第i个顶点Vi的度;

有向图:邻接矩阵的第i行的非零元素个数正好是第i个顶点Vi的出度,第i列非零元素的个数正好是第i个顶点Vi的入度。

(f)邻接矩阵也可以表示有权值的图,此时单元格内容是边的权值。

上图Python代码参考:

邻接矩阵的缺点:

当结点很多,边很少时,很多个0,浪费空间。寻找每个结点的邻接顶点时,需要遍历列表,稍有不便。

邻接集合

只存储有边的数据,不存储无边的数据。

比如上图中,和a相邻的边,只存储ad和ae,只需要存储和a相邻的结点是d和e就可以了。

邻接列表

和邻接集合类似,只是将集合变为列表。

邻接加权字典

可以使用邻接加权字典表示有权值的图。

好了,我们今天的学习就先到这里。

你学会了吗?

好了,我们今天就学到这里吧!

如果遇到什么问题,咱们多多交流,共同解决。

我是猫妹,咱们下次见!

标签: #画无向图的邻接矩阵 #无向图的邻接矩阵的特点