【霍罗维兹数据结构】GRAPH 图 | 基本图运算 DFS&BFS | 最小代价生成树

Ⅰ. 图的抽象数据类型 - THE GRAPH ABSTRACT DATA TYPE

0x00 引入：七桥问题

概念：最早可追溯到1736年，欧拉用图论解决了经典的七桥问题。

欧拉证明，如果要从图中的一个节点除法，经图中所有边一次且仅一次，最后回到出发的节点，那么当且仅当图中所有节点的度都是偶数。为了纪念欧拉的发现，我们称之为欧拉回路。

图是使用最广泛的数学结构，可应用于电路分析、寻找最短路径、项目规划、化合物鉴定、网络流程设计、基因/蛋白质相互作用等……

0x01 图的定义

一个图由两个集合构成：

：有限的、非空的顶点集合， ：有限的、可能是空的边缘集合。

我们可以将其写作   .

An undirected graph：each edge is represented as an unordered pair of vertices.

无向图的节点二元组是无序二元组   eg.   和  表示同一条边。

A directed graph -- each edge is represented as a directed pair of vertices.

有向图的边是有序的节点二元组，用 表示， 是边尾， 是边头。 eg. 与 是两条不同的边。

这些图的集合表示为：

注意，有向图在边头标出箭头。 是树，我们可以将树定义为图的一种特例 （ 不是树）

① No self loops：

图中不允许存在由节点 发出而只想自己的边，即不允许存在 的情况。

也就是说 不是图的合法边，这样的边我们称之为 环边 。

② No multiple edges：

图中一般不重复出现同一条边，如果允许重复出现，那么这样的图称为 重复边图（multigraph）

Complete graph：

对于无向图，一个有 个顶点的完整图有 条不同的边。

对于有向图，一个有 个顶点的完整图有 条不同的边。

一个有向图是强连通的（strongly connected），如果 中的每一对不同的顶点，都有一条从 到 和 到  的有向路径。

A strongly connected component is a maximal subgraph which is strongly connected.

强连通分量是有向图中的最大强连通子图。

一个顶点的度是与该顶点相关的边的数量。

对于一个有向图，我们将一个顶点 的内度（in-degree）定义为以 为首的边的数量，而一个顶点 的外度（out-degree）定义为以 为尾的边的数量。

如果 是一个有 个顶点和 条边的图 中顶点 的度数，那么边的数量为：

0x02 图的ADT

Ⅱ. 图的表示

0x00 邻接矩阵 - Adjacency Matrix

令 为一个具有 个顶点的图，

的邻接矩阵为一个 的二维数组，比如 adj_mat，定义为：

adj_mat[i][j] = 1    if the edge ( , ) is in E(G)
                0    if there is no such edge.

这样的定义也可以用于有向图，只是 是有向的。

无向图的邻接矩阵是对称的，因为边 在 中，则边 也在 中。

对于无定向图，我们可以通过只存储矩阵的上三角或下三角来节省空间。

有些问题或任务要求我们（可能）检查图的所有边，例如G中有多少条边？或者G 是否连通？

使用邻接矩阵，所有回答这些问题的算法都需要至少 的时间。

因为我们必须检查矩阵的 个条目来确定图的边。

对于稀疏图，其邻接矩阵变得稀疏。

我们可能期望上述问题可以在更短的时间内得到解答，比如 时间。

0x01 邻接表 - Adjacency Lists

在这个表示中，我们将邻接矩阵的 n 行替换为 n 个链表，每个链表对应 G 中的每个顶点。

💬 The C declaration for the adjacency list representation：

#define MAX_VERTICES 50 /*maximum number of vertices*/
typedef struct node* node_pointer;
typedef struct node {
  int vertex;
  node_pointer link;
};
node_pointer graph[MAX_VERTICES];
int n = 0; /* vertices currently in use */

对于具有 n 个顶点和 e 个边的无向图，这种表示需要 n 个头节点和 2e 个列表节点。每个列表节点有两个字段。

确定任意顶点的度数， ，等价于入射在顶点上的边数。

我们可以在 的时间 ，确定 G 中的总边数。

对于有向图，我们可以很容易地确定出度，但找到入度更复杂。

（Weighted Edges Need to modify our representations）

