6 图

Wu Jun 2019-12-25 15:59:04
01 数据结构与算法 > 数据结构 > 01 数据结构

一、图的基本概念

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

1、各种图定义

2、图的顶点与边间关系

3、连通图相关术语

二、图的存储及基本操作

1、邻接矩阵:适合稠密图

邻接矩阵 (Adjacency Matrix)用两个数组来表示图:

设图 G 有 n 个顶点,则邻接矩阵是一个 n * n 的方阵,定义为 :

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

1)无向图

2)有向图

3)网

网的对应边或弧存权值

$arc[i][j] = \begin{cases} W_ij& \text{若}(v_i,v_j)\in E \text{或} <v_i,v_j>\in E\\ 0& \text{若}i = j\\ \infty& \text{反之} \end{cases}$

2、邻接表:适合稀疏图

邻接表(Adjacency List) 使用数组与链表相结合存储图

1)无向图

2)有向图

以顶点为弧尾来存储边表

有向图的逆邻接表:以顶点为弧头的边表

3)网

在边表结点定义中再增加一个 weight 的数据域,存储权值信息

3、十字链表:适合有向图

对于有向图来说,邻接表是有缺陷的。出度入度只能关心一个。

十字链表把邻接表与逆邻接表结合起来。

实线箭头指针的图示与邻接表相同。虚线箭头是逆邻接表的表示。

4、邻接多重表:适合处理无向图的边

ivex 和 jvex 是与某条边依附的两个顶点在顶点表中下标。ilink 指向依附顶点 ivex 的下一条边, jlink 指向依附顶点 jvex 的下一条边。这就是邻接多重表结构。

邻接多重表与邻接表的差别,仅仅是在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。

5、边集数组:适合对边依次处理

边集数组是由两个一维数组构成。一个是存储顶点的信息;另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标 (begin) 、终点下标 (end) 和权(weigbt) 组成

三、图的遍历

图的遍历(Traversing Grapb):从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次

1、深度优先搜索

深度优先遍历(Depth_First_Search),也有称为深度优先搜索,简称为 DFS。

类似于树的前序遍历,用数组记录访问:

  1. 访问初始结点v,并标记结点v为已访问。
  2. 查找结点v的第一个邻接结点w。
  3. 若w存在,则继续执行4,否则算法结束。
  4. 若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。
  5. 查找结点v的w邻接结点的下一个邻接结点,转到步骤3。

2、广度优先搜索

广度优先遍历 (Breadth.First.Search) ,又称为广度优先搜索,简称 BFS。

类似于树的分层遍历,用队列保持访问过的结点的顺序:

  1. 访问初始结点v并标记结点v为已访问。
  2. 结点v入队列
  3. 当队列非空时,继续执行,否则算法结束。
  4. 出队列,取得队头结点u。
  5. 查找结点u的第一个邻接结点w。
  6. 若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:
    1. 若结点w尚未被访问,则访问结点w并标记为已访问。
    2. 结点w入队列
    3. 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。

四、图的基本应用

1、最小(代价)生成树

最小生成树: 一个具有n个顶点的加权的无向连通图,用n-1条边连接这n个顶点,并且使得连接之后的所有边的权值之和最小的树。

1)普里姆 ( Prim )算法

  1. 将点分为两拨,已经加入最小生成树的,未加入的
  2. 找到未加入中距离集合最近的点,添加该点,修改其它点到集合的距离
  3. 直到所有结点都加入到最小生成树

2)克鲁斯卡尔( Kruskal )算法

  1. 现将所有边进行权值的从小到大排序
  2. 定义一个一维数组代表连接过的边,数组的下标为边的起点,值为边的终点
  3. 按照排好序的集合用边对顶点进行依次连接,连接的边则存放到一维数组中
  4. 用一维数组判断是否对已经连接的边能构成回路,有回路则无效,没回路则是一条有效边
  5. 重复3,4直至遍历完所有的边为止,即找到最小生成树

2、最短路径

对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点是源点,最后一个顶点是终点。

1)迪杰斯特拉( Dijkstra ) 算法

适用于求一个节点到其他节点的最短路径,通过广度搜索来遍历其他所有需要求距离的点。

  1. 选取初始节点作为一个集合,D(v)表示初始节点到V节点的最短路径
  2. 所有能直接到达V的节点路径记为 D(v)=距离,不能直接到达的节点路径记为 D(v)=无穷
  3. 选取 D(v) 最小的节点加入初始节点集合,最短路径记为D(w)=min(D(w),D(v)+j(v,w))(j(v,w)为节点V到W的距离)
  4. 重复步骤3,直到所有节点都加入初始节点集合

2)弗洛伊德( Floyd )算法

适用于求所有顶点至所有顶点的最短路径问题。

  1. 确定一个中间点
  2. 定义两个二维数组 D[][] 和 P[][]
    • D 代表顶点到顶点的最短路径权值和的矩阵,即点的邻接矩阵
    • P 代表对应顶点的最小路径的前驱矩阵
  3. 对于每一对顶点 v 和 w,看看是否存在一个顶点 u 使得从 v 到 u 再到 w 比己知的路径更短。如果是更新它
    $D^0[v][w] = min\{ D^{-1}[v][w], D^{-1}[v][0]+D^{-1}[0][w]\}$

3、拓扑排序

建立一个邻接表,在顶点表结点结构中,增加一个人度域 in

4、关键路径

关键路径算法
  1. 事件最早开始时间(etv):顶点$v_k$最早发生的时间。
  2. 事件最晚开始时间(ltv):顶点$v_k$最晚发生的时间,超出则会延误整个工期。
  3. 活动的最早开始时间(ete):弧$a_k$最早发生时间。
  4. 活动的最晚开始时间(lte):弧$a_k$最晚发生时间。不推迟工期的最晚开工时间。

由 1 和 2 可以求得 3 和 4 ,然后再根据 ete[k] 是否与 lte[k] 相等来判断$a_k$是 否是关键活动。

建立一个邻接表,弧链表增加了 weight 域,用来存储弧的权值。

如果是多条关键路径,则单是提高一条关键路径上的关键活动速度并不是能导致整个工程缩短工期、而必须提高同时在几条关键路径上的活动的速度。