八、图(一)、基本概念

2020-07-03 本文已影响0人默默_David

数据结构目录

一、定义

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

图形结构

对于图的定义，我们需要明确几个注意的地方:

线性表中我们把数据元素叫元素，树中叫结点，在图中数据元素我们则称之为顶点(Vertex)
线性表可以没有数据元素，成为空表，树中可以没有结点，叫做空树，而图结构在国内大部分教材中强调顶点集合V要有穷非空
线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图结构中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边(Edge)，用无序偶(Vi,Vj)来表示。

无向边

如上图所示，图G1是一个无向图，G1={V1,E1},其中
V1 = {A,B,C,D}
E1 = {(A,B),(B,C),(C,D),(D,A),(A,C)}

有向边:若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧(Arc)，用有序偶<Vi,Vj>来表示，Vi称为弧尾，Vj称为弧头。

有向边
如上图所示，图G2是一个有向图，G2={V2,E2},其中
V2={A,B,C,D}
E2={<B,A>,<B,C>,<C,A>,<A,D>}

二、各种特殊的图

1.简单图

在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。
如下图所示，下图两个都不是简单图

非简单图

2.无向完全图

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

无向完全图

3.有向完全图

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

有向完全图

4.稀疏图和稠密图

这里稀疏和稠密是模糊的概念，都是相对而言的，通常认为边或弧度小于n*logn(n是顶点的个数)的图称为稀疏图，反之称为稠密图

5.权、网

有些图的边或者弧带有与它相关的数字，这种与图的边或弧相关的数叫做权(Weight)，带权的图通常称为网(Network)

权和网

6.子图

假设有两个图G1={V1,E1},G2={V2,E2},如果V2⊆V1，E2⊆E1,则称G2为G1的子图。

左边为图，右边为它的子图

三、图的顶点与边之间的关系

对于无向图G=(V,E)，如果边(V1,V2)∈E，则称顶点V1和V2互为邻接点(Adjacent)，即V1和V2相邻接。边(V1,V2)依附(incident)于顶点V1和V2，或者说边(V1,V2)与顶点V1和V2相关联。
顶点V的度(Degree)是和V相关联的边的数目，记为TD(V)，如下图，顶点A与B互为邻接点，边(A,B)依附于顶点A与B上，顶点A的度为3。

图

对于有向图G=(V,E)，如果有<V1,V2>∈E，则称顶点V1邻接到顶点V2，顶点V2邻接自顶点V1。
以顶点V为头的弧的数目称为V的入度(InDegree)，记为ID(V)，以V为尾的弧的数目称为V的出度(OutDegree)，记为OD(V)，因此顶点V的度为TD(V)=ID(V)+OD(V)。
下图顶点A的入度是2，出度是1，所以顶点A的度是3