C#图表算法之无向图
时间：2022-11-06 09:22:27 | 栏目：.NET代码 | 点击：次
图是由一组顶点和一组能够将两个顶点相连的边组成。
顶点叫什么名字并不重要，但我们需要一个方法来指代这些顶点。一般使用 0 至 V-1 来表示一张含有 V 个顶点的图中的各个顶点。这样约定是为了方便使用数组的索引来编写能够高效访问各个顶点信息的代码。用一张符号表来为顶点的名字和 0 到 V-1 的整数值建立一一对应的关系并不困难，因此直接使用数组索引作为结点的名称更方便且不失一般性，也不会损失什么效率。
我们用 v-w 的记法来表示连接 v 和 w 的边， w-v 是这条边的另一种表示方法。
在绘制一幅图时，用圆圈表示顶点，用连接两个顶点的线段表示边，这样就能直观地看出图地结构。但这种直觉有时可能会误导我们，因为图地定义和绘制地图像是无关的，一组数据可以绘制不同形态的图像。
特殊的图
自环：即一条连接一个顶点和其自身的边；
多重图：连接同一对顶点的两条边成为平行边，含有平行边的图称为多重图。
没有平行边的图称为简单图。
1.相关术语
当两个顶点通过一条边相连时，称这两个顶点是相邻得，并称这条边依附于这两个顶点。某个顶点的度数即为依附于它的边的总数。子图是由一幅图的所有边的一个子集（以及它们所依附的所有顶点）组成的图。许多计算问题都需要识别各种类型的子图，特别是由能够顺序连接一系列顶点的边所组成的子图。
在图中，路径是由边顺序连接的一系列顶点。简单路径是一条没有重复顶点的路径。环是一条至少含有一条边且起点和终点相同的路径。简单环是一条（除了起点和终点必须相同之外）不含有重复顶点和边的环。路径或环的长度为其中所包含的边数。
当两个顶点之间存在一条连接双方的路径时，我们称一个顶点和另一个顶点是连通的。
如果从任意一个顶点都存在一条路径到达另一个任意顶点，我们称这副图是连通图。一幅非连通的图由若干连通的部分组成，它们都是其极大连通子图。
一般来说，要处理一张图需要一个个地处理它的连通分量（子图）。
树是一幅无环连通图。互不相连的树组成的集合称为森林。连通图的生成树是它的一幅子图，它含有图中的所有顶点且是一棵树。图的生成森林是它的所有连通子图的生成树的集合。
树的定义非常通用，稍作改动就可以变成用来描述程序行为（函数调用层次）模型和数据结构。当且仅当一幅含有 V 个结点的图 G 满足下列 5 个条件之一时，它就是一棵树：
- G 有 V - 1 条边且不含有环；
- G 有 V - 1 条边且是连通的；
- G 是连通的，但删除任意一条都会使它不再连通；
- G 是无环图，但添加任意一条边都会产生一条环；
- G 中的任意一对顶点之间仅存在一条简单路径；
图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例。在稀疏图中，被连接的顶点对很少；而在稠密图中，只有少部分顶点对之间没有边连接。一般来说，如果一幅图中不同的边的数量在顶点总数 v 的一个小的常数倍以内，那么我们认为这幅图是稀疏的，否则就是稠密的。
二分图是一种能够将所有结点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的集合。
2.表示无向图的数据结构
图的几种表示方法
接下来要面对的图处理问题就是用哪种数据结构来表示图并实现这份API，包含下面两个要求：
- 1.必须为可能在应用中碰到的各种类型图预留出足够的空间；
- 2.Graph 的实例方法的实现一定要快。
下面有三种选择：
- 1.邻接矩阵：我们可以使用一个 V 乘 V 的布尔矩阵。当顶点 v 和 w 之间有连接的边时，定义 v 行 w 列的元素值为 true，否则为 false。这种表示方法不符合第一个条件--含有上百万个顶点的图所需的空间是不能满足的。
- 2.边的数组：我们可以使用一个 Edge 类，它含有两个 int 实例变量。这种表示方法很简单但不满足第二个条件--要实现 Adj 需要检查图中的所有边。
- 3.邻接表数组：使用一个以顶点为索引的列表数组，其中每个元素都是和该顶点相连的顶点列表。
非稠密图的标准表示成为邻接表的数据结构，它将每个顶点的所有相邻顶点都保存在该顶点对应的元素所指向的一张链表中。我们使用这个数组就是为了快速访问给定顶点的邻接顶点列表。这里使用 Bag 来实现这个链表，这样我们就可以在常数时间内添加新的边或遍历任意顶点的所有相邻顶点。
要添加一条连接 v 与 w 的边，我们将 w 添加到 v 的邻接表中并把 v 添加到 w 的邻接表中。因此在这个数据结构中每条边都会出现两次。这种 Graph 的实现的性能特点：
- 1.使用的空间和 V+E 成正比；
- 2.添加一条边所需的时间为常数；
- 3.遍历顶点 v 的所有相邻顶点所需的时间和 v 的度数成正比。
对于这些操作，这样的特性已经是最优的了，而且支持平行边和自环。注意，边的插入顺序决定了Graph 的邻接表中顶点的出现顺序。多个不同的邻接表可能表示着同一幅图。因为算法在使用 Adj() 处理所有相邻的顶点时不会考虑它们在邻接表中的出现顺序，这种差异不会影响算法的正确性，但在调试或是跟踪邻接表的轨迹时需要注意这一点。
public class Graph
{
private int v;
private int e;
private List<int>[] adj; //邻接表(用List 代替 bag)
/// <summary>
/// 创建一个含有V个顶点但不含有边的图
/// </summary>
/// <param name="V"></param>
public Graph(int V)
{
v = V;
e = 0;
adj = new List<int>[V];
for (var i = 0; i < V; i++)
adj[i] = new List<int>();
}
public Graph(string[] strs)
{
foreach (var str in strs)
{
var data = str.Split(' ');
int v = Convert.ToInt32(data[0]);
int w = Convert.ToInt32(data[1]);
AddEdge(v,w);
}
}
/// <summary>
/// 顶点数
/// </summary>
/// <returns></returns>
public int V()
{
return v;
}
/// <summary>
/// 边数
/// </summary>
/// <returns></returns>
public int E()
{
return e;
}
/// <summary>
/// 向图中添加一条边 v-w
/// </summary>
/// <param name="v"></param>
/// <param name="w"></param>
public void AddEdge(int v, int w)
{
adj[v].Add(w);
adj[w].Add(v);
e++;
}
/// <summary>
/// 和v相邻的所有顶点
/// </summary>
/// <param name="v"></param>
/// <returns></returns>
public IEnumerable<int> Adj(int v)
{
return adj[v];
}
/// <summary>
/// 计算 V 的度数
/// </summary>
/// <param name="G"></param>
/// <param name="V"></param>
/// <returns></returns>
public static int Degree(Graph G, int V)
{
int degree = 0;
foreach (int w in G.Adj(V))
degree++;
return degree;
}
/// <summary>
/// 计算所有顶点的最大度数
/// </summary>
/// <param name="G"></param>
/// <returns></returns>
public static int MaxDegree(Graph G)
{
int max = 0;
for (int v = 0; v < G.V(); v++)
{
var d = Degree(G, v);
if (d > max)
max = d;
}
return max;
}
/// <summary>
/// 计算所有顶点的平均度数
/// </summary>
/// <param name="G"></param>
/// <returns></returns>
public static double AvgDegree(Graph G)
{
return 2.0 * G.E() / G.V();
}
/// <summary>
/// 计算自环的个数
/// </summary>
/// <param name="G"></param>
/// <returns></returns>
public static int NumberOfSelfLoops(Graph G)
{
int count = 0;
for (int v = 0; v < G.V(); v++)
{
foreach (int w in G.Adj(v))
{
if (v == w)
count++;
}
}
return count / 2; //每条边都被计算了两次
}
public override string ToString()
{
string s = V() + " vertices, " + E() + " edges\n";
for (int v = 0; v < V(); v++)
{
s += v + ":";
foreach (int w in Adj(v))
{
s += w + " ";
}
s += "\n";
}
return s;
}
}
在实际应用中还有一些操作可能有用，例如：
- 添加一个顶点；
- 删除一个顶点。
实现这些操作的一种方法是，使用符号表 ST 来代替由顶点索引构成的数组，这样修改之后就不需要约定顶点名必须是整数了。可能还需要：
- 删除一条边；
- 检查图是否含有 v-w。
要实现这些方法，可能需要使用 SET 代替 Bag 来实现邻接表。我们称这种方法为邻接集。现在还不需要，因为：
- 不需要添加，删除顶点和边或是检查一条边是否存在；
- 上述操作使用频率很低或者相关链表很短，可以直接使用穷举法遍历；
- 某些情况下会使性能损失 logV。
3.图的处理算法的设计模式
因为我们会讨论大量关于图处理的算法，所以设计的首要目标是将图的表示和实现分离开来。为此，我们会为每个任务创建一个相应的类，用例可以创建相应的对象来完成任务。类的构造函数一般会在预处理中构造各种数据结构，以有效地响应用例的请求。典型的用例程序会构造一幅图，将图作为参数传递给某个算法类的构造函数，然后调用各种方法来获取图的各种性质。
我们用起点 s 区分作为参数传递给构造函数的顶点与图中的其他顶点。在这份 API 中，构造函数的任务就是找到图中与起点连通的其他顶点。用例可以调用 marked 方法和 count 方法来了解图的性质。方法名 marked 指的是这种基本方法使用的一种实现方式：在图中从起点开始沿着路径到达其他顶点并标记每个路过的顶点。
在 union-find算法已经见过 Search API 的实现，它的构造函数会创建一个 UF 对象，对图中的每条边进行一次 union 操作并调用 connected(s,v) 来实现 marked 方法。实现 count 方法需要一个加权的 UF 实现并扩展它的API，以便使用 count 方法返回 sz[find(v)]。
下面的一种搜索算法是基于深度优先搜索（DFS）的，它会沿着图的边寻找喝起点连通的所有顶点。
4.深度优先搜索
要搜索一幅图，只需要一个递归方法来遍历所有顶点。在访问其中一个顶点时：
- 1.将它标记为已访问；
- 2.递归地访问它所有没有被标记过地邻居顶点。
这种方法称为深度优先搜索（DFS）。
namespace Graphs
{
/// <summary>
/// 使用一个 bool 数组来记录和起点连通地所有顶点。递归方法会标记给定地顶点并调用自己来访问该顶点地相邻顶点列表中
/// 所有没有被标记过地顶点。 如果图是连通的，每个邻接链表中的元素都会被标记。
/// </summary>
public class DepthFirstSearch
{
private bool[] marked;
private int count;
public DepthFirstSearch(Graph G,int s)
{
marked = new bool[G.V()];
Dfs(G,s);
}
private void Dfs(Graph g, int V)
{
marked[V] = true;
count++;
foreach (var w in g.Adj(V))
{
if (!marked[w])
Dfs(g,w);
}
}
public bool Marked(int w)
{
return marked[w];
}
}
}
深度优先搜索标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比。
这种简单的递归模式只是一个开始 -- 深度优先搜索能够有效处理许多和图有关的任务。
- 1.连通性。给定一幅图，两个给定的顶点是否连通？（两个给定的顶点之间是否存在一条路径?路径检测） 图中有多少个连通子图？
- 2.单点路径。给定一幅图和一个起点 s ，从 s 到给定目的顶点 v 是否存在一条路径？如果有，找出这条路径。
5.寻找路径
单点路径的API：
构造函数接受一个起点 s 作为参数，计算 s 到与 s 连通的每个顶点之间的路径。在为起点 s 创建 Paths 对象之后，用例可以调用 PathTo 方法来遍历从 s 到任意和 s 连通的顶点的路径上的所有顶点。
实现
下面的算法基于深度优先搜索，它添加了一个 edgeTo[ ] 整型数组，这个数组可以找到从每个与 s 连通的顶点回到 s 的路径。它会记住每个顶点到起点的路径，而不是记录当前顶点到起点的路径。为了做到这一点，在由边 v-w 第一次任意访问 w 时，将edgeTo[w] = v 来记住这条路径。换句话说， v-w 是从s 到 w 的路径上最后一条已知的边。这样，搜索的结果是一棵以起点为根结点的树，edgeTo[ ] 是一棵由父链接表示的树。 PathTo 方法用变量 x 遍历整棵树，将遇到的所有顶点压入栈中。
public class DepthFirstPaths
{
private bool[] marked;
private int[] edgeTo; //从起点到一个顶点的已知路径上的最后一个顶点
private int s;//起点
public DepthFirstPaths(Graph G, int s)
{
marked = new bool[G.V()];
edgeTo = new int[G.V()];
this.s = s;
Dfs(G,s);
}
private void Dfs(Graph G, int v)
{
marked[v] = true;
foreach (int w in G.Adj(v))
{
if (!marked[w])
{
edgeTo[w] = v;
Dfs(G,w);
}
}
}
public bool HasPathTo(int v)
{
return marked[v];
}
public IEnumerable<int> PathTo(int v)
{
if (!HasPathTo(v))
return null;
Stack<int> path = new Stack<int>();
for (int x = v; x != s; x = edgeTo[x])
path.Push(x);
path.Push(s);
return path;
}
}
使用深度优先搜索得到从给定起点到任意标记顶点的路径所需的时间与路径长度成正比。
6.广度优先搜索
深度优先搜索得到的路径不仅取决于图的结构，还取决于图的表示和递归调用的性质。
单点最短路径：给定一幅图和一个起点 s ，从 s 到给定目的顶点 v 是否存在一条路径？如果有，找出其中最短的那条（所含边最少）。
解决这个问题的经典方法叫做广度优先搜索（BFS）。深度优先搜索在这个问题上没有什么作用，因为它遍历整个图的顺序和找出最短路径的目标没有任何关系。相比之下，广度又出现搜索正式为了这个目标才出现的。
要找到从 s 到 v 的最短路径，从 s 开始，在所有由一条边就可以到达的顶点中寻找 v ，如果找不到就继续在与 s 距离两条边的所有顶点中查找 v ,如此一直进行。
在程序中，在搜索一幅图时遇到有很多边需要遍历的情况时，我们会选择其中一条并将其他边留到以后再继续搜索。在深度优先搜索中，我们用了一个可以下压栈。使用LIFO （后进先出）的规则来描述下压栈和走迷宫时先探索相邻的
通道类似。从有待搜索的通道中选择最晚遇到过的那条。在广度优先搜索中，我们希望按照与起点距离的顺序来遍历所有顶点，使用（FIFO，先进先出）队列来代替栈即可。我们将从有待搜索的通道中选择最早遇到的那条。
实现
下面的算法使用了一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。先将顶点加入队列，然后重复下面步骤知道队列为空：
- 1.取队列的下一个顶点 v 并标记它；
- 2.将与 v 相邻的所有未被标记过的顶点加入队列。
下面的 Bfs 方法不是递归。它显示地使用了一个队列。和深度优先搜索一样，它的结果也是一个数组 edgeTo[ ] ，也是一棵用父链接表示的根结点为 s 的树。它表示了 s 到每个与 s 连通的顶点的最短路径。
namespace Graphs
{
/// <summary>
/// 广度优先搜索
/// </summary>
public class BreadthFirstPaths
{
private bool[] marked;//到达该顶点的最短路径已知吗？
private int[] edgeTo;//到达该顶点的已知路径上的最后一个顶点
private int s;//起点
public BreadthFirstPaths(Graph G,int s)
{
marked = new bool[G.V()];
edgeTo = new int[G.V()];
this.s = s;
Bfs(G,s);
}
private void Bfs(Graph G, int s)
{
Queue<int> queue = new Queue<int>();
marked[s] = true;//标记起点
queue.Enqueue(s);//将它加入队列
while (queue.Count > 0)
{
int v = queue.Dequeue();//从队列中删去下一个顶点
foreach (var w in G.Adj(v))
{
if (!marked[w])//对于每个未标记的相邻顶点
{
edgeTo[w] = v;//保存最短路径的最后一条边
marked[w] = true;//标记它，因为最短路径已知
queue.Enqueue(w);//并将它添加到队列中
}
}
}
}
public bool HasPathTo(int v)
{
return marked[v];
}
}
}
轨迹：
对于从 s 可达的任意顶点 v ,广度优先搜索都能找到一条从 s 到 v 的最短路径，没有其他从 s 到 v 的路径所含的边比这条路径更少。
广度优先搜索所需的时间在最坏情况下和 V+E 成正比。
我们也可以使用广度优先搜索来实现已经用深度优先搜索实现的 Search API，因为它检查所有与起点连通的顶点和边的方法只取决于查找能力。
广度优先搜索和深度优先搜索在搜索中都会先将起点存入数据结构，然后重复以下步骤直到数据结构清空：
- 1.取其中的下一个顶点并标记它；
- 2.将 v 的所有相邻而又未被标记的顶点加入数据结构。
这两个算法的不同之处在于从数据结构中获取下一个顶点的规则（对于广度优先搜索来说是最早加入的顶点，对于深度优先搜索来说是最晚加入的顶点）。这种差异得到了处理图的两种完全不同的视角，尽管无论使用哪种规则，所有与起点连通的顶点和边都会被检查到。
深度优先搜索不断深入图中并在栈中保存了所有分叉的顶点；广度优先搜索则像扇面一般扫描图，用一个队列保存访问过的最前端的顶点。深度优先搜索探索一幅图的方式是寻找离起点更远的顶点，只在碰到死胡同时才访问进出的顶点；广度优先搜索则首先覆盖起点附近的顶点，只在临近的所有顶点都被访问了之后才向前进。根据应用的不同，所需要的性质也不同。
7.连通分量
深度优先搜索的下一个直接应用就是找出一幅图的所有连通分量。在 union-find中 “与......连通” 是一种等价关系，它能够将所有顶点切分成等价类（连通分量）。
实现
CC 的实现使用了marked 数组来寻找一个顶点作为每个连通分量中深度优先搜索的起点。递归的深度优先搜索第一次调用的参数是顶点 0 -- 它会标记所有与 0 连通的顶点。然后构造函数中的 for 循环会查找每个没有被标记的顶点并递归调用 Dfs 来标记和它相邻的所有顶点。另外，还使用了一个以顶点作为索引的数组 id[ ] ，值为连通分量的标识符，将同一连通分量中的顶点和连通分量的标识符关联起来。这个数组使得 Connected 方法的实现变得非常简单。
namespace Graphs
{
public class CC
{
private bool[] marked;
private int[] id;
private int count;
public CC(Graph G)
{
marked = new bool[G.V()];
id = new int[G.V()];
for (var s = 0; s < G.V(); s++)
{
if (!marked[s])
{
Dfs(G,s);
count++;
}
}
}
private void Dfs(Graph G, int v)
{
marked[v] = true;
id[v] = count;
foreach (var w in G.Adj(v))
{
if (!marked[w])
Dfs(G,w);
}
}
public bool Connected(int v, int w)
{
return id[v] == id[w];
}
public int Id(int v)
{
return id[v];
}
public int Count()
{
return count;
}
}
}
深度优先搜索的预处理使用的时间和空间与 V + E 成正比且可以在常数时间内处理关于图的连通性查询。由代码可知每个邻接表的元素都只会被检查一次，共有 2E 个元素（每条边两个）。
union-find 算法
CC 中基于深度优先搜索来解决图连通性问题的方法与 union-find算法 中的算法相比，理论上，深度优先搜索更快，因为它能保证所需的时间是常数而 union-find算法不行；但在实际应用中，这点差异微不足道。union-find算法其实更快，因为它不需要完整地构造表示一幅图。更重要的是，union-find算法是一种动态算法（我们在任何时候都能用接近常数的时间检查两个顶点是否连通，甚至是添加一条边的时候），但深度优先搜索则必须对图进行预处理。
因此，我们在只需要判断连通性或是需要完成大量连通性查询和插入操作混合等类似的任务时，更倾向使用union-find算法，而深度优先搜索则适合实现图的抽象数据类型，因为它能更有效地利用已有的数据结构。
使用深度优先搜索还可以解决 检测环 和双色问题：
检测环，给定的图是无环图吗？
namespace Graphs
{
public class Cycle
{
private bool[] marked;
private bool hasCycle;
public Cycle(Graph G)
{
marked = new bool[G.V()];
for (var s = 0; s < G.V(); s++)
{
if (!marked[s])
Dfs(G,s,s);
}
}
private void Dfs(Graph g, int v, int u)
{
marked[v] = true;
foreach (var w in g.Adj(v))
{
if (!marked[w])
Dfs(g, w, v);
else if (w != u)
hasCycle = true;
}
}
public bool HasCycle()
{
return hasCycle;
}
}
}
是二分图吗？（双色问题）
namespace Graphs
{
public class TwoColor
{
private bool[] marked;
private bool[] color;
private bool isTwoColorable = true;
public TwoColor(Graph G)
{
marked = new bool[G.V()];
color = new bool[G.V()];
for(var s = 0;s<G.V();s++)
{
if (!marked[s])
Dfs(G,s);
}
}
private void Dfs(Graph g, int v)
{
marked[v] = true;
foreach (var w in g.Adj(v))
{
if (!marked[w])
{
color[w] = !color[v];
Dfs(g, w);
}
else if (color[w] == color[v])
isTwoColorable = false;
}
}
public bool IsBipartite()
{
return isTwoColorable;
}
}
}
8.符号图
在典型应用中，图都是通过文件或者网页定义的，使用的是字符串而非整数来表示和指代顶点。为了适应这样的应用，我们使用符号图。符号图的API：
这份API 定义一个构造函数来读取并构造图，用 name() 和 index() 方法将输入流中的顶点名和图算法使用的顶点索引对应起来。
实现
需要用到3种数据结构：
- 1.一个符号表 st ，键的类型为 string（顶点名），值的类型 int （索引）；
- 2.一个数组 keys[ ]，用作反向索引，保存每个顶点索引对应的顶点名；
- 3.一个 Graph 对象 G，它使用索引来引用图中顶点。
SymbolGraph 会遍历两遍数据来构造以上数据结构，这主要是因为构造 Graph 对象需要顶点总数 V。在典型的实际应用中，在定义图的文件中指明 V 和 E 可能会有些不便，而有了 SymbolGraph，就不需要担心维护边或顶点的总数。
namespace Graphs
{
public class SymbolGraph
{
private Dictionary<string, int> st;//符号名 -> 索引
private string[] keys;//索引 -> 符号名
private Graph G;
public SymbolGraph(string fileName, string sp)
{
var strs = File.ReadAllLines(fileName);
st = new Dictionary<string, int>();
//第一遍
foreach (var str in strs)
{
var _strs = str.Split(sp);
foreach (var _str in _strs)
{
st.Add(_str,st.Count);
}
}
keys = new string[st.Count];
foreach (var name in st.Keys)
{
keys[st[name]] = name;
}
//第二遍 将每一行的第一个顶点和该行的其他顶点相连
foreach (var str in strs)
{
var _strs = str.Split(sp);
int v = st[_strs[0]];
for (var i = 1; i < _strs.Length; i++)
{
G.AddEdge(v,st[_strs[i]]);
}
}
}
public bool Contains(string s)
{
return st.ContainsKey(s);
}
public int Index(string s)
{
return st[s];
}
public string Name(int v)
{
return keys[v];
}
public Graph Gra()
{
return G;
}
}
}
间隔的度数
可以使用SymbolGraph 和 BreadthFirstPaths 来查找图中的最短路径：
总结