Ⅲ. 基本图运算 - ELEMENTARY GRAPH OPERATIONS

0x00 引入

给定一个无向图 G = (V, E) 和 V(G) 中的一个顶点 v，

我们希望访问 G 中从 v 可达的所有顶点，即所有连接到 v 的顶点。

Depth First Search （DFS）

Breadth First Search （BFS）

0x01 Depth First Search

我们首先访问起始顶点 v。接下来，我们从 v 的邻接列表中选择一个未访问的顶点 w，

并对 w 进行深度优先搜索。我们通过将 v 的邻接列表放置在栈上来保留当前位置。

最终，我们的搜索到达一个顶点 u，它的邻接列表中没有未访问的顶点。

此时，我们从堆栈中删除一个顶点并继续处理它的邻接表。

以前访问过的顶点被丢弃；访问未访问的顶点并将其放置在堆栈上。当栈为空时搜索结束。

📜 需要的申明：

#define FALSE 0
#define TRUE 1
short int visited[MAX_VERTICES];

💬 [Program 6.1] : Depth first search

void dfs(int v)
{
  /* depth first search of a graph beginning with vertex v. */
  node_pointer w;
  visited[v] = TRUE;
  printf("%5d", v);
  for (w = graph[v]; w; w = w->link)
    if (!visited[w->vertex])
      dfs(w->vertex);
}

分析：如果我们使用邻接表，由于 dfs 对邻接表中的每个节点最多检查一次，所以完成搜索的时间是 。如果我们使用邻接矩阵，那么确定与 v 相邻的所有顶点需要 时间。由于我们最多访问 n 个顶点，因此总时间为 。

0x02 Breadth First Search

从顶点开始并将其标记为已访问。然后它访问 v 的邻接表上的每个顶点。

当我们访问了 v 的邻接表上的所有顶点后，访问与 v 的邻接表上的第一个顶点相邻的所有未访问的顶点。为了实现这个方案，当我们访问每个顶点时，我们将顶点放入队列中。

当我们用完一个邻接列表时，我们从队列中删除一个顶点并继续检查其邻接列表上的每个顶点。未访问的顶点被访问，然后放入队列；访问的顶点被忽略。当队列为空时搜索结束。

为了实现广度优先搜索，我们使用动态链接队列。

📜 需要的申明：

typedef struct queue* queue_pointer;
typedef struct queue {
  int vertex;
  queue_pointer link;
};
void addq(queue_pointer*, queue_pointer*, int);
int deleteq(queue_pointer*);

💬 [program 6.2] : Breadth first search

void bfs(int v)
{
  /* breadth first traversal of a graph, staring with node v.
  the global array visited is initialized to 0, the queue
  operations are similar to those described in Chapter 4. */
  node_pointer w;
  queue_pointer front, rear;
  front = rear = NULL; /* initialize queue */
  printf("%5d", v);
  visited[v] = TRUE;
  addq(&front, &rear, v);
  while (front) {
    v = deleteq(&front);
    for (w = graph[v]; w; w = w->link)
      if (!visited[w->vertex]) {
        printf("%5d", w->vertex);
        addq(&front, &rear, w->vertex);
        visited[w->vertex] = TRUE;
      }
  }
}

分析：由于每个顶点在队列中只放置一次，所以 while 循环最多迭代 n 次。对于邻接表表示，这个循环的总成本为 ，其中 。对于邻接矩阵表示，while 循环需要 次访问每个顶点。因此，总时间为 。

0x03 连通分量 - Connected Components

注意，在深度优先搜索和广度优先搜索中，所有访问过的顶点，

连同所有与它们相关的边，形成 G 的连通分量。此属性允许我们确定有向图是否连通。

只需调用 dfs(0) 或 bfs(0) ，然后确定是否有任何未访问的顶点。

如果使用邻接表，这需要 O(n+e) 时间。一个密切相关的问题是列出连接的组件。

💬 [Program 6.3] : Connected components

void connected(void)
{
  /* determine the connected components
  of a graph */
  int i;
  for (i = 0; i < n; i++)
    if (!visited[i]) {
      dfs(i);
      printf("\n");
    }
}

分析：如果G用它的邻接表来表示，那么dfs所用的总时间是 。由于 for 循环需要   时间，因此生成所有连接组件所需的总时间是   。如果 G 由其邻接矩阵表示，则确定连通分量所需的时间为 。

