来自计算思维百科
跳转至: 导航搜索

图是非线性的数据结构。在数学、化学、物理、工程和计算机科学中有大量的问题需要表示数据对象之间的各种关系,图是表达这些关系的常用模型。例如,计算机网络有大量设备结点,通过通信线路把它们有机连接成一个系统,用图就可以方便地表示计算机网络的一些问题。

图的定义:图G是由两个集合V(G)和E(G)组成的,记为

     G=(V, E)

其中:V(G)是顶点的非空有限集合;

     E(G)是边的有限集合,边是顶点的无序对或有序对。

图是顶点和线段的集合,结点称为顶点,线段称为线,用于连接一对顶点。图包括有向图和无向图。在有向图中,每条线都有一个方向指向后继结点,如图1(a)所示。有向图中的线称为弧,在有向图中,两顶点间弧的流向只能朝一个指定方向。而在无向图中,边是没有方向的,称为边,如图1(b)所示。在无向图中,两顶点之间的流向可以按照任意一个方向。有时图的边具有与它相关的数值,这种与边相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或花费的代价。此类图又称为网。

3.2.18.png3.2.19.png

         图1 图

例如,格尼斯堡“七桥”问题:两个岛与陆地间有七座桥,如图2(a)所示,能否不重复走遍所有道路。可以将该问题中的地图抽象为图,如图2(b)所示,然后将七桥问题转换为“一笔画”问题,即如何不重复地画出一个几何图形的问题。

3.2.20.png3.2.21.png

                    图2 “七桥”问题

  对于上述的每种数据结构,均存在多种不同的物理存储方式,并为每种数据结构实现了常用的一些操作,如如何在数据结构中进行数据元素的查找、添加、删除、遍历等等。