图graph，G(V,E)=Vertex(顶点集合)+Edge(

2018-07-29 本文已影响651人 XDgbh

线性表是一对一，树是一对多，图是多对多的关系。
图中的数据元素我们称为顶点（相对于树中的结点），顶点集合不能为空，边集合可以为空。
无向图——只要图中有一条边是无向边（A,B）。
有向图——任意两顶点之间的边都是有向边（弧）<A,B>。
无向完全图——n个顶点中任意两顶点之间都存在边的无向图。边的总数是n*(n-1)/2。
有向完全图——n个顶点中任意两顶点之间都存在方向相反的有向边的有向图。边的总数是n*(n-1)。
权——与图的边相关的数字。这些权可以表示从一个顶点到另一个顶点的距离或耗费。
网——带权的图。如网络图中，各条边就是链路，链路都是有带权（距离或带宽）的。
子图——G=(V,{E})，G'=(V',{E'})，其中V'是V的子集，E'是E的子集，则称G'是G的子图(subgraph)。
顶点v的度degree——是和顶点v相连接的边的数目。对于有向图的顶点的度还分为出度和入度。
邻接点——同一条边的两个点互为邻接点。
路径——指从一个顶点到另一个顶点所经过的顶点的序列。树的路径唯一，但图的路径不唯一，所以有很多求最短路径的算法。在网络图中，路径又叫路由。
路径的长度——路径上的边或弧的数目。
回路或环——第一个顶点和最后一个顶点相同的路径。
简单路径——路径序列中没有重复出现的顶点。
简单回路——除了第一个和最后一个顶点相同外，其余的顶点都不相同。
连通图（connected graph）——无向图中任意两个顶点都有路径（即都是连通的）。
非连通图——存在两个顶点之间没有路径，即不连通。有n个顶点，但只有小于n-1条边，一定是非连通图。
连通分量——无向图中的极大连通子图。连通图本身即是，而非连通图中最大的连通子图即是。
强连通图——有向图中，任意两个顶点都存在双向连通的路径。有向图的非强连通图，对应有强连通分量。
生成树——一个连通图的极小连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边（即去掉了环路）。不过n个顶点有n-1条边并不一定是生成树，比如一个非连通图中有一部分是个环路。因此生成树的前提一定是连通图。
有向树——一个有向图恰有一个顶点的入度为0（根结点），其余顶点的入度均为1。
生成森林——一个有向图的所有顶点，被分成若干颗不相交的有向树，这些有向树就组成了有向森林。