0x04 生成树 - Spanning Trees

当 G 连接时，从任何顶点开始的深度优先搜索或广度优先搜索访问 G 中的所有顶点。

搜索隐式地将 G 中的边分成两组：

T（对于树边）是在搜索期间使用或遍历的边的集合，

N（对于非树边）是剩余边的集合。

T 中的边形成一棵包含 G 的所有顶点的树。

生成树是仅由 G 中的边组成并包含 G 中的所有顶点的任何树。

我们可以使用 dfs 或 bfs 来创建生成树；深度优先生成树广度优先生成树。

如果我们将一条非树边 (v,w) 添加到任何生成树 T 中，

它会创建一个由边 (v,w) 和 T 中从 w 到 v 的路径上的所有边组成的循环。

生成树的另一个性质：生成树是 G 的最小子图 G'，使得 V(G')= V(G) 且 G' 是连通的。

任何具有 n 个顶点的连通图必须至少有 n-1 条边，并且所有具有 n-1 条边的连通图都是树。

因此，生成树有 n-1 条边。构造最小子图在通信网络的设计中经常得到应用。

0x05 重连通分量 - Biconnected Components and Articulation Points

对于无向连通图 G，关节点是 G 的一个顶点 v，这样删除 v 以及所有入射到 v 上的边，

生成一个图 G，该图 G 至少具有两个连通分量。双连通图是没有连接点的连通图。

在许多图形应用程序中，关节点是不可取的。连通无向图的双连通分量是 G 的最大双连通子图 H。很容易验证同一个图的两个双连通分量的公共顶点不超过一个。这意味着没有边可以位于图的两个或多个双连通分量中。因此，G 的双连通分量划分了 G 的边。

通过使用 G 的深度优先生成树来查找连通无向图 G 的双连通分量：

我们按照在深度优先搜索期间访问顶点的顺序对顶点进行编号。我们将此数字称为顶点的深度优先数或 dfn。如果 u 和 v 是两个顶点，并且 u 是深度优先生成树中 v 的祖先，则 dfn(u) < dfn(v)。非树边 (u,v) 是后边当且仅当 u 是 v 的祖先或 v 是 u 的祖先。

根据深度优先搜索的定义，所有非树边都是后边。这意味着深度优先生成树的根是一个关节点，如果它至少有两个孩子。此外，任何其他顶点 u 是一个连接点，当且仅当它具有至少一个子 w 使得我们无法使用仅由 w、w 的后代和单个后边组成的路径到达 u 的祖先。这些观察导致我们为 G 的每个顶点定义一个值 low ，使得 low(u) 是我们可以从 u 到达的最低 dfn ，使用后代路径后跟最多一个后边缘：

low(u) = min{ dfn(u), min{low(w) | w is a child of u},
min{dfn(w) | (u,w) is a back edge} }

因此，我们可以说 u 是一个关节点，当且仅当 u 是生成树的根并且有两个或多个孩子，或者 u 不是根并且有一个孩子 w 使得

我们可以轻松地修改 dfs 以计算连接无向图的每个顶点的 dfn 和 low。见程序 6.4。它的初始调用是 dfnlow(x,-1)，其中 x 是深度优先搜索的起始顶点。在该程序中，我们使用宏 MIN2 和全局变量 dfn、low 和 num。函数 init（程序 6.5）包含正确初始化 dfn、low 和 num 的代码。

📜 需要的申明：

#define MIN2(x,y) ((x) < (y) ? (x) : (y))
short int dfn[MAX_VERTICES];
short int low[MAX_VERTICES];
int num;

💬 [Program 6.5] Initialization of dfn and low

void dfnlow(int u, int v)
{
  /* compute dfn and low while performing a dfs search
  beginning at vertex u, v is the parent of u (if any) */
  node_pointer ptr;
  int w;
  dfn[u] = low[u] = num++;
  for (ptr = graph[u]; ptr; ptr = ptr->link) {
    w = ptr->vertex;
    if (dfn[w] < 0) { /* w is an unvisited vertex */
      dfnlow(w, u);
      low[u] = MIN2(low[u], low[w]);
    }
    else if (w != v)
      low[u] = MIN2(low[u], dfn[w]);
  }
}

