【数据结构】图的基本概念

图的定义

通俗来说一堆顶点被一堆线连在一起，这一坨顶点与线的集合

目录

图的定义

术语

有向图与无向图

简单图与多重图

度、入度与出度

路径与回路

路径长度与距离

子图

连通、连通图与连通分量

强连通、强连通图与强连通分量

完全图

生成树与生成森林

权、网与带权路径长度

例题

---

就是图。

图的严格定义如下：

图G由顶点集 和边集 E组成，记为 G=(V,E)，其中 V(G)表示图 G中顶点的有限非空集;E(G)表示图 G中顶点之间的关系(边)集合。若V={v1,v2...，vn}，则用表示图G中顶点的个数，E={(u,v)|uV,vV}，用表示图G中边的条数。

术语

有向图与无向图

有向图：

若E是有向边(也称弧)的有限集合，则图G为有向图。弧是顶点的有序对，记为<v,w>其中v,w是顶点，v称为弧尾，w称为弧头，<v,w>称为从v到w的弧，也称v邻接到w。

E1={<2,1>}

无向图：

若E是无向边(简称边)的有限集合，则图G为无向图。边是顶点的无序对，记为（v,w）或(w,v)。可以说w和v互为邻接点。边(v,w)依附于w和v，或称边(v,w)和v,w 相关联。

E2={(2,1)}

说人话就是无向图的边没有箭头，有向图的边有箭头。

简单图与多重图

如果一个图 G满足以下两个条件：① 任意两顶点之间最多只有一条边；② 没有任何顶点通过边与自身相连，那么这个图称为简单图。
如果一个图 G允许两个顶点之间存在多条边，同时允许顶点通过一条边与自身相连，则称为多重图。

度、入度与出度

对于无向图，顶点的度指的是依附于顶点的边的条数，记为TD(v)。

对于有向图，顶点的入度指的是以该顶点为终点的有向边的数目（被箭头指向），记为ID(v)；出度指的是以该顶点为起点的有向边的数目，记为OD(v)；顶点的度为入度与出度之和。

无向图中顶点的度为顶点数的两倍（一个边连着两个顶点），有向图中所有顶点入度之和=出度之和=边数（一个弧有一个头和一个尾）。

路径与回路

顶点v1到v2的路径指的是能够从v1出发到达v2不中断的途径中所有的顶点与边。第一个顶点与最后一个顶点相同的路径称为回路或者环。

顶点不重复出现的路径称为简单路径；除了最后一个顶点和第一个顶点以外，其余顶点不重复出现的回路称为简单回路。

若图的边数大于顶点数-1，则图一定有环。

路径长度与距离

路径包含的边的数目为路径长度，顶点之间最短路径称为距离。如果顶点v1到达不了顶点v2，记两者距离为无穷。

子图

如果G1的顶点是G2顶点的子集，G1的边也是G2的边的子集，称G1是G2的子图。如果G1顶点完全继承G2，但是G1的边不一定完全继承G2，称G1为G2的生成子图。

这种情况G1不是G2的子图，因为G1不满足图的定义。

连通、连通图与连通分量

无向图中：

如果v与w有路径存在，称v与w连通。

如果一个无向图所有顶点之间都连通，则称该图为连通图。

一个图里的极大连通子图称为连通分量。

极大连通子图的极大指的是是尽量包含多的顶点和边。对于下面这张图，虽然123也是连通的，但是比1234少一个顶点，所以123不是图连通分量，1234是图的连通分量。

当然按照定义，一个孤立的顶点也是一个连通分量。

强连通、强连通图与强连通分量

有向图中：

如果v与w有路径存在，w与v有路径存在，称v与w强连通。

如果一个有向图所有顶点之间都强连通，则称该图为强连通图。

一个图里的极大强连通子图称为强连通分量。

完全图

对于无向图，如果任意一个顶点都与其他所有的顶点相连，则这样的图称为完全图。完全图的边数等于n+(n-1)+...+1=。对于有向完全图，则要求每个顶点有来去两条边相连，所以数目是无向完全图的两倍。

生成树与生成森林

连通图的生成树是包含图中全部顶点的一个极小连通子图。包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

这里的极小连通子图的极小指的是包含尽可能少的边。

权、网与带权路径长度

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

例题

1、含n个顶点的非连通图最多有几条边？

答：包含n-1个顶点的完全图和一个孤立顶点。边数为(n-1)(n-2)/2。

2、含n个顶点的强连通图最少要有几条边？

答：一个环，边数为n。