数据结构与算法（六）图

一、图的定义及术语
　　图状结构是一种比树形结构更复杂的非线性结构，在树形结构中，结点具有分支层次关系，每一层的结点只能和上一层的至多一个结点相关，但可能和下一层的多个结点相关；而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的；因此，图是比树更一般、更复杂的非线性结构，常被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。
　　图（graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。在线性表中我们把数据元素叫做元素，树中将数据元素称为结点，在图中数据元素，我们称之为顶点（Vertex）；线性表中可以没有数据元素，称为空表，树中可以没有结点，叫做空树，同样，在图结构中，不允许没有顶点，在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空；在线性表中，相邻的数据元素之间具有线性关系，在树结构中，相邻两层的结点具有层次关系，而在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。
　　
　　无向边：若顶点Vi到Vj之间的边是没有方向的，则称这条边为无向边（Edge），用无序偶对（Vi，Vj）来表示；
　　无向图：如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）；
　　
　　有向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧（Arc）；用有序偶<Vi，Vj>来表示，Vi称为弧尾（Tail），Vj称为弧头（Head）；
　　有向图：如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs）；下图就是一个有向图，连接顶点V1到V2的有向边就是弧，V1是弧尾，V2是弧头，<V1，V2>表示弧，注意不能写成<V2，V1>。
　　
　　无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图，含有n个顶点的无向完全图有n*(n-1)/2条边；
　　
　　有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称为该图为有向完全图；含有n个顶点的有向完全图有n*(n-1)条边；
　　
　　连通图：在无向图G中，如果从顶点V到顶点V`有路径，则称V和V`是连通的，如果对于图中任意两个顶点Vi、Vj属于V，Vi和Vj都是连通的，则称G是连通图（Connected Graph）；
　　

二、图的存储结构
　　邻接矩阵Adjacency Matrix）：图的邻接矩阵（存储方式是用两个数组来表示图，一个一维数组存储图中的顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息；
　　
　　邻接表（Adjacency list）：数组与链表相结合的存储方法称为邻接表；邻接表的处理方法是：在图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便；另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息；图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点Vi的边表，有向图称为顶点Vi作为弧尾的出边表；从下图中我们可以知道，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点；边表结点由adjvex和next两个域组成；adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。
　　

三、图的遍历
　　图的遍历（Traversing Graph）：从图中某一个顶点出发访遍图中的其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历；
　　深度优先遍历（Depth First_Search）：它从图某个顶点V出发，访问此顶点，然后从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；
　　
　　广度优先遍历（Breadth_First_Search）：类似于树的按层次遍历的过程，假设从图中某顶点V出发，在访问了V之后依次访问V的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使"先被访问的顶点的邻接点"先于"后被访问的顶点的邻接点"被访问，直至图中所有已被访问的邻接点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至所有顶点都被访问到为止；换句话说，广度优先搜索遍历图的过程是以V为起始点，由近至远，依次访问和V有路径相通且路径长度为1,2，……的顶点。