图的基本概念-Toy模板网

这篇具有很好参考价值的文章主要介绍了图的基本概念。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

图的基本概念

一个图 G 它可以由顶点集（图 G 中顶点的有限非空集） V 和边集（图 G 中顶点之间的关系集合） E 所组成。图中顶点个数也可以称为图的阶；任何一条边的两头必须连接某一个顶点。图不可以是空，即顶点集 V 一定是非空集，但边集 E 可以是空集。

子图,数据结构,图论,数据结构,算法

有向图	无向图
无向图里的各条边我们可以把它称为无向边（或者简称弧）	有向图里把各条边称为有向边（或者简称为边）
<v，w>，v：弧尾 w：弧头弧头弧尾顺序调换表示的不一样	(v，w) 或（w，v）这两种方式等价

简单图：在这个图里不存在重复的边，并且也不存在顶点到自身的边。

子图,数据结构,图论,数据结构,算法

多重图

一个图里存在重复的两条边或者自身连向自身的边。

子图,数据结构,图论,数据结构,算法

顶点的度

在无向图中，指依附于这个顶点的边到底有多少条，记为 TD(V)，V指的是某一特定的点。

子图,数据结构,图论,数据结构,算法

在有向图中，入度是以顶点为终点的有向边的数目，记为 ID(V)；出度是以顶点为起点的有向边的数目，记为 OD(V)；顶点 v 的度等于入度和出度之和 TD(V) = ID(V) + OD(V).

子图,数据结构,图论,数据结构,算法

路径-----顶点 vp 到顶点 vq 之间的一条路径是指顶点序列

回路-----第一个顶点和最后一个顶点相同的路径称为回路或环

简单路径-----在路径序列中，顶点不重复出现的路径称为简单路径

简单回路-----除了第一个顶点和最后一个顶点之外，其余的顶点都不重复出现的回路

路径长度-----两个顶点之间的路径，这个路径上总共有多少条边

点到点的距离-----两个顶点之间最短路径的长度作为顶点到顶点之间的距离;如果两个顶点之间根本就不存在路径的话，那么我们需要把它们之间的距离记为∞(无穷)。

无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的;有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的.

注意:

对于 n 个顶点的无向图 G, 若 G 是连通图,则最少有 n -1 条边; 若 G 是非连通图,则最少有条边.
对于 n 个顶点的有向图 G, 若 G 是强连通图,则最少有 n 条边（形成回路）

子图与生成子图

子图：一个图里边有一些顶点集和边集，取出几个顶点，然后再取出整个边集当中的某一个子集，用这样的方式构建的这个图就是原图的一个子图。注意并不是从原图当中任意选择几个顶点，任意选择几条边都能构成子图的，因为子图首先它必须是一个图。

子图,数据结构,图论,数据结构,算法

生成子图：子图里边包含了原图当中的所有顶点，那么这个子图就可以称为原图的一个生成子图。

子图,数据结构,图论,数据结构,算法

对于有向图的子图和生成图的概念一样。

连通分量（无向图）与强连通分量（有向图）

连通分量：无向图中的极大连通子图（子图必须连通，且包含尽可能多的顶点和边）

子图,数据结构,图论,数据结构,算法

强连通分量：

如图在图 G 中A,B,E,C,D是强连通的，将这个部分择出来就是一个极大的强连通分量。而顶点 F 和 A,B,C,D,E不是强连通的(从其他顶点到 F 的路径存在，而 F 到其他顶点的路径不存在)，所以 F 和 A,B,C,D,E是不强连通的。

子图,数据结构,图论,数据结构,算法

生成树和生成森林

生成树：对于一个连通的无向图，它的生成树指的是这个图里边的全部顶点的一个极小的连通的子图。也就是说这个子图它要包含原图里边的全部顶点，要包含全部顶点，同时要保证这个子图连通，而且要极小(指在这个子图里边的边要尽可能的少,但要保持连通)。若图中顶点数为 n ，则他生成树含有 n-1 条边。若砍去一条边，则会变成非连通图；若加上一条边则会形成一个回路。

子图,数据结构,图论,数据结构,算法