6.4 实际应用案例
6.4.1 图算法应用
基本概念
图算法是解决现实世界中各种网络结构问题的强大工具。图可以表示各种关系和连接，从社交网络到交通系统，从互联网到电力网络。
图算法在许多实际问题中都有广泛的应用，如社交网络分析、路由规划、网络流量分析等。
生活中的图算法应用
导航应用：
- 问题：如何从A地到B地找到最短或最快的路线
- 图表示：城市或路口作为节点，道路作为边，边的权重表示距离或时间
- 算法：Dijkstra算法、A*算法
社交网络：
- 问题：推荐可能认识的人，发现社区结构
- 图表示：用户作为节点，好友关系作为边
- 算法：广度优先搜索（BFS）、社区检测算法
电力网络：
- 问题：如何以最小成本连接所有变电站
- 图表示：变电站作为节点，电缆作为边，边的权重表示建设成本
- 算法：最小生成树算法（Kruskal、Prim）
常见的图算法应用
最短路径算法：
- 应用：导航系统、网络路由、物流配送
- 算法：Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法
- 生活例子：地图应用找最短路线、网络数据包路由
最小生成树算法：
- 应用：网络设计、聚类分析、电路设计
- 算法：Kruskal算法、Prim算法
- 生活例子：设计最小成本的电缆网络连接所有建筑
网络流算法：
- 应用：资源分配、交通规划、供应链优化
- 算法：Ford-Fulkerson算法、Edmonds-Karp算法
- 生活例子：水管网络中的最大流量、道路网络的最大通行能力
图匹配算法：
- 应用：任务分配、人员调度、婚配问题
- 算法：匈牙利算法、Hopcroft-Karp算法
- 生活例子：求职者与职位的最佳匹配、学生与宿舍的分配
Dijkstra算法实现导航系统
问题描述：
- 给定一个城市地图（用加权图表示）
- 找出从起点到其他所有点的最短路径
图解：
B
/|\
/ | \
2 | 3
/ | \
A 1 D
\ | /
5 | 1
\ | /
\|/
C
Dijkstra算法步骤：
初始化：
- 起点A到自身距离为0
- 起点A到其他所有点的距离设为无穷大
- 所有点标记为未访问
当有未访问的点时，重复：
- 选择未访问点中距离最小的点（第一次是起点A）
- 标记该点为已访问
- 更新该点的所有邻居的距离
执行过程（从A开始）：
初始状态：dist[A]=0, dist[B]=∞, dist[C]=∞, dist[D]=∞
选择A（距离最小的未访问点）：
- 更新A的邻居：dist[B]=2, dist[C]=5
- 标记A为已访问
选择B（距离最小的未访问点）：
- 更新B的邻居：dist[C]=min(5,2+1)=3, dist[D]=2+3=5
- 标记B为已访问
选择C（距离最小的未访问点）：
- 更新C的邻居：dist[D]=min(5,3+1)=4
- 标记C为已访问
选择D（距离最小的未访问点）：
- D没有未访问的邻居
- 标记D为已访问
最终结果：dist[A]=0, dist[B]=2, dist[C]=3, dist[D]=4
Java实现：
public static int[] dijkstra(int[][] graph, int start) {
int n = graph.length;
int[] dist = new int[n]; // 存储起点到各点的最短距离
boolean[] visited = new boolean[n]; // 标记点是否已访问
// 初始化距离数组
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0; // 起点到自身的距离为0
// 对每个顶点进行处理
for (int i = 0; i < n; i++) {
// 找到未访问的最近顶点
int u = -1;
int minDist = Integer.MAX_VALUE;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
// 如果没有可达的未访问顶点，结束算法
if (u == -1) break;
visited[u] = true;
// 更新所有邻接顶点的距离
for (int v = 0; v < n; v++) {
// 条件：v未访问 && u到v有边 && u可达 && 经过u到v的路径更短
if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
&& dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v]; // 更新距离
}
}
}
return dist; // 返回起点到所有点的最短距离
}
使用示例：
public static void main(String[] args) {
// 示例图的邻接矩阵表示
// 0表示没有直接连接，其他值表示边的权重
int[][] graph = {
{0, 2, 5, 0}, // A的邻接关系
{2, 0, 1, 3}, // B的邻接关系
{5, 1, 0, 1}, // C的邻接关系
{0, 3, 1, 0} // D的邻接关系
};
int start = 0; // 起点A
int[] distances = dijkstra(graph, start);
// 打印结果
System.out.println("从顶点" + start + "到各顶点的最短距离：");
for (int i = 0; i < distances.length; i++) {
System.out.println("到顶点" + i + "的距离: " +
(distances[i] == Integer.MAX_VALUE ? "不可达" : distances[i]));
}
}
其他图算法示例
Prim算法（最小生成树）：
- 应用：设计最小成本的网络连接所有节点
- 工作原理：从一个起始顶点开始，逐步添加最小权重的边，直到所有顶点都连接
广度优先搜索（BFS）：
- 应用：寻找最短路径（无权图）、社交网络中的"六度分隔"
- 工作原理：从起点开始，先访问所有相邻节点，然后再访问下一层节点
深度优先搜索（DFS）：
- 应用：拓扑排序、寻找连通分量、迷宫问题
- 工作原理：从起点开始，尽可能深入图中，直到无法继续前进时回溯
应用场景
交通规划：
- 最短路径算法用于导航
- 最大流算法用于分析道路网络容量
- 最小生成树算法用于设计公交线路
社交网络分析：
- 中心性算法识别有影响力的人物
- 社区检测算法发现紧密联系的群体
- 推荐系统基于图结构推荐朋友或内容
计算机网络：
- 路由算法确定数据包传输路径
- 网络设计算法优化网络拓扑
- 负载均衡算法分配网络流量
生物信息学：
- 蛋白质相互作用网络分析
- 基因调控网络建模
- 代谢通路分析
6.4.2 字符串处理算法
字符串处理算法在文本编辑、生物信息学、网络搜索等领域有广泛的应用。
常见的字符串处理算法包括：
- 字符串匹配算法：如KMP算法、Boyer-Moore算法、Rabin-Karp算法等。
- 字符串编辑距离算法：如Levenshtein距离、Hamming距离等。
- 后缀树和后缀数组：用于快速字符串查找和分析。
- 字符串压缩算法：如Huffman编码、Lempel-Ziv算法等。
示例：实现KMP字符串匹配算法。
public static int kmpSearch(String text, String pattern) {
int m = pattern.length();
int n = text.length();
// 如果模式串为空，返回0
if (m == 0) return 0;
// 计算部分匹配表
int[] lps = computeLPSArray(pattern);
int i = 0; // text的索引
int j = 0; // pattern的索引
while (i < n) {
if (pattern.charAt(j) == text.charAt(i)) {
i++;
j++;
}
if (j == m) {
// 找到匹配，返回起始索引
return i - j;
} else if (i < n && pattern.charAt(j) != text.charAt(i)) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return -1; // 未找到匹配
}
private static int[] computeLPSArray(String pattern) {
int m = pattern.length();
int[] lps = new int[m];
int len = 0;
int i = 1;
while (i < m) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}