算法学习-图

风尘

文章目录

  1. 1. 图的定义
    1. 1.1. 无向图
    2. 1.2. 有向图
  2. 2. 图的存储
    1. 2.1. 邻接矩阵
    2. 2.2. 邻接表
    3. 2.3. 十字链表
    4. 2.4. 邻接多重表
    5. 2.5. 边集数组

图的定义

在图中的数据元素称之为顶点(Vertex);任意两顶点之间可能存在关系,顶点间的关系叫做边(Edge)。在图结构中不允许没有顶点,因此图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成的数据结构,通常表示为:G(V,E)G(V,E) ,G 表示一个图,V 表示顶点集合,E 表示边集合。

图1|图2图1|图2

无向图

若顶点 VAV_AVBV_B 之间的边没有方向,则称这条边为无向边,用无序偶对 (VA,VB)(V_A,V_B) 来表示。当一个图中任意两顶点间的边都是无向边时,则称该图为无向图

如图1,由于没有方向顶点 A 和 B 的边可以表示 (A,B)(A,B),也可以写成 (B,A)(B,A)

G1=(V1,{E1})图:G_1=(V_1,\{E_1\})

V1={A,B,C,D}顶点集合:V_1=\{A,B,C,D\}

E1={(A,B),(A,C),(A,D),(B,C),(B,D)}边集合:E_1=\{(A,B),(A,C),(A,D),(B,C),(B,D)\}

  • 顶点与边的关系

    如果边 (v,v)E(v,v') \in E ,则称顶点 v 和 v’ 相邻接,即两顶点相关联。和顶点相关联的边的数量,称之为顶点的,记录 TD(v)TD(v)

    如图1,A 和 B 相联接,互为邻接点,顶点 A 的度为 3。

    通过观察发现图的边数,其实是各个顶点度数和的一半,多出的一半是因为重复记了两次。

有向图

若顶点 VAV_AVBV_B 之间的边有方向,则称这条边为有向边(也称为),用有序偶对 <VA,VB><V_A,V_B> 来表示,VAV_A 称为弧尾 (Tail),VBV_B 称为弧头 (Head)。

当一个图中任意两顶点间的边都是有向边时,则称该图为有向图

如图2,A 和 B 的边表示为 <A,B><A,B>,注意不能写成 <B,A><B,A>

G2=(V2,{E2})图:G_2=(V_2,\{E_2\})

V1={A,B,C,D}顶点集合:V_1=\{A,B,C,D\}

E1={<A,B>,<A,C>,(C,B),(B,D)}边集合:E_1=\{<A,B>,<A,C>,(C,B),(B,D)\}

  • 顶点与边的关系

    如果边 <v,v>E<v,v'> \in E ,则称顶点 v 邻接到顶点 v’。以顶点 v 为尾的边数量,称之为顶点的出度,记录 ID(v)ID(v) ; 反之以顶点 v 为头的边的数量,称之为顶点的入度,记录 OD(v)OD(v)

    如图2,顶点 B 的入度为 2 (从 A 到 B,从 C 到 B) ,出度为 1 (从 B 到 D),所以顶点 B 的度为 2+1 = 3。

    通过观察发现该图的边数与图的入度或出度数相等。

图的存储

邻接矩阵

图的邻接矩阵存储方式,采用两个数组来表示图。一个一维数组存储顶点信息,一个二维数组存储边信息。

arc[i][j]={1,(vi,vj)E<vi,vj>E0,arc[i][j]=\begin{cases} 1,若(v_i,v_j)\in E 或 <v_i,v_j> \in E \\0,反之\end{cases}

  • 根据图1的无向图,得到如下:

图3图3

矩阵的对角线值都为 0,因为不存在顶点到自身的边。

由于是无向图,所以边是对称的,即 A 到 B 存在边,意味着 B 到 A 也存在边,值为1。所以无向图的边数组矩阵是一个对称矩阵。

根据图3可得到的信息有:

1)可以判断任意两点是否存在边,即值为1有边,值为0无边。

2)顶点的度就是该顶点的第 i 行(或第 i 列)的元素之和。

3)顶点的邻接点,就是将第 i 行元素描述一遍,arc[i][j]为1就是邻接点。

  • 根据图2有向图,得到如下:

    图4图4

矩阵的对角线仍然为 0。

由于是有向图,所以矩阵不再对称,即 A 到 B 存值为 1,而 B 到 A 值为 0。

根据图4可得到的信息有:

1)顶点的出度值正好为顶点所在行的各数之和 。

2)顶点的入度值正好为顶点所在列的各数之和。

3)同无向图一样判断任意两点是否存在边,即值为 1 有边,值为 0 无边。

邻接表

邻接矩阵存储图的问题在于,当存储边数相较顶点来说较少的图时,邻接矩阵大多数值均为 0,此时这种结构浪费了大量存储空间。

针对顺序结构存在预先分配内存可能造成存储空间浪费问题,可以采用链式存储结构。这种数组与链表相结合的存储方法称为邻接表。

邻接表的存储结构如下:

​ 1)顶点用一个一维数组存储,数组中每个数据的元素内还需要存储指向第一个邻接点的指针,以便查找该顶点的边信息。

