文章目录
- 前言
- 一、图的定义与术语
- 总结
前言
我们知道，在数据结构中，逻辑结构分为四种：
- 集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系
- 线性结构：线性结构中的数据元素之间是一对一的关系
- 树形结构：树形结构中的数据元素之间存在一对多的层次关系
- 图形结构：图形结构中的数据元素是多对多的关系
今天，我们就开始学习第四种结构，也就是图，一种多对多的数据结构、
一、图的定义与术语
1.各种图的定义
图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
对于图的定义，需要几个注意的地方：
- 在图中的数据元素，我们称之为顶点(Vertex)
- 在图结构中，不允许没有顶点，即定义中的有穷非空
- 在图中，任意两个顶点之间都有可能有关系，顶点之间的逻辑关系用边来表示，边集可以为空
1.1无向图
无向边：若顶点Vi和vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对（vi， vj）来表示。
如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（undirected graphs）。如上面那张图，就是一个无向图，连接顶点A和D的边就可以用无序对（A，D）表示，也可以用（D， A）表示。
1.2有向图
有向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称弧(Arc)。用有序偶<Vi,Vj>表示，Vi称为弧尾（Tail），Vj称为弧头（Head）。
如果图中所有的边都为有向边，则称该图为有向图（directed graphs）。如上图，就是一个有向图，连接顶点A和D的有向边就是弧，A是弧尾，D是弧头,<A, D>表示弧，此时不能写成<A, D>
1.3简单图
在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。
1.4完全图
完全图：任意两个顶点之间都有一条边相连。
- 在无向完全图中，n个顶点总共有n(n-1)/2条边
- 在有向完全图中，n个顶点总共有n(n-1)条边
1.5稀疏图、稠密图
稀疏图：有很少条边或弧的图
稠密图：有很多条边或弧的图
这里的多和少都是模糊的概念，是相对而言的。
1.6权和网
与图的边或弧相关的数叫权（Weight），这种带权的图通常称为网（Network）。
1.7子图
假设有两个图G1=（V1，{E1}），G2=（V2，{E2}），如果V1
V2且E1E2，则称G1为G2的子图（Subgraph）。
2.顶点与边的关系
2.1邻接
对于无向图G=（V，{E}），如果边（Vi，Vj）
E，则称顶点Vi和Vj互为邻接点（Adjacent），即Vi和Vj相关联。）
对于有向图G=（V，{E}），如果弧<Vi，Vj>E，则称顶点Vi邻接到Vj，顶点Vj邻接自顶点Vi
2.2关联(依附)
无向图：边（Vi，Vj）依附（incident）于顶点Vi和Vj，或者说（Vi，Vj）与顶点Vi和Vj相关联。
有向图：弧<Vi,Vj>和顶点Vi，Vj相关联。
2.3入度和出度
以顶点Vi为头的弧的数目称为Vi的入度（InDegree）,记为ID（Vi）;以Vi结尾的弧的数目称为Vi的出度（OutDegree），记为OD（Vi）。
2.4顶点的度
无向图：顶点v的度是和v相连的边的数目，记为TD（v）。
有向图：顶点v的度为TD（v）=ID（v）+OD（v）。
2.5路径和路径长度
无向图G=（V，{E}）中从顶点v到v'的路径（Path）是一个顶点序列（v=vi,0,vi,1,……vi,m=v'）,其中(vi,j-1,vi,j)E,1<=j<=m.
有向图的路径则是有方向的。
路径长度就是路径上的边或弧的数目。
2.6回路
第一个顶点和最后一个顶点相同的路径称为回路或环（Cycle）。
2.7简单路径
序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
3.连通图的相关术语
3.1连通图和连通分量
在无向图中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。如果对于图中任意两个顶点vi、vjV，vi和vj是连通的，则称G是连通图（Connected Graph）。
无向图中的极大连通子图称为连通分量。极大连通子图的意思是，该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。
注意连通分量的概念，它强调：
- 要是子图
- 子图要是连通的
- 连通子图含有极大顶点数
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边
3.2强连通图和强连通分量
在有向图G中，如果对于每一对vi、vjV、vi != vj，从vi到vj和从vi到vj都存在路径，则称G是强连通图。
有向图中的极大强连通子图称做有向图的强连通分量。
3.3连通图的生成树
所谓一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。不过，有n-1条边并不一定是生成树。
3.4有向树
如果一个有向图恰好有一个顶点的入度为0，其余顶点的入度均为1，则是一个有向树。
3.5有向图的生成森林
一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只是足以构成若干棵不相交的有向树的弧。
总结
