数据结构之图（概念）

一、图的相关概念    

    图的定义：图是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

    无向边：若顶点V_i 到V_j 的边没有方向，则称这条边为无向边，用无序偶对（V_{i ，}V_j）来表示。

    如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。

    有向边：若从顶点Vi 到V_j的边有方向，则称这条边为有向边，也称为弧。用有序偶对（V_{i ，}V_j）来表示。V_i称为弧尾，V_j称为弧头。

    如果图中任意顶点之间的边都是有向边，则称该图为有向图。

    简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

    无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。

    有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条边。

    因此，对于有n个顶点和e条边数的图，无向图0<=e<=n(n-1)/2，有向图0<=e<=n(n-1)。

    有很少条边或弧的图称为稀疏图，反之称为稠密图。

    路径的长度是路径上的边或弧的数目。

    第一个顶点到最后一个顶点相同路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

    连通图相关术语

    在无向图G中，如果从顶点v到顶点w有路径，则称v和w是相通的。如果对图中任意两个顶点Vi和V_j 属于E，则两个顶点是连通的，则称G是连通图。如下图1，它的顶点A都顶点B、C、D都是连通的，但显然顶点A与顶点E或F就无路径，因此不能算是连通图。而图2，顶点A、B、C、D相互都是连通的，所以它本身是连通图。

    无向图中的极大连通子图称为连通分量。注意连通分量的概念，它强调：

    （1）要是子图；

    （2）子图要是连通的；

    （3）连通子图含有极大顶点数；

    （4）具有极大顶点树的连通子图包含依附于这些顶点的所有边。

    在有向图G中，如果对于每一对Vi和Vj 属于顶点集V，Vi不等于V_j ，从Vi到Vj和从Vj到Vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

    所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。比如下图的图1是一个普通图，但显然它不是生成树，当去掉两条构成环的边后，比如图2或图3，就满足n个顶点n-1条边且连通的定义了。它们都是一棵生成树。从这里也知道，如果一个图有n个顶点和小于n-1条边，则是非连通图，如果它多于n-1条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图2和图3，随便加哪两顶点的边都将构成环。不过有n-1条边并不一定是生成树，比如图4。

 二、图的定义与术语总结

    图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧头和弧尾之分。

    图按照边或弧的多少分为稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。

    图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。

    图上的边或弧带权则称为网。

    图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环当中不重复的叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称为强连通分量。

    无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点的入度为0其余顶点的入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

    参考：《大话数据结构》

                                                                                                       梦醒潇湘love

                                                                                                   2013-01-28  10:40