数据结构与算法基础八:图

一:图的概念
1.定义
图由有限非空的顶点集合与顶点之间有限的边的集合组成,通常表示为G(V,E),G是图,V是顶点集合,E是边集合.
数据就是顶点,边就是逻辑关系.

2.概念

• 无向: 如果一个图的边都是无向的,那么称为无向图,无向边表示为(A,D),下左图为无向图表示为G1 = (V1,{E1});
  其中V1 = {A,B,C,D},E1 = {(A,B),(B,C),(C,D),(D,A),(A,C)}

• 有向:如果一个图的边都是有向的,那么称为有向图,有向边也称为弧(Arc),表示为<A,D>,A是弧尾,D是弧头,下右图为有向图表示为G2 = (V2,{E2}),其中V2 = {A,B,C,D},E2 = {<A,D>,<B,A>,<C,A>,<B,C>}.

  
  无向图和有向图

在无向图中,任意两个顶点都有边的话,叫做完全无向图,n个顶点共有n*(n-1)/2条边.

完全无向图

在有向图中,任意两个顶点之间都有两条方向相反的边,成为完全有向图,n个顶点共有n*(n-1)条边.

完全有向图

图也可以带权,此时权是边的一种量化,带权的图叫做网.

网

与树一样,图也可以有子图

子图

对于无向图G = (V,{E}),如果(v,v1) ∈ E,也就是说存在(v,v1)这条边,则成v和v1为邻接点,顶点的度是存在邻接点的数量,也是与顶点相关的边的数量.边数 = 顶点的度之和 / 2;
对于有向图G = (V,{E}),如果(v,v1) ∈ E,则v邻接到v1,v1邻接自v,以v为头的弧数成为v的入度,记为ID(v),ID为InDegree;以v为尾的弧数成为v的出度,记为OD(v),OD为OutDegree;顶点v的度TD = ID + OD.

对于无向图,两个顶点之间边的序列叫做路径(Path),可能会有多种路径.

从B到D的四种路径

对于有向图,路径也是有方向的,因此下图中A到B不存在路径.

从B到D的路径

起点和终点一样的路径叫做环(Circle),不出现重复顶点的环叫做简单环.

左边是简单环,右边不是

对于无向图,如果两个顶点之间有路径,则成为连通,如果任意两个顶点都是连通的,则称为连通图;

右边是连通图,左边不是

连通分量:
a.是子图
b.子图需要是连通的
c.子图占到了最大连通数,也就是说能连的全连上
结合上图,如果上图左是原图,右边是和下面两个都是子图,那么根据条件,上图右边的ABCD和下图左边的EF是连通分量,而ABC不是.

左边是连通分量,右边不是

对于有向图:
a.弱连通：有向图的底图（无向图）是连通图，则是弱连通图.
b.单向连通：有向图中，任意结点对中，至少从一个到另一个是可达的，就是单向连通.
c.强连通：有向图中，强连通图是任意对中都互相可达.

注意三种情况是包含关系
三种有向连通图

连通图的生成树:
首先需要包含全部的n个顶点,然后有n-1条边,并且此时它仍然是连通的,则叫做这个连通图的生成树.

1是连通图,2和3是生成树,4不是

对于有向图连通图:
a.有且仅有一个结点的入度为0;
b.除树根外的结点入度为1;
c.从树根到任一结点有一条有向通路;
则称为有向树.