1294 lines
30 KiB
Markdown
1294 lines
30 KiB
Markdown
|
||
# 08 图
|
||
|
||
**知识结构：**
|
||
|
||
|
||
|
||
|
||
|
||
---
|
||
|
||
## 1. 图的基本概念与术语
|
||
|
||
### 1.1 图的定义
|
||
|
||
图由顶点集和边集组成，记为 $G=(V,E)$。
|
||
- 顶点集：顶点的有穷非空集合，记为$V(G)$。
|
||
- 边集：顶点偶对的有穷集合，记为$E(G)$ 。
|
||
|
||
边：
|
||
- 无向边：$(v_i,v_j)=(v_j,v_i)$
|
||
- 有向边（弧）：$ <v_i,v_j> \neq <v_j,v_i> $ 始点$v_i$称为弧尾，终点$v_j$称为弧头。
|
||
|
||
例题：
|
||
|
||
|
||
|
||
|
||
例题：
|
||
|
||
|
||
|
||
### 1.2 图的分类
|
||
|
||
- 有向图：$E(G)$由有向边构成。
|
||
- 无向图：$E(G)$由无向边构成。
|
||
|
||
### 1.3 图中顶点数与边数的关系
|
||
|
||
（1）设顶点数为$n$，边数为$e$则：
|
||
|
||
- 无向图：$0\leq e \leq \frac{n(n-1)}{2}$，$e=\frac{n(n-1)}{2}$的图称为无向完全图。
|
||
- 有向图：$0\leq e \leq n(n-1)$，$e = n(n-1)$的图称为有向完全图。
|
||
|
||
（2）顶点的度
|
||
|
||
- 无向图：$D(v)=$与$v$连接的边数。
|
||
- 有向图：$D(v)=ID(v)+OD(v)$
|
||
- $ID(v)$：以$v$为终点（弧头）的边数。
|
||
- $OD(v)$：以$v$为起点（弧尾）的边数。
|
||
|
||
（3）度与边的关系
|
||
|
||
|
||
$$
|
||
e=\frac{\sum_{i=1}^{n}D(v_i)}{2}
|
||
$$
|
||
|
||
（4）正则图：所有顶点的度都相同的图
|
||
|
||
|
||
|
||
|
||
### 1.4 路径
|
||
|
||
（1）定义：图$G=(V,E)$，若存在一个顶点序列 $v_p,v_{i1},v_{i2},\cdots,v_{im},v_q$，使得$(v_p,v_{i1}),(v_{i1},v_{i2}),\cdots,(v_{im},v_q)\in E(G)$（无向图）或者$ <v_p,v_{i1}>,<v_{i1},v_{i2}>,\cdots,<v_{im},v_q>\in E(G)$（有向图）则称$v_p$到$v_q$存在一条路径。
|
||
|
||
（2）路径的长度：路径上边的数目。
|
||
|
||
（3）简单路径：若一条路径上除$v_p$，$v_q$可相同外，其余顶点均不相同的路径。
|
||
|
||
（4）简单回路：$v_p$与$v_q$相同的简单路径。
|
||
|
||
### 1.5 子图
|
||
设$G=(V,E)$是一个图，若$V'\subseteq V$，$E'\subseteq E$且$E^{'}$中的边所关联的顶点$\in V'$，则$G'=(V',E')$ 也是一个图，并称其为$G$的子图。
|
||
|
||
|
||
|
||
### 1.6 连通图与连通分量（无向图）
|
||
|
||
连通图：无向图$G$的$V(G)$中，任何两个顶点都存在路径，则称$G$为连通图。
|
||
|
||
连通分量：无向图$G$的极大连通子图。
|
||
|
||
注：
|
||
|
||
- 连通图的连通分量只有一个，为其本身。
|
||
- 非连通图的连通分量不唯一。
|
||
|
||
例子：
|
||
|
||
|
||
|
||
### 1.7 强连通图与强连通分量（有向图）
|
||
|
||
强连通图：有向图$G$的$V(G)$中，任何两个顶点都存在路径，则称$G$为强连通图。
|
||
|
||
强连通分量：有向图$G$的极大连通子图。
|
||
|
||
注：
|
||
- 强连通图的强连通分量只有一个，为其本身。
|
||
- 非强连通图的强连通分量不唯一。
|
||
|
||
例子：
|
||
|
||
|
||
|
||
### 1.8 网络
|
||
|
||
$E(G)$中的每条边都带有权值的图称为网络。
|
||
|
||
注：权一般具有实际意义，比如距离、消耗等。
|
||
|
||
例子：
|
||
|
||
|
||
|
||
|
||
---
|
||
## 2. 图的存储结构
|
||
|
||
### 2.1 顺序存储（邻接矩阵）
|
||
|
||
邻接矩阵：表示顶点之间相邻关系的矩阵
|
||
|
||
若图$G=(V,E)$，则其邻接矩阵可表示为：
|
||
|
||
$$
|
||
A[i,j]=\begin{cases}
|
||
1, & (v_i,v_j)\in E(G) or \left\langle v_i,v_j \right\rangle \in E(G)\\
|
||
0, & (v_i,v_j)\notin E(G) or \left\langle v_i,v_j \right\rangle \notin E(G)
|
||
\end{cases}
|
||
$$
|
||
|
||
例子：无向图的存储
|
||
|
||
|
||
|
||
|
||
例子：有向图的存储
|
||
|
||
|
||
|
||
若图$G=(V,E)$为网络，则其邻接矩阵可表示为：
|
||
|
||
|
||
$$
|
||
A[i,j]=\begin{cases}
|
||
\omega_{ij}, & (v_i,v_j)\in E(G) or \left\langle v_i,v_j \right\rangle\in E(G)\\
|
||
0 or \infty, & (v_i,v_j)\notin E(G) or \left\langle v_i,v_j \right\rangle\notin E(G)
|
||
\end{cases}
|
||
$$
|
||
|
||
例子：网络的存储
|
||
|
||
|
||
|
||
|
||
|
||
|
||
```c
|
||
using System;
|
||
namespace NonLinearStruct.Graph
|
||
{
|
||
/// <summary>
|
||
/// 图抽象数据类型实现--利用邻接矩阵
|
||
/// </summary>
|
||
public class MGraph
|
||
{
|
||
private readonly double[,] _adMatrix;//邻接矩阵
|
||
private readonly string[] _vertexNameList;//存储图中各结点名字的数组
|
||
|
||
/// <summary>
|
||
/// 获取图中结点的个数
|
||
/// </summary>
|
||
public int VertexCount { get; }
|
||
|
||
/// <summary>
|
||
/// 初始化MGraph类的新实例
|
||
/// </summary>
|
||
/// <param name="vCount">图中结点的个数</param>
|
||
public MGraph(int vCount)
|
||
{
|
||
if (vCount <= 0)
|
||
throw new ArgumentOutOfRangeException();
|
||
|
||
VertexCount = vCount;
|
||
_vertexNameList = new string[vCount];
|
||
_adMatrix = new double[vCount, vCount];
|
||
}
|
||
|
||
/// <summary>
|
||
/// 获取或设置图中各结点的名称
|
||
/// </summary>
|
||
/// <param name="index">结点名称从零开始的索引</param>
|
||
/// <returns>指定索引处结点的名称</returns>
|
||
public string this[int index]
|
||
{
|
||
get
|
||
{
|
||
if (index < 0 || index > VertexCount - 1)
|
||
throw new IndexOutOfRangeException();
|
||
return _vertexNameList[index];
|
||
}
|
||
set
|
||
{
|
||
if (index < 0 || index > VertexCount - 1)
|
||
throw new IndexOutOfRangeException();
|
||
_vertexNameList[index] = value;
|
||
}
|
||
}
|
||
|
||
private int GetIndex(string vertexName)
|
||
{
|
||
//根据结点名字获取结点在数组中的下标
|
||
int i;
|
||
for (i = 0; i < VertexCount; i++)
|
||
{
|
||
if (_vertexNameList[i] == vertexName)
|
||
break;
|
||
}
|
||
return i == VertexCount ? -1 : i;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 给邻接矩阵赋值
|
||
/// </summary>
|
||
/// <param name="startVertexName">起始结点的名字</param>
|
||
/// <param name="endVertexName">终止结点的名字</param>
|
||
/// <param name="weight">边上的权值或连接关系</param>
|
||
public void AddEdge(string startVertexName, string endVertexName, double weight = 1)
|
||
{
|
||
int i = GetIndex(startVertexName);
|
||
int j = GetIndex(endVertexName);
|
||
if (i == -1 || j == -1)
|
||
throw new Exception("图中不存在该边.");
|
||
_adMatrix[i, j] = weight;
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
### 2.2 链式存储（邻接表）
|
||
|
||
邻接表：由顺序存储的顶点表和链式存储的边表构成的图的存储结构。
|
||
|
||
例子：无向图的存储
|
||
|
||
|
||
|
||
例子：有向图的存储
|
||
|
||
|
||
|
||
|
||
例子：网络的存储
|
||
|
||
|
||
|
||
边表结点的实现：
|
||
|
||
|
||
|
||
|
||
|
||
```c
|
||
using System;
|
||
namespace NonLinearStruct.Graph
|
||
{
|
||
/// <summary>
|
||
/// 邻接表边表上的结点
|
||
/// </summary>
|
||
public class EdgeNode
|
||
{
|
||
/// <summary>
|
||
/// 获取边终点在顶点数组中的位置
|
||
/// </summary>
|
||
public int Index { get; }
|
||
|
||
/// <summary>
|
||
/// 获取边上的权值
|
||
/// </summary>
|
||
public double Weight { get; }
|
||
|
||
/// <summary>
|
||
/// 获取或设置下一个邻接点
|
||
/// </summary>
|
||
public EdgeNode Next { get; set; }
|
||
|
||
/// <summary>
|
||
/// 初始化EdgeNode类的新实例
|
||
/// </summary>
|
||
/// <param name="index">边终点在顶点数组中的位置</param>
|
||
/// <param name="weight">边上的权值</param>
|
||
/// <param name="next">下一个邻接点</param>
|
||
public EdgeNode(int index, double weight = 0.0, EdgeNode next = null)
|
||
{
|
||
if (index < 0)
|
||
throw new ArgumentOutOfRangeException();
|
||
|
||
Index = index;
|
||
Weight = weight;
|
||
Next = next;
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
顶点表结点的实现：
|
||
|
||
|
||
|
||
|
||
|
||
```c
|
||
namespace NonLinearStruct.Graph
|
||
{
|
||
/// <summary>
|
||
/// 邻接表顶点表中的结点
|
||
/// </summary>
|
||
public class VertexNode
|
||
{
|
||
/// <summary>
|
||
/// 获取或设置顶点的名字
|
||
/// </summary>
|
||
public string VertexName { get; set; }
|
||
|
||
/// <summary>
|
||
/// 获取或设置顶点是否被访问
|
||
/// </summary>
|
||
public bool Visited { get; set; }
|
||
|
||
/// <summary>
|
||
/// 获取或设置顶点的第一个邻接点
|
||
/// </summary>
|
||
public EdgeNode FirstNode { get; set; }
|
||
|
||
/// <summary>
|
||
/// 初始化VertexNode类的新实例
|
||
/// </summary>
|
||
/// <param name="vName">顶点的名字</param>
|
||
/// <param name="firstNode">顶点的第一个邻接点</param>
|
||
public VertexNode(string vName, EdgeNode firstNode = null)
|
||
{
|
||
VertexName = vName;
|
||
Visited = false;
|
||
FirstNode = firstNode;
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
图结构的实现
|
||
|
||
|
||
|
||
```c
|
||
using System;
|
||
using System.Collections.Generic;
|
||
using System.Linq;
|
||
using LinearStruct;
|
||
|
||
namespace NonLinearStruct.Graph
|
||
{
|
||
/// <summary>
|
||
/// 图抽象数据类型实现--利用邻接表
|
||
/// </summary>
|
||
public class AdGraph
|
||
{
|
||
private readonly VertexNode[] _vertexList; //结点表
|
||
|
||
/// <summary>
|
||
/// 获取图的结点数
|
||
/// </summary>
|
||
public int VertexCount { get; }
|
||
|
||
/// <summary>
|
||
/// 初始化AdGraph类的新实例
|
||
/// </summary>
|
||
/// <param name="vCount">图中结点的个数</param>
|
||
public AdGraph(int vCount)
|
||
{
|
||
if (vCount <= 0)
|
||
throw new ArgumentOutOfRangeException();
|
||
|
||
VertexCount = vCount;
|
||
_vertexList = new VertexNode[vCount];
|
||
}
|
||
|
||
/// <summary>
|
||
/// 获取或设置图中各结点的名称
|
||
/// </summary>
|
||
/// <param name="index">结点名称从零开始的索引</param>
|
||
/// <returns>指定索引处结点的名称</returns>
|
||
public string this[int index]
|
||
{
|
||
get
|
||
{
|
||
if (index < 0 || index > VertexCount - 1)
|
||
throw new ArgumentOutOfRangeException();
|
||
|
||
return _vertexList[index] == null
|
||
? "NULL"
|
||
: _vertexList[index].VertexName;
|
||
}
|
||
set
|
||
{
|
||
if (index < 0 || index > VertexCount - 1)
|
||
throw new ArgumentOutOfRangeException();
|
||
|
||
if (_vertexList[index] == null)
|
||
_vertexList[index] = new VertexNode(value);
|
||
else
|
||
_vertexList[index].VertexName = value;
|
||
}
|
||
}
|
||
|
||
/// <summary>
|
||
/// 得到结点在结点表中的位置
|
||
/// </summary>
|
||
/// <param name="vertexName">结点的名称</param>
|
||
/// <returns>结点的位置</returns>
|
||
private int GetIndex(string vertexName)
|
||
{
|
||
int i;
|
||
for (i = 0; i < VertexCount; i++)
|
||
{
|
||
if (_vertexList[i] != null && _vertexList[i].VertexName == vertexName)
|
||
break;
|
||
}
|
||
return i == VertexCount ? -1 : i;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 给图加边
|
||
/// </summary>
|
||
/// <param name="startVertexName">起始结点的名字</param>
|
||
/// <param name="endVertexName">终止结点的名字</param>
|
||
/// <param name="weight">边上的权值</param>
|
||
public void AddEdge(string startVertexName, string endVertexName, double weight = 0.0)
|
||
{
|
||
int i = GetIndex(startVertexName);
|
||
int j = GetIndex(endVertexName);
|
||
|
||
if (i == -1 || j == -1)
|
||
throw new Exception("图中不存在该边.");
|
||
|
||
EdgeNode temp = _vertexList[i].FirstNode;
|
||
if (temp == null)
|
||
{
|
||
_vertexList[i].FirstNode = new EdgeNode(j, weight);
|
||
}
|
||
else
|
||
{
|
||
while (temp.Next != null)
|
||
temp = temp.Next;
|
||
temp.Next = new EdgeNode(j, weight);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
---
|
||
## 3. 图的遍历
|
||
### 3.1 深度优先搜索
|
||
|
||
算法：
|
||
|
||
假设$G=(V,E)$以$S$为起点（源点）进行搜索。
|
||
|
||
首先标识$S$为已访问结点，接着寻找与$S$相邻的结点$\omega$，若$\omega$是未被访问结点，则以$\omega$为起点进行深度优先搜索，若$\omega$是已被访问结点，则寻找其它与$S$相邻的结点，直到与$S$有路径相通的所有结点都被访问过。
|
||
|
||
例子：
|
||
|
||
|
||
|
||
深度优先搜索的序列为：$V_0,V_1,V_3,V_7,V_4,V_5,V_2,V_6$
|
||
|
||
虽然遍历序列不唯一，但是邻接表确定后，遍历序列就唯一了。
|
||
|
||
实现：
|
||
|
||
|
||
|
||
|
||
|
||
```c
|
||
private void Dfs(int i, ref string dfsResult)
|
||
{
|
||
//深度优先搜索递归函数
|
||
_vertexList[i].Visited = true;
|
||
dfsResult += _vertexList[i].VertexName + "\n";
|
||
|
||
EdgeNode p = _vertexList[i].FirstNode;
|
||
while (p != null)
|
||
{
|
||
if (_vertexList[p.Index].Visited)
|
||
p = p.Next;
|
||
else
|
||
Dfs(p.Index, ref dfsResult);
|
||
}
|
||
}
|
||
|
||
/// <summary>
|
||
/// 得到深度优先搜索序列
|
||
/// </summary>
|
||
/// <param name="startVertexName">进行深度优先搜索的起始点名称</param>
|
||
/// <returns>深度优先搜索序列</returns>
|
||
public string DfsTraversal(string startVertexName)
|
||
{
|
||
string dfsResult = string.Empty;
|
||
int i = GetIndex(startVertexName);
|
||
if (i != -1)
|
||
{
|
||
for (int j = 0; j < VertexCount; j++)
|
||
_vertexList[j].Visited = false;
|
||
Dfs(i, ref dfsResult);
|
||
}
|
||
return dfsResult;
|
||
}
|
||
```
|
||
|
||
### 3.2 广度优先搜索
|
||
|
||
算法：
|
||
|
||
假设$G=(V,E)$以$S$为起点（源点）进行搜索。
|
||
|
||
首先标识$S$为已访问结点，接着访问$S$的邻接点$\omega_1,\omega_2,\cdots,\omega_t$然后访问$\omega_1,\omega_2,\cdots,\omega_t$的未被访问的邻接点，以此类推，直到与$S$有路径相连的所有结点都被访问到。
|
||
|
||
先来先服务的思想。
|
||
|
||
例子：
|
||
|
||
|
||
|
||
深度优先搜索的序列为：$V_0,V_1,V_2,V_3,V_4,V_5,V_6,V_7$
|
||
|
||
虽然遍历序列不唯一，但是邻接表确定后，遍历序列就唯一了。
|
||
|
||
|
||
实现：
|
||
|
||
|
||
|
||
```c
|
||
/// <summary>
|
||
/// 得到广度优先搜索序列
|
||
/// </summary>
|
||
/// <param name="startNodeName">进行广度优先搜索的起始点名称</param>
|
||
/// <returns>广度优先搜索序列</returns>
|
||
public string BfsTraversal(string startNodeName)
|
||
{
|
||
string bfsResult = string.Empty;
|
||
int i = GetIndex(startNodeName);
|
||
if (i != -1)
|
||
{
|
||
for (int j = 0; j < VertexCount; j++)
|
||
_vertexList[j].Visited = false;
|
||
|
||
_vertexList[i].Visited = true;
|
||
bfsResult += _vertexList[i].VertexName + "\n";
|
||
LinkQueue<int> lq = new LinkQueue<int>();
|
||
lq.EnQueue(i);
|
||
while (lq.IsEmpty() == false)
|
||
{
|
||
int j = lq.QueueFront;
|
||
lq.DeQueue();
|
||
EdgeNode p = _vertexList[j].FirstNode;
|
||
while (p != null)
|
||
{
|
||
if (_vertexList[p.Index].Visited == false)
|
||
{
|
||
_vertexList[p.Index].Visited = true;
|
||
bfsResult += _vertexList[p.Index].VertexName + "\n";
|
||
lq.EnQueue(p.Index);
|
||
}
|
||
p = p.Next;
|
||
}
|
||
}
|
||
}
|
||
return bfsResult;
|
||
}
|
||
```
|
||
|
||
---
|
||
## 4. 拓扑排序
|
||
|
||
### 4.1 基本概念
|
||
|
||
$AOV$网（Activity on Vertex Network）：用顶点表示活动，用有向边表示活动之间先后关系的有向图。
|
||
|
||
拓扑序列：把$AOV$网中的所有顶点排成一个线性序列，使每个活动的所有前驱活动都排在该活动的前边。
|
||
|
||
拓扑排序：构造$AOV$网拓扑序列的过程。
|
||
|
||
例题：按照拓扑排序安排下列课程
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
### 4.2 算法步骤
|
||
|
||
第1步：从网中选择一个入度为0的顶点加入排序序列。
|
||
|
||
第2步：从网中删除该顶点及其所有出边。
|
||
|
||
第3步：执行第1、2步，直到所有顶点已排序或网中剩余顶点入度均不为0（说明：网中存在回路，无法继续拓扑排序）。
|
||
|
||
拓扑序列：
|
||
|
||
（1）$V_0,V_1,V_4,V_6,V_2,V_3,V_7,V_5,V_8$
|
||
|
||
（2）$V_0,V_6,V_1,V_2,V_3,V_4,V_5,V_8,V_7$
|
||
|
||
注：对于任何无回路的$AOV$网，其顶点均可排成拓扑序列，但其拓扑序列未必唯一。
|
||
|
||
|
||
|
||
存在回路的有向图，不能构成拓扑序列。
|
||
|
||
### 4.3 算法实现
|
||
|
||
|
||
|
||
```c
|
||
/// <summary>
|
||
/// 得到每个节点的入度
|
||
/// </summary>
|
||
/// <returns></returns>
|
||
private int[] GetInDegressList()
|
||
{
|
||
int[] id = new int[VertexCount];
|
||
for (int i = 0; i < VertexCount; i++)
|
||
{
|
||
EdgeNode p = _vertexList[i].FirstNode;
|
||
while (p != null)
|
||
{
|
||
id[p.Index]++;
|
||
p = p.Next;
|
||
}
|
||
}
|
||
return id;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 得到AOV网的拓扑排序序列
|
||
/// </summary>
|
||
/// <returns>AOV网的拓扑排序序列</returns>
|
||
public string TopoSort()
|
||
{
|
||
string result = string.Empty;
|
||
int[] id = GetInDegressList();
|
||
LinkQueue<int> lq = new LinkQueue<int>();
|
||
for (int i = 0; i < VertexCount; i++)
|
||
{
|
||
if (id[i] == 0)
|
||
lq.EnQueue(i);
|
||
}
|
||
|
||
if (lq.Length == VertexCount)
|
||
throw new Exception("此有向图无有向边.");
|
||
|
||
while (lq.IsEmpty() == false)
|
||
{
|
||
int j = lq.QueueFront;
|
||
lq.DeQueue();
|
||
result += _vertexList[j].VertexName + "\n";
|
||
|
||
EdgeNode p = _vertexList[j].FirstNode;
|
||
while (p != null)
|
||
{
|
||
id[p.Index]--;
|
||
if (id[p.Index] == 0)
|
||
{
|
||
lq.EnQueue(p.Index);
|
||
}
|
||
p = p.Next;
|
||
}
|
||
}
|
||
int k;
|
||
for (k = 0; k < VertexCount; k++)
|
||
{
|
||
if (id[k] != 0)
|
||
{
|
||
break;
|
||
}
|
||
}
|
||
return (k == VertexCount) ? result : "该AOV网有环.";
|
||
}
|
||
```
|
||
|
||
|
||
---
|
||
## 5. 最小生成树
|
||
|
||
### 5.1 基本概念
|
||
|
||
生成树：设$G$为连通网，具有$G$的所有顶点（$n$个）且只有$n-1$条边的连通子网。
|
||
|
||
树的权：生成树$T$的各边的权值总和。
|
||
|
||
最小生成树：权值最小的生成树。
|
||
|
||
### 5.2 Prim算法
|
||
|
||
算法原理（贪心算法）：
|
||
|
||
设$G=(V,E)$为连通网，$T=(U,TE)$为其对应的最小生成树，从$v_0$开始构造。
|
||
|
||
（1）开始时，$U = \lbrace u_0=v_0 \rbrace$，$TE=\Phi$。
|
||
|
||
（2）找到满足$weight(u,v)=min \lbrace weight(u_i,v_j)|u_i \in U,v_j\in V-U \rbrace$的边，把它并入$TE$中，$v$同时并入$U$。
|
||
|
||
（3）反复执行（2），直到$U=V$时，终止算法。
|
||
|
||
例题：
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
算法实现：
|
||
|
||
最小生成树结点的存储：
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
```c
|
||
using System;
|
||
|
||
namespace NonLinearStruct
|
||
{
|
||
/// <summary>
|
||
/// 生成树结点的抽象数据类型
|
||
/// </summary>
|
||
public class SpanTreeNode
|
||
{
|
||
/// <summary>
|
||
/// 获取或设置结点本身的名称
|
||
/// </summary>
|
||
public string SelfName { get; }
|
||
|
||
/// <summary>
|
||
/// 获取或设置结点双亲的名称
|
||
/// </summary>
|
||
public string ParentName { get; }
|
||
|
||
/// <summary>
|
||
/// 获取或设置边的权值
|
||
/// </summary>
|
||
public double Weight { get; set; }
|
||
|
||
/// <summary>
|
||
/// 构造SpanTreeNode实例
|
||
/// </summary>
|
||
/// <param name="selfName">结点本身的名称</param>
|
||
/// <param name="parentName">结点双亲的名称</param>
|
||
/// <param name="weight">边的权值</param>
|
||
public SpanTreeNode(string selfName, string parentName, double weight)
|
||
{
|
||
if (string.IsNullOrEmpty(selfName) || string.IsNullOrEmpty(parentName))
|
||
throw new ArgumentNullException();
|
||
|
||
SelfName = selfName;
|
||
ParentName = parentName;
|
||
Weight = weight;
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
```c
|
||
/// <summary>
|
||
/// 得到连通网的最小生成树Prim算法
|
||
/// </summary>
|
||
/// <param name="vName">树根结点</param>
|
||
/// <returns>连通网的最小生成树</returns>
|
||
public SpanTreeNode[] MiniSpanTree(string vName)
|
||
{
|
||
int i = GetIndex(vName);
|
||
if (i == -1)
|
||
return null;
|
||
|
||
SpanTreeNode[] spanTree = new SpanTreeNode[VertexCount];
|
||
spanTree[0] = new SpanTreeNode(_vertexList[i].VertexName, "NULL", 0.0);
|
||
|
||
//U中结点到各结点最小权值那个结点在VertexList中的索引号
|
||
int[] vertexIndex = new int[VertexCount];
|
||
//U中结点到各个结点的最小权值
|
||
double[] lowCost = new double[VertexCount];
|
||
for (int j = 0; j < VertexCount; j++)
|
||
{
|
||
lowCost[j] = double.MaxValue;
|
||
vertexIndex[j] = i;
|
||
}
|
||
|
||
EdgeNode p1 = _vertexList[i].FirstNode;
|
||
while (p1 != null)
|
||
{
|
||
lowCost[p1.Index] = p1.Weight;
|
||
p1 = p1.Next;
|
||
}
|
||
vertexIndex[i] = -1;
|
||
|
||
for (int count = 1; count < VertexCount; count++)
|
||
{
|
||
double min = double.MaxValue;
|
||
int v = i;
|
||
for (int k = 0; k < VertexCount; k++)
|
||
{
|
||
if (vertexIndex[k] != -1 && lowCost[k] < min)
|
||
{
|
||
min = lowCost[k];
|
||
v = k;
|
||
}
|
||
}
|
||
spanTree[count] = new SpanTreeNode(_vertexList[v].VertexName, _vertexList[vertexIndex[v]].VertexName, min);
|
||
vertexIndex[v] = -1;
|
||
|
||
EdgeNode p2 = _vertexList[v].FirstNode;
|
||
while (p2 != null)
|
||
{
|
||
if (vertexIndex[p2.Index] != -1 && p2.Weight < lowCost[p2.Index])
|
||
{
|
||
lowCost[p2.Index] = p2.Weight;
|
||
vertexIndex[p2.Index] = v;
|
||
}
|
||
p2 = p2.Next;
|
||
}
|
||
}
|
||
return spanTree;
|
||
}
|
||
```
|
||
|
||
### 5.3 Kruskar算法
|
||
|
||
设$G=(V,E)$为连通网，$T$为其对应的最小生成树。
|
||
|
||
（1）初始时$T=\lbrace V, \lbrace \Phi \rbrace \rbrace$，即$T$中没有边，只有$n$个顶点，就是$n$个连通分量。
|
||
|
||
（2）在$E$中选择权值最小的边$(u,v)$，并将此边从$E$中删除。
|
||
|
||
（3）如果$u$，$v$在$T$的不同的连通分量中，则将$(u,v)$加入到$T$中，从而导致$T$中减少一个连通分量。
|
||
|
||
（4）反复执行（2）（3）直到$T$中仅剩一个连通分量时，终止操作。
|
||
|
||
例题：
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
算法实现：
|
||
|
||
|
||
|
||
|
||
```c
|
||
namespace NonLinearStruct.Graph
|
||
{
|
||
/// <summary>
|
||
/// 表示图的边
|
||
/// </summary>
|
||
public class Edge
|
||
{
|
||
/// <summary>
|
||
/// 起点编号
|
||
/// </summary>
|
||
public int Begin { get; }
|
||
|
||
/// <summary>
|
||
/// 终点编号
|
||
/// </summary>
|
||
public int End { get; }
|
||
|
||
/// <summary>
|
||
/// 权值
|
||
/// </summary>
|
||
public double Weight { get; }
|
||
|
||
/// <summary>
|
||
/// 创建一个 Edge 类的新实例
|
||
/// </summary>
|
||
/// <param name="begin">起点编号</param>
|
||
/// <param name="end">终点编号</param>
|
||
/// <param name="weight">权值</param>
|
||
public Edge(int begin, int end, double weight = 0.0)
|
||
{
|
||
Begin = begin;
|
||
End = end;
|
||
Weight = weight;
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
```c
|
||
private Edge[] GetEdges()
|
||
{
|
||
for (int i = 0; i < VertexCount; i++)
|
||
_vertexList[i].Visited = false;
|
||
|
||
List<Edge> result = new List<Edge>();
|
||
|
||
for (int i = 0; i < VertexCount; i++)
|
||
{
|
||
_vertexList[i].Visited = true;
|
||
EdgeNode p = _vertexList[i].FirstNode;
|
||
while (p != null)
|
||
{
|
||
if (_vertexList[p.Index].Visited == false)
|
||
{
|
||
Edge edge = new Edge(i, p.Index, p.Weight);
|
||
result.Add(edge);
|
||
}
|
||
p = p.Next;
|
||
}
|
||
}
|
||
return result.OrderBy(a => a.Weight).ToArray();
|
||
}
|
||
|
||
private int Find(int[] parent, int f)
|
||
{
|
||
while (parent[f] > -1)
|
||
f = parent[f];
|
||
return f;
|
||
}
|
||
|
||
/// <summary>
|
||
/// 克鲁斯卡尔算法 最小生成树
|
||
/// </summary>
|
||
/// <returns></returns>
|
||
public SpanTreeNode[] MiniSpanTree()
|
||
{
|
||
int[] parent = new int[VertexCount];
|
||
for (int i = 0; i < VertexCount; i++)
|
||
{
|
||
parent[i] = -1;
|
||
}
|
||
SpanTreeNode[] tree = new SpanTreeNode[VertexCount];
|
||
Edge[] edges = GetEdges();
|
||
|
||
int count = 1;
|
||
for (int i = 0; i < edges.Length; i++)
|
||
{
|
||
int begin = edges[i].Begin;
|
||
int end = edges[i].End;
|
||
int b = Find(parent, begin);
|
||
int e = Find(parent, end);
|
||
if (b != e)
|
||
{
|
||
parent[e] = b;
|
||
tree[count] = new SpanTreeNode(_vertexList[end].VertexName,
|
||
_vertexList[begin].VertexName, edges[i].Weight);
|
||
count++;
|
||
}
|
||
}
|
||
for (int i = 0; i < parent.Length; i++)
|
||
{
|
||
if (parent[i] == -1)
|
||
{
|
||
tree[0] = new SpanTreeNode(_vertexList[i].VertexName, "NULL", 0.0);
|
||
break;
|
||
}
|
||
}
|
||
return tree;
|
||
}
|
||
```
|
||
|
||
---
|
||
## 6. 单源最短路径
|
||
|
||
### 6.1 定义
|
||
设$G=(V,E)$为连通网，$v$为源点，$v$到其余各顶点的最短路径问题即为单源最短路径问题。
|
||
|
||
|
||
### 6.2 迪杰特撕拉算法
|
||
|
||
$Dijkstra$（迪杰特斯拉）算法（按路径长度递增顺序构造的算法）：
|
||
|
||
初始时$s$为源点，$D_s=0$，$D_i= + \infty (i \neq s)$ ，标识$s$被访问。
|
||
|
||
（1）令$v=s$，$D_v=0$（$v$到$s$的路径长度）。
|
||
|
||
（2）依次考察$v$的未被访问的邻接点$\omega$，若$D_v+weight(v,\omega)<D_\omega $，则改变$D_\omega$的值，使$D_\omega=D_v+weight(v,\omega )$。
|
||
|
||
（3）在未被访问顶点中选择$D_v$最小的顶点$v$，访问$v$。
|
||
|
||
（4）重复（2）、（3）直至所有顶点都被访问。
|
||
|
||
例题：
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
算法实现：
|
||
|
||
|
||
|
||
|
||
```c
|
||
/// <summary>
|
||
/// 单源最短路径
|
||
/// </summary>
|
||
/// <param name="vName">寻找最短路径的源点</param>
|
||
/// <returns>源点到各个顶点的最短路径</returns>
|
||
public string ShortestPath(string vName)
|
||
{
|
||
int v = GetIndex(vName);
|
||
if (v == -1)
|
||
{
|
||
return string.Empty;
|
||
}
|
||
|
||
string result = string.Empty;
|
||
double[] dist = new double[VertexCount];
|
||
string[] path = new string[VertexCount];
|
||
//初始化
|
||
for (int i = 0; i < VertexCount; i++)
|
||
{
|
||
_vertexList[i].Visited = false;
|
||
dist[i] = double.MaxValue;
|
||
path[i] = _vertexList[v].VertexName;
|
||
}
|
||
dist[v] = 0.0;
|
||
_vertexList[v].Visited = true;
|
||
|
||
for (int i = 0; i < VertexCount - 1; i++)
|
||
{
|
||
EdgeNode p = _vertexList[v].FirstNode;
|
||
while (p != null)
|
||
{
|
||
if (_vertexList[p.Index].Visited == false
|
||
&& dist[v] + p.Weight < dist[p.Index])
|
||
{
|
||
dist[p.Index] = dist[v] + p.Weight;
|
||
path[p.Index] = path[v] + " ->" + _vertexList[p.Index].VertexName;
|
||
}
|
||
p = p.Next;
|
||
}
|
||
|
||
double min = double.MaxValue;
|
||
for (int j = 0; j < VertexCount; j++)
|
||
{
|
||
if (_vertexList[j].Visited == false && dist[j] < min)
|
||
{
|
||
min = dist[j];
|
||
v = j;
|
||
}
|
||
}
|
||
_vertexList[v].Visited = true;
|
||
}
|
||
|
||
for (int i = 0; i < VertexCount; i++)
|
||
{
|
||
result += path[i] + ":" + dist[i] + "\n";
|
||
}
|
||
|
||
return result;
|
||
}
|
||
```
|
||
|
||
|
||
---
|
||
## 7. 连通分量
|
||
|
||
例题：
|
||
|
||
|
||
|
||
|
||
|
||
可利用深度优先搜索，求非连通图的连通分量。
|
||
|
||
第一个：A，B，D，C；第二个：E，F；第三个：G，H，I
|
||
|
||
算法实现：
|
||
|
||
|
||
|
||
```c
|
||
/// <summary>
|
||
/// 得到连通分量
|
||
/// </summary>
|
||
/// <returns>连通分量</returns>
|
||
public string ConnectedComponent()
|
||
{
|
||
string result;
|
||
SLinkList<string> lst = new SLinkList<string>();
|
||
|
||
for (int i = 0; i < VertexCount; i++)
|
||
_vertexList[i].Visited = false;
|
||
|
||
for (int i = 0; i < VertexCount; i++)
|
||
{
|
||
if (_vertexList[i].Visited == false)
|
||
{
|
||
result = string.Empty;
|
||
//利用深度优先搜索求非连通图的连通分量
|
||
Dfs(i, ref result);
|
||
lst.InsertAtRear(result);
|
||
}
|
||
}
|
||
result = string.Empty;
|
||
for (int i = 0; i < lst.Length; i++)
|
||
{
|
||
result += "第" + i + "个连通分量为:\n" + lst[i];
|
||
}
|
||
return result;
|
||
}
|
||
```
|
||
|
||
---
|
||
## 8. 练习
|
||
|
||
根据要求完成程序代码：
|
||
|
||
给定纽约市附近的一幅简单地图，图中的顶点为城市，无向边代表两个城市的连通关系，边上的权为两城市之间的距离。
|
||
|
||
|
||
|
||
（1）对该图进行深度优先和广度优先搜索，并输出搜索序列（图的搜索问题）。
|
||
|
||
（2）在分析这张图后可以发现，任一对城市都是连通的。
|
||
|
||
第一个问题是：要用公路把所有城市连接起来，如何设计可使得工程的总造价最少（最小生成树问题）。
|
||
|
||
第二个问题是：要开车从一个城市到另外一个城市求其最短距离以及驱车路线（最短路径问题）。
|
||
|
||
|
||
解答：
|
||
|
||
数据TXT文件：
|
||
```c
|
||
Source,Target,Weight
|
||
San Rapheal,Cross,12
|
||
San Rapheal,Oakland,18
|
||
Cross,Daly Cit,3
|
||
Cross,San Franciso,3
|
||
Daly Cit,San Franciso,4
|
||
Daly Cit,Cross B,19
|
||
San Franciso,Oakland,7
|
||
San Franciso,San Mateo,21
|
||
Oakland,San Iarenzo,18
|
||
Oakland,Dublin,31
|
||
San Iarenzo,Hayward,3
|
||
San Iarenzo,Dublin,12
|
||
Cross B,San Mateo,4
|
||
Cross B,Cross C,7
|
||
San Mateo,Hayward,13
|
||
San Mateo,Redwood City,6
|
||
Hayward,Freemont,9
|
||
Dublin,San Jose,35
|
||
Redwood City,Cross C,5
|
||
Redwood City,Palo Alto,6
|
||
Cross C,Cupertin,14
|
||
Palo Alto,Freemont,9
|
||
Palo Alto,Mtn View,6
|
||
Freemont,San Jose,24
|
||
Mtn View,Cupertin,6
|
||
Mtn View,San Jose,8
|
||
Cupertin,San Jose,7
|
||
```
|
||
|
||
|
||
深度优先搜索序列：
|
||
```c
|
||
San Rapheal
|
||
Cross
|
||
Daly Cit
|
||
San Franciso
|
||
Oakland
|
||
San Iarenzo
|
||
Hayward
|
||
San Mateo
|
||
Cross B
|
||
Cross C
|
||
Redwood City
|
||
Palo Alto
|
||
Freemont
|
||
San Jose
|
||
Dublin
|
||
Mtn View
|
||
Cupertin
|
||
```
|
||
|
||
广度优先搜索序列：
|
||
|
||
```c
|
||
San Rapheal
|
||
Cross
|
||
Oakland
|
||
Daly Cit
|
||
San Franciso
|
||
San Iarenzo
|
||
Dublin
|
||
Cross B
|
||
San Mateo
|
||
Hayward
|
||
San Jose
|
||
Cross C
|
||
Redwood City
|
||
Freemont
|
||
Mtn View
|
||
Cupertin
|
||
Palo Alto
|
||
```
|
||
|
||
最小生成树：
|
||
|
||
```c
|
||
(NULL,San Rapheal) Weight:0
|
||
(San Rapheal,Cross) Weight:12
|
||
(Cross,Daly Cit) Weight:3
|
||
(Cross,San Franciso) Weight:3
|
||
(San Franciso,Oakland) Weight:7
|
||
(Oakland,San Iarenzo) Weight:18
|
||
(San Iarenzo,Hayward) Weight:3
|
||
(Hayward,Freemont) Weight:9
|
||
(Freemont,Palo Alto) Weight:9
|
||
(Palo Alto,Redwood City) Weight:6
|
||
(Redwood City,Cross C) Weight:5
|
||
(Redwood City,San Mateo) Weight:6
|
||
(San Mateo,Cross B) Weight:4
|
||
(Palo Alto,Mtn View) Weight:6
|
||
(Mtn View,Cupertin) Weight:6
|
||
(Cupertin,San Jose) Weight:7
|
||
(San Iarenzo,Dublin) Weight:12
|
||
|
||
最小生成树权值：116
|
||
```
|
||
|
||
最短路径：
|
||
|
||
```c
|
||
San Rapheal:0
|
||
San Rapheal ->Cross:12
|
||
San Rapheal ->Oakland:18
|
||
San Rapheal ->Cross ->Daly Cit:15
|
||
San Rapheal ->Cross ->San Franciso:15
|
||
San Rapheal ->Cross ->Daly Cit ->Cross B:34
|
||
San Rapheal ->Cross ->San Franciso ->San Mateo:36
|
||
San Rapheal ->Oakland ->San Iarenzo:36
|
||
San Rapheal ->Oakland ->San Iarenzo ->Dublin:48
|
||
San Rapheal ->Oakland ->San Iarenzo ->Hayward:39
|
||
San Rapheal ->Cross ->Daly Cit ->Cross B ->Cross C:41
|
||
San Rapheal ->Cross ->San Franciso ->San Mateo ->Redwood City:42
|
||
San Rapheal ->Oakland ->San Iarenzo ->Hayward ->Freemont:48
|
||
San Rapheal ->Cross ->San Franciso ->San Mateo ->Redwood City ->Palo Alto ->Mtn View ->San Jose:62
|
||
San Rapheal ->Cross ->San Franciso ->San Mateo ->Redwood City ->Palo Alto:48
|
||
San Rapheal ->Cross ->Daly Cit ->Cross B ->Cross C ->Cupertin:55
|
||
San Rapheal ->Cross ->San Franciso ->San Mateo ->Redwood City ->Palo Alto ->Mtn View:54
|
||
```
|
||
|