如果低[w] dfn[u]，那么我们已经确定了一个新的双连通分量。如果我们在第一次遇到边时使用堆栈来保存边，我们可以输出双连接组件中的所有边。见程序 6.6。它的初始调用是 bicon(x, -1)，其中 x 是生成树的根。使用相同的初始化函数（程序 6.5）。

💬 [Program 6.6] Biconnected components of a graph

void bicon(int u, int v)
{
  node_pointer ptr;
  int w, x, y;
  dfn[u] = low[u] = num++;
  for (ptr = graph[u]; ptr; ptr = ptr->link) {
    w = ptr->vertex;
    if (v != w && dfn[w] < dfn[u])
      add(&top, u, w); /* add edge to stack */
    if (dfn[w] < 0) { /* w is an unvisited vertex */
      bicon(w, u);
      low[u] = MIN2(low[u], low[w]);
      if (low[w] >= dfn[u]) {
        printf("New biconnected component: ");
        do { /* delete edge from stack */
          delete(&top, &x, &y);
          printf(“ <% d, % d>”, x, y);
        } while (!((x == u) && (y == w)));
        printf("\n");
      }
    }
    else if (w != v) low[u] = MIN2(low[u], dfn[w]);
  }
}

分析：函数bicon假设连通图至少有两个顶点。 bicon 的时间复杂度是 。

Ⅳ. 最小代價生成樹 - MINIMUM COST SPANNING TREES

0x00 引入

加权无向图的生成树的成本是生成树中边的成本（权重）的总和。

最小成本生成树是成本最低的生成树。

三种贪心算法： 算法、 算法、 算法。

在贪心中，我们分阶段构造最优解。

在每个阶段，我们都会做出一个目前最好的决定（使用一些标准）。

由于我们以后无法更改此决定，因此我们确保该决定将导致可行的解决方案。

通常，每个阶段的项目选择基于最低成本或最高利润标准。

可行的解决方案是在问题指定的约束范围内工作的解决方案。

对于生成树，我们使用最低成本标准。我们的解决方案必须满足以下约束：

（1）只选图中出现的边

（2）只选 条边

（3）不选构成环路的边

0x01 克鲁斯卡尔算法 - Kruskal's Algorithm

的算法通过一次向 T 中添加一条边来构建最小成本生成树 T。

该算法以成本的非递减顺序选择包含在 T 中的边。如果一条边没有与 T 中的边形成一个循环，

则将一条边添加到 T。如果 G 是连通的并且顶点 n > 0，则恰好 n-1 条边将被选择包含在 T 中。

💬 [Program 6.7] Kruskal's algorithm

T = {};
while (T contains less than n - 1 edges && E is not empty) {
  choose a least cost edge(v, w) from E;
  delete (v, w) from E;
  if ((v, w) does not create a cycle in T)
    add(v, w) to T;
  else
    discard(v, w);
}
if (T contains fewer than n - 1 edges)
printf("No spanning tree\n");

实施：如何以最低成本确定一条边并删除该边？排序或使用最小堆。如何检查新边 (v,w) 是否在 T 中不形成循环？我们可以使用 5.10 节中的 union-find 操作。

Kruskal 算法的计算时间为 。

【定理】令G是无向连接图， 算法给出G的最小代价生成树。

0x02 普利姆算法 - Prim's algorithm

Prim 的算法 Prim 的算法与 Kruskal 的算法一样，一次构造一条边的最小成本生成树。

然而，在每个阶段，一组选定的边形成一棵树。 Prim 的算法从包含单个顶点的树 T 开始。

这可以是任何顶点。接下来，我们将最小成本边 (u,v) 添加到 T 使得 T U {(u,v)} 也是一棵树。

我们重复这个边添加步骤，直到 T 包含 n-1 条边。为了确保添加的边不形成循环，

在每一步我们选择边 (u,v)，使得 T 中的 u 或 v 恰好其中一个。

💬 [Program 6.8]: Prim's algorithm

T = {};
TV = { 0 }; /* start with vertex 0 and no edges */
while (T contains fewer than n - 1 edges) {
  let(u, v) be a least cost edge such that
    u ∈ TVand v TV;
  if (there is no such edge)
    break;
  add v to TV;
  add(u, v) to T;
}
if (T contains fewer than n - 1 edges)
printf("No spanning tree\n");