​ 2)每个顶点 viv_i 的所有邻接点构成一个线性表,由于邻接点数量不确定,所以采用间链表存储。无向图称为顶点 viv_i 的边表,有向图称为顶点 viv_i 的出边表。

  • 根据图1无向图,得到如下:

    图5图5

    ​ 图5中,顶点表的各个结点由 datafirstedge 两个域表示,其中 data 是数据域存,储顶点信息 ; firstedge 是指针域,指向边表的第一个邻接点。

    ​ 边表各结点由 adjvexnext 两个域组成,其中 adjvex 邻接点域,存储某顶点的邻接点在顶点表中的下标 ; next 存储指向边表中下一个结点的指针。

    如 C 顶点,与 A、B 互为邻接点,所以顶点 C 的边表中 adjvex 分别为 A、B 所对应的下标 0 和 1。

  • 根据图2有向图,得到如下:

    与无向图类似,但由于边是有方向,所以以顶点为尾来存储边表,这样可得到出度的邻接表。

    图6图6

    有时为了确定顶点的入度,可以以顶为点头来存储边表,这样可得到入度的邻接表,称之为逆邻接表

    图7图7

十字链表

对于有向图来说,邻接表是有缺陷的。建立出度邻接表时,想要获得入度就必须要遍历整个图,反之亦然。而十字链表法,解决了这个问题。

十字链表存储结构如下:

1)顶点表增加入边表头指针( firstin) 指向该顶点的入边表中的第一个结点 ; 出边表头指针( firstout)指向该顶点的出边表中的第一个结点。

2)边表增加弧的起点(出边顶点)在顶点表的坐标 (tailvex) 、弧的终点(入边顶点)在顶点表的坐标 (headvex) 和入边表指针域 (headlink)指向终点相同的下一条边、出边表指针域(taillink)指向起点相同的下一条边。

  • 根据图2有向图,得到如下:

    图8图8

    十字链表步骤解析:

    1)第一步画出邻接表,步骤完全相同, firstout为第一个邻接点指针,headvex 就是邻接表 adjvex 值 ; taillink 就是邻接表next值。

    2)根据图2可知,顶点 A 没有入边所以 firstin 为空,用 ^ 标识。

    3)顶点 B 第一个入边为 <A,B> 坐标为 (0,1) ,所以 firstin 指针指向图中的

    4)因为顶点 B 存在第二个入边 <C,B> 坐标为 (2,1) ,所以入边顶点的 headlink 指针继续向下指向图中的 。此时顶点 B 已经没有其他入边,所以该顶点的入边链表在此结点终止,将该结点的 headlink 标记为 ^

    5)同理顶点 CD 也能画出各自的入边链表,如图

    十字链表的优点就是把邻接表和逆邻表整合在了一起,从而更容易获得顶点的出度与入度,并且创建图的算法时间复杂度和邻接表相同。其缺点就是结构更加复杂。

邻接多重表

对于无向图,邻接表也存在一些问题。当关注的重点不是顶点而是边时,如图1,要删除 (A,B) 边,对应的邻接表需要删除下图图9灰色两个结点,比较烦琐。可以通过邻接多重表解决这个问题。

图9图9

邻接多重表存储结构:

1)顶点表保持不变

2)边表增加 ivexilinkjvexjlink,其中 ivexjvex 是某条边的两个顶点在顶点表中的下标 ; ilink 指向顶点 ivex 的下一条边,jlink 指向顶点 jvex 的下一条边。

  • 根据图1无向图,得到如下:

    图10图10

    邻接多重表步骤解析:

    1)先画出顶点表的 4 个顶点和 5 条边。因为是无向边,所以 ivexjvex 可以是两个顶点中的任意一个。如 (A,B) 边,无论 ivex 为 0 、jvex 为 1,还是反过来都可以,一般为了规范,通常都将 ivex 值与左侧顶点下标相同。

    2)首先连线 ①②③④ ,就是将顶点指向一条边。

    3)顶点 A(vA,vB)(v_A,v_B) 边的邻边有 (vA,vC)(vA,vD)(v_A,v_C)和(v_A,v_D) ,因此步骤 中的 ilink 指向顶点 ivex 的下一条边 (vA,vC)(v_A,v_C) 坐标为 (0,2) 因为是无向边,所以指向的也就是边 (vC,vA)(v_C,v_A) 坐标 (2,0)

    4)继续链接指向顶点 jvexjlink ,即指向顶点 jvex 的下一条边,此处是 (vA,vD)(v_A,v_D) 坐标为 (0,3) 见步骤

    5)同上一步,继续链接指向顶点 jvexjlink,此时发现顶点 jvex 即顶点 A 不存在其他边了,所以为空,将 jlink 标记为 ^

    6)顶点 A 链接完成,重复上述 2-5 步,继续链接顶点 BCD

    注意 ilink 所指向的结点 jvex 一定要和它本身的 ivex 值相同。

    由此可见,邻接多重表与邻接表的区别,仅仅是在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。若要删除 (A,B) 边时,只需要将 的链接指向改为 ^ 即可。

边集数组

边集数组是由两个一维数组组成构成。一个存储顶点的信息 ; 另一个存储边信息。边数组每个数据元素由一条边的起点下标 (begin)、终点下标 (end) 和权重 (weight)组成,没有权重可以省略。

  • 根据图2有向图,得到如下:

    图11图11

边集数组是边的集合,在边集数组中要查找一个顶点的度,需要遍历整个数组,效率不高。因此它更适合对边依次进行处理的操作,而不适合对顶点的操作。