|
图  图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E),G表示一个图，V是图G中顶点的集合，E是图G中边的集合。 注意： 1. 线性表中数据元素叫做元素，树种数据元素叫结点，图中数据元素叫顶点 2. 线性表和树可以没有数据元素和结点，分别为空表，空树。图结构中，不允许没有顶点 3. 线性表中相邻数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，图中，任意两个顶点之间可能有关系，顶点之间的逻辑关系用边来表示，边集可以为空。 图的定义： 1. 无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对（Vi, Vj）表示 2. 无向图：图中任意两个顶点之间的边都是无向边，则称该图为无向图 3. 有向边：若顶点Vi到Vj之间的边有方向，则称这条边为有向边，也称为弧，用有序偶对<Vi, Vj>表示, Vi称为弧尾，Vj称为弧头。 4. 有向图：如果图中任意两个顶点之间的边都是有向边，则称该图为有向图 5. 简单图：不存在顶点到其自身的边，且同一条边不重复出现 6. 无向完全图：无向图中，如果任意两个顶点之间都存在边 n (n -1)/2条边 7. 有向完全图：有向图中，任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。n (n-1)条边 8. 稀疏图： 有很少条边或弧的图 9. 稠密图：有很多条边或弧的图 10. 权：有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（weight） 11. 网：带权的图通常称为网 图的顶点与边之间的关系 无向图 1. 邻接点 2. 顶点V的度：是和V相关联的边的数目，记为TD(v) 有向图 对于有向图G=(V, {E})，如果弧<v, v'>属于E，则称顶点v邻接到顶点v'，顶点v'邻接自顶点v。顶点v为头的弧的数目成为v的入度，记为ID(v)， 以v为尾的数目称为v的出度，记为OD(v)。顶点v的度为TD(v)=ID(v)+OD(v) 3. 路径的长度是路径上的边或弧的数目。 连通图相关术语 连通图：在无向图G中，如果顶点v到顶点v'有路径，则称v和v'是连通的。如果对于图中任意两个顶点vi、vj属于E，vi和vj都是连通的，则称G是连通图 连通分量：无向图中的极大连通子图称为连通分量，注意连通分量的概念： 1. 要是子图 2. 子图要是连通的 3. 连通子图含有极大顶点数 4. 具有极大顶点数的连通子图包含依附于这些顶点的所有边 强连通图：在有向图G中，如果对于图中任意两个顶点vi、vj属于V，vi不等于vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图 强连通分量：有向图中的极大连通子图称为有向图的强连通分量 图的抽象数据类型 存储结构 邻接矩阵 邻接表：数组与链表相结合的存储方法 十字链表 |
|
|
