“图”是不是“图画”或“图形”中的图呢？不是的，这里说的“图”是一种数学模型，即一种数据结构，也就是图结构，简称图。

　　18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来，如下概述图所示。

有个人提出一个这样的问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。很多人都去尝试，但都以失败告终。于人们去求助大数学家欧拉。

　　虽然欧拉是大数学家，但他也没接触过类似的问题。不过数学家与其他人不一样，他能把一个具体的问题抽象为数学模型。他考虑A、D两岛和B、C两岸的大小及桥的长度都与这个问题无关，于是把A、D两岛和B、C两岸抽象成一个点，把七条桥变成连接这四点的七条线段。如下图所示。

把七桥问题转化成一个几何问题——一笔画问题：不重复经过连接线段，一次经过所有线段。人们看了欧拉画的示意图和听了他的解答，才恍然大悟——七桥问题无解。

　　一个连通图，除了出发点和结束点，经过点必然有进有出，由于不能走重复路，因此经过点都必须要有偶数条路与别的节点相连。如果出发点和结束点不同，则它们都是奇数条路与别的节点相连（奇点）。这样，如果多于2个奇点，那也不行了。如果出发点和结束点相同，则不能有奇点。七桥问题中4个点都是奇点，所以是不可能一笔画的。

　　欧拉解决七桥问题所用的图与我们图画或图形中的图有很大的差别。因为它里面的点只是一个符号，而关注的是点之间的关系——连线，这就是所谓的数学中的“图”。因此我们可以认为“图”是节点关系的数学模型，而对于节点本身的属性则忽略了。

　　图结构是一种比树形结构更复杂的非线性结构。在树形结构中，节点间具有分支层次关系，每一层上的节点只能和上一层中的至多一个节点相关，但也可能和下一层的多个节点相关。而在图结构中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的。因此，图结构被用于描述各种复杂的数据对象，在计算机科学、人工智能、电子线路分析、最短路径寻找、工程计划、化学化合物分析、统计力学、遗传学、控制论、语言学和社会科学等方面均有不同程度的应用。图结构如下图所示。

　　有关图的基本概念如下：

　　■图的组成：图G是由一个非空的有限顶点集合V和一个有限边集合E组成，定义为G=(V,E)。

　　■无向图：若图的每条边都没有方向，则称该图为无向图。比如：人行道，可去可回。如下图所示。

　　■有向图：若图的每条边都有方向，则称该图为有向图。比如：汽车的单行线，只能向一个方向前进，禁止逆行，如下图所示。

　　■路径：图结构中，节点A与节点E之间存在：经过节点B，C，D之间的边，最终到达节点E，称A与E之间存在一条路径。

　　■路径长度：一条路径上经过的边的数量，如下图所示。

　　■环：某条路径包含相同的顶点两次或两次以上，如下图所示。

　　■有向无环图：没有环的有向图，简称DAG，如下图所示。

　　■完全图：任意两个顶点都相连的图称为完全图，又分为无向完全图和有向完全图。

　　■连通图：在无向图中，若任意两个顶点之间都有路径相通，则称该无向图为连通图。

　　■强连通图：在有向图中，若任意两个顶点之间都有路径相通，则称该有向图为强连通图。

　　计算机是不懂我们这种“图”的，如何把图输入计算机呢？图既然是节点的关系，自然是一个表或二维数组，也叫做矩阵。我们把这种矩阵叫做邻接矩阵。邻接矩阵是一个n×n的二维数组（正方形），用来描述图中节点之间的连接关系，如下图所示。

　　在上面的邻接矩阵中，有很多0，意思就是行列相交的2个节点无连线。这些0实际只是占位符，没什么意义，因此只要把不是0的数记下就行了。但失去占位符，就无法知道是与那个节点的连线了。解决的办法就是用一个单向链表连接每行的节点——邻接表。邻接表是图的一种链式存储结构，对于图G中每个顶点Vi，把所有邻接于Vi的顶点Vj链成一个单链表，这个单链表称为顶点Vi的邻接表。图的邻接表是N个链表构成的个数组，如下图所示。

　　邻接表虽然没有占位符，但是每个数据项又多了节点和指针，如果节点连线较多，不但不能减少数据规模，反而增大了数据规模。

     对于一个具有n个顶点e条边的无向图，它的邻接表有n个顶点，2e个边，它的邻接矩阵是一个nXn的二维数组。对于一个具有n个顶点e条边的有向图，它的邻接表有n个顶点e个边，它的邻接矩阵是一个n×n的二维数组。

    如果图中边的数目远远小于节点数量的平方，这样的图结构称作稀疏图，这时用邻接表表示比用邻接矩阵表示节省空间。如果图中边的数目接近于节点数量的平方（若是无向图，边的数量接近于nX(n一1)），称作稠密图，考虑到邻接表中要附加链域，采用邻接矩阵表示法为宜。

　　在上面的图中，用1表示有连线，0表示无连线，这样的图实际就是拓扑图。欧拉在拓扑图的基础上，开创了数学分支——拓扑学。

　　在很多情况下，边是有权重的，意思就是不能只用1来表示边，而还要用其它数表示边。比如：北京、天津、郑州、青岛4个节点，它们之间的距离是不同的，所以它们之间的边应该用长度的比例关系描述。另有可能，有的节点之间距离虽然短，但很难走，比如山中的羊肠小道；而有的节点之间的距离虽然长，但很好走，比如高速公路，所以走长路消耗的能源和时间可能更短，而走短路可能更费劲。把路程、所耗能源和耗时等因素考虑进对边的描述中，于是产生了边的权重这一概念，也就是节点之间的边可以用不同的数字表示，那么在选择路径上会更加科学，如下图所示。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社

２、百度百科——七桥问题https://baike.baidu.com/item/%E4%B8%83%E6%A1%A5%E9%97%AE%E9%A2%98/2580504?fr=aladdin