实现：对于不在 TV 中的每个顶点 v，我们保留一个伴生顶点 near(v)，使得 near(v) ∈TV 和 cost(near(v), v) 在所有这些选项中为 near(v) 的最小值.计算时间为 ，其中 n 是 G 中的顶点数。

0x03 索林算法 - Sollin's Algorithm

Sollin 算法与 Kruskal 和 Prim 算法不同，Sollin 算法在每个阶段选择几条边包含在 T 中。

在阶段开始时，选定的边与所有 n 个图顶点一起形成一个生成森林。

在一个阶段，我们为森林中的每棵树选择一条边。该边是最小成本边，在树中只有一个顶点。

在第一阶段开始时，选定边的集合是空的。当阶段结束时只有一棵树或没有边可供选择时，该算法终止。

0x04 最短路径和迁移闭包 - Shortest Paths and Transitive Closure

假设我们有一个表示高速公路系统的图表。在该图中，顶点代表城市，边代表高速公路的路段。

每条边都有一个权重，表示由边连接的两个城市之间的距离。

问题（来自一位希望从 A 市开车到 B 市的驾车者）：

(1) 是否有从 A 市到 B 市的路径？

(2) 如果从 A 到 B 有多条路径，哪条路径最短？

我们将路径的长度定义为该路径上边的权重之和。我们假设有向图。

0x05 单源点至所有其他节点：边权值非负 - Single Source All Destinations: Nonnegative Edge Costs

给定有向图 G=(V, E)，权重函数 w(e)，w(e) > 0，用于 G 的边，以及源顶点 v0。我们希望确定从 v0 到 G 的每个剩余顶点的最短路径。

我们可以使用贪心算法以长度的非递减顺序生成最短路径。

令 S 为已找到最短路径的顶点集，包括 v0 。对于不在 S 中的 w，令 distance[w] 为从 v0 开始，

仅通过 S 中的顶点，并以 w 结束的最短路径的长度。

观察：

(1) 如果下一条最短路径是到顶点 u，那么从 v0 到 u 的路径只经过 S 中的那些顶点。

(2) 选择顶点 u，使其具有最小距离，distance[u ]，在所有不在 S 中的顶点中。

(3) 一旦我们选择了 u 并生成了从 v0 到 u 的最短路径，u 就成为了 S 的成员。

将 u 添加到 S 可以改变从 v0 开始的最短路径的距离，仅通过 S 中的顶点，并在当前不在 S 中的顶点 w 处结束。

0x06 实现 Dijkstra 算法 - Implementing Dijkstra’s algorithm

假设n个顶点从0到n-1编号。将集合 S 保持为一个数组，found，如果顶点 i 不在 S 中，

则 found[i] = FALSE，如果顶点 i 在 S 中，则 found[i] = TRUE。图由其成本邻接矩阵表示，

其中 cost[i ][j] 是边 <i,j> 的权重。如果边 <i,j> 不在 G 中，我们将 cost[i][j] 设置为某个大数。

这个数字的选择是任意的，但是我们做了两个规定：

（1）这个数字必须大于成本矩阵中的任何一个值。

 (2) 必须选择数字以便距离[u] + cost[u][w] 不会产生溢出到符号位。

💬 Program 6.9 : Declarations for the shortest path algorithm

#define MAX_VERTICES 6 /* maximum number of vertices*/
int cost[][MAX_VERTICES] =
        { { 0, 50, 10, 1000, 45, 1000},
        { 1000, 0, 15, 1000, 10, 1000},
        { 20, 1000, 0, 15, 1000, 1000},
        { 1000, 20, 1000, 0, 35, 1000},
        { 1000, 1000, 30, 1000, 0, 1000},
        { 1000, 1000, 1000, 3, 1000, 0} };
int distance[MAX_VERTICES];
short int found[MAX_VERTICES];
int n = MAX_VERTICES;

💬 Program 6.10 : Single source shortest paths

void shortestpath (
  int v, 
  int cost[][MAX_VERTICES],
  int distance[], 
  int n, short int found[]
  )
{
  /* distance[i] represents the shortest path from vertex v to i,
  found[i] holds a 0 if the shortest path from vertex i has not
  been found and a 1 if it has. cost is the adjacency matrix */
  int i, u, w;
  for (i = 0; i < n; i++) {
    found[i] = FALSE;
    distance[i] = cost[v][i];
  }
  found[v] = TRUE;
  distance[v] = 0;
  for (i = 0; i < n - 2; i++) {
    u = choose(distance, n, found);
    found[u] = TRUE;
    for (w = 0; w < n; w++)
      if (!found[w])
        if (distance[u] + cost[u][w] < distance[w])
          distance[w] = distance[u] + cost[u][w];
  }
}
int choose(int distance[], int n, short int found[])
{
  /* find the smallest distance not yet checked */
  int i, min, minpos;
  min = INT_MAX;
  minpos = -1;
  for (i = 0; i < n; i++)
    if (distance[i] < min && !found[i]) {
      min = distance[i];
      minpos = i;
    }
  return minpos;
}

分析：

0x07 所有节点两两之间的最短路径 - Single Source All Destinations: General Weights

Dijkstra 算法不适用于具有负权重的图（例如图 6.29）

Bellman-Ford 算法解决了这个问题（没有负长度的循环）

观察： 1. 如果从 v 到 u 的最短路径最多 k，k>1，则边不超过 k-1 条边，

那么 2. 如果从 v 到 u 的最短路径最多 k，k>1 ，边正好有 k 条边，

那么它由一条从 v 到某个顶点 j 的最短路径，然后是边 <j,u> 组成。

从 v 到 j 的路径有 k-1 条边，长度为 。所有顶点 i 使得边 <i,u> 在图中是 j 的候选者。

由于我们对最短路径感兴趣，因此最小化的 i 是 j 的正确值。

💬 Bellman-Ford Algorithm

void BellmanFord(int n, int v)
{ // single source all destination shortest paths with
// negative edge lengths
  for (int i = 0; i < n; i++)
    dist[i] = length[v][i]; // initialize dist
  for (int k = 2; k <= n - 1; k++)
    for (each u such that u != v and u has at least one
      incoming edge)
      for (each <i, u> in the graph)
        if (dist[u] > dist[i] + length[i][u])
          dist[u] = dist[i] + length[i][u];
}

时间复杂度： 与邻接矩阵， 与 list.

所有对最短路径，我们希望找到所有顶点对之间的最短路径，

我们可以使用以 V(G) 中的每个顶点为源的最短路径来解决这个问题。

所需的总时间为 。然而，我们可以获得一个概念上更简单的算法，即使 G 中的某些边具有负权重也能正常工作。 （我们确实要求 G 没有负长度的环。）

动态规划方法。虽然这个算法仍然有 的计算时间，但它有一个更小的常数因子

我们用它的成本邻接矩阵来表示图 G。令   为从 i 到 j 的最短路径的成本，

仅使用索引为 k 的那些中间顶点。 是从 i 到 j 的最短路径的成本。

。所有对算法的基本思想是从矩阵 开始.

并依次生成矩阵 .

如果我们已经生成了  ，那么我们可以通过意识到对于任何一对顶点 i 、 j 都适用以下两条规则之一来生成 Ak。

(1) i 到 j 不经过索引大于 k 的顶点的最短路径不经过索引为 k 的顶点，因此它的成本是

(2) 最短路径经过顶点 k 。这样的路径包括从 i 到 k 的路径，然后是从 k 到 j 的路径。

这些规则产生如下公式：

并且 .

Example 6.5: Look at A1 [0][2]

函数 allcosts 计算 。使用数组 distance 就地完成计算。

注意： 和 .

💬 Program 6.12 : All pairs, shortest paths function

void allcosts(int cost[][MAX_VERTICES],
  int distance[][MAX_VERTICES], int n)
{ /* determine the distances from each vertex to every other vertex, cost is
the adjacency matrix, distance is the matrix of the distances. */
  int i, j, k;
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      distance[i][j] = cost[i][j];
  for (k = 0; k < n; k++)
    for (i = 0; i < n; i++)
      for (j = 0; j < n; j++)
        if (distance[i][k] + distance[k][j] < distance[i][j])
          distance[i][j] = distance[i][k] + distance[k][j];
}

对于 allcosts 的分析：

参考资料

Fundamentals of Data Structures in C