2.Bellman-Fird算法
2.1Bellman-Fird算法c++代码示例
#include <iostream> #include <vector> #include <climits> using namespace std; // 定义无穷大表示距离为未确定状态 const int INF = INT_MAX; // Bellman-Ford算法实现 void bellmanFord(vector<vector<int>>& graph, int source) { int numVertices = graph.size(); // 创建距离数组，用于存储源节点到各个节点的最短距离 vector<int> distance(numVertices, INF); // 设置源节点的距离为0 distance[source] = 0; // 对每条边进行V-1次松弛操作 for (int i = 0; i < numVertices - 1; ++i) { // 遍历所有边，并进行松弛操作 for (int u = 0; u < numVertices; ++u) { for (int v = 0; v < numVertices; ++v) { if (graph[u][v] != 0 && distance[u] != INF && distance[u] + graph[u][v] < distance[v]) { distance[v] = distance[u] + graph[u][v]; } } } } // 检测是否存在负权回路 for (int u = 0; u < numVertices; ++u) { for (int v = 0; v < numVertices; ++v) { if (graph[u][v] != 0 && distance[u] != INF && distance[u] + graph[u][v] < distance[v]) { cout << "Negative cycle detected!" << endl; return; } } } // 输出节点距离 cout << "Bellman-Ford Algorithm" << endl; cout << "Shortest Distance from Source Node to Each Node:" << endl; for (int v = 0; v < numVertices; ++v) { cout << "Node " << v << ": " << distance[v] << endl; } } int main() { int numVertices = 5; vector<vector<int>> graph = { {0, -1, 4, 0, 0}, {0, 0, 3, 2, 2}, {0, 0, 0, 0, 0}, {0, 1, 5, 0, 0}, {0, 0, 0, -3, 0} }; bellmanFord(graph, 0); return 0; }
2.2Bellman-Fird算法的c代码和python代码示例
#include <stdio.h> #include <stdbool.h> #include <limits.h> #define INF INT_MAX struct Edge { int source, destination, weight; }; void bellmanFord(struct Edge graph[], int numVertices, int numEdges, int source) { int distance[numVertices]; // 初始化所有节点的距离为无穷大 for (int i = 0; i < numVertices; ++i) { distance[i] = INF; } // 设置源节点的距离为0 distance[source] = 0; // 进行V-1次松弛操作 for (int i = 0; i < numVertices - 1; ++i) { // 遍历所有边，并进行松弛操作 for (int j = 0; j < numEdges; ++j) { int u = graph[j].source; int v = graph[j].destination; int weight = graph[j].weight; if (distance[u] != INF && distance[u] + weight < distance[v]) { distance[v] = distance[u] + weight; } } } // 检测是否存在负权回路 for (int i = 0; i < numEdges; ++i) { int u = graph[i].source; int v = graph[i].destination; int weight = graph[i].weight; if (distance[u] != INF && distance[u] + weight < distance[v]) { printf("Negative cycle detected!\n"); return; } } printf("Bellman-Ford Algorithm\n"); printf("Shortest Distance from Source Node to Each Node:\n"); for (int i = 0; i < numVertices; ++i) { printf("Node %d: %d\n", i, distance[i]); } } int main() { int numVertices = 5; int numEdges = 7; struct Edge graph[] = { {0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2}, {1, 4, 2}, {3, 1, 1}, {4, 3, -3} }; int source = 0; bellmanFord(graph, numVertices, numEdges, source); return 0; }
def bellmanFord(graph, numVertices, numEdges, source): distance = [float('inf')] * numVertices distance[source] = 0 for i in range(numVertices - 1): for j in range(numEdges): u = graph[j][0] v = graph[j][1] weight = graph[j][2] if distance[u] != float('inf') and distance[u] + weight < distance[v]: distance[v] = distance[u] + weight for i in range(numEdges): u = graph[i][0] v = graph[i][1] weight = graph[i][2] if distance[u] != float('inf') and distance[u] + weight < distance[v]: print("Negative cycle detected!") return print("Bellman-Ford Algorithm") print("Shortest Distance from Source Node to Each Node:") for i in range(numVertices): print("Node", i, ":", distance[i]) numVertices = 5 numEdges = 7 graph = [ [0, 1, -1], [0, 2, 4], [1, 2, 3], [1, 3, 2], [1, 4, 2], [3, 1, 1], [4, 3, -3] ] source = 0 bellmanFord(graph, numVertices, numEdges, source)
五.最大流最小割
最大流最小割（Max-flow min-cut）是网络流问题中的一个经典概念和定理。
在一个网络流问题中，我们有一个有向图，其中每条边都有一个容量限制，表示该边可以传输的最大流量。网络中有一个源节点和一个汇节点，我们的目标是从源节点将尽可能多的流量送到汇节点。最大流最小割定理指出，最大流的值等于最小割的值。
割（cut）是指将网络图中的节点分为两部分的一条边集。一个割将源节点和汇节点分别放在两侧。割的容量（cut capacity）是指这些边的容量之和，也就是从源节点指向割的边的容量之和。最小割（minimum cut）是指割的容量最小的割。
最大流最小割定理的关键观察是：在最大流情况下，流量从源节点到汇节点会被割截成不同的路径，并且割的容量等于最大流的值。换句话说，最大流的值是网络中任何割的容量的下限。这也意味着想要找到最大流，只需要找到任何一个割，使得割的容量等于最大流的值。
最大流最小割算法是一类用于求解网络流问题的算法，其中最著名的算法是Edmonds-Karp算法和Ford-Fulkerson算法，它们都基于不断寻找增广路径来求解最大流问题。这些算法在实际应用中被广泛使用，例如在网络通信、交通流量调度和图像分割等领域。
1.Edmonds-Karp算法
Edmonds-Karp算法是用于解决最大流最小割问题的一个经典算法。它是基于最大流最小割定理的一种实现方法。
最大流最小割定理指出，一个图的最大流的值等于图中任意一个割的容量。割将图的节点分为两个部分，并且割的容量等于从源节点指向割的边的容量之和。因此，为了找到图的最大流，我们只需找到任意一个割，使其容量等于最大流的值。
Edmonds-Karp算法利用广度优先搜索（BFS）来寻找增广路径，并通过不断更新剩余容量来增加流量。它遍历图中的所有增广路径，每次寻找到一条从源节点到汇节点的增广路径，就将该路径上的最小剩余容量作为流量增加到当前的最大流中。这个过程不断重复，直到不存在从源节点到汇节点的增广路径为止。最终得到的最大流就是图的最大流。
因此，可以说Edmonds-Karp算法是一种用于求解最大流最小割问题的具体算法实现。它是一种有效而且常用的算法，在实际应用中广泛被使用。
1.1Edmonds-Karp算法c++代码示例
#include <iostream> #include <queue> #include <limits.h> #define V 6 // 定义图的节点数量 // 使用邻接矩阵来表示图的边 int graph[V][V] = { {0, 16, 13, 0, 0, 0}, {0, 0, 10, 12, 0, 0}, {0, 4, 0, 0, 14, 0}, {0, 0, 9, 0, 0, 20}, {0, 0, 0, 7, 0, 4}, {0, 0, 0, 0, 0, 0} }; bool bfs(int residualGraph[V][V], int source, int sink, int parent[]) { bool visited[V]; memset(visited, 0, sizeof(visited)); std::queue<int> q; q.push(source); visited[source] = true; parent[source] = -1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 0; v < V; ++v) { if (!visited[v] && residualGraph[u][v] > 0) { q.push(v); parent[v] = u; visited[v] = true; } } } return visited[sink]; } int edmondsKarp(int source, int sink) { int residualGraph[V][V]; for (int u = 0; u < V; ++u) { for (int v = 0; v < V; ++v) { residualGraph[u][v] = graph[u][v]; } } int maxFlow = 0; int parent[V]; while (bfs(residualGraph, source, sink, parent)) { int pathFlow = INT_MAX; // 找到增广路径上的最小剩余容量 for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; pathFlow = std::min(pathFlow, residualGraph[u][v]); } // 更新增广路径上的边的剩余容量 for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; residualGraph[u][v] -= pathFlow; residualGraph[v][u] += pathFlow; } maxFlow += pathFlow; } return maxFlow; } int main() { int source = 0; int sink = 5; int maxFlow = edmondsKarp(source, sink); std::cout << "Max Flow: " << maxFlow << std::endl; return 0; }
这段C++代码实现了Edmonds-Karp算法来求解最大流问题。算法的关键在于不断寻找增广路径并更新剩余容量。
首先，定义了一个邻接矩阵graph来表示图的边，其中graph[u][v]表示节点u到节点v之间的容量限制。
然后，在bfs函数中使用广度优先搜索（BFS）来寻找增广路径。该函数维护一个队列，并记录每个节点是否被访问过。当存在未访问节点且存在剩余容量的边时，将该节点加入队列，并标记为已访问。同时，记录节点的父节点，以便构造增广路径。
在edmondsKarp函数中，创建一个初始的剩余图residualGraph，并初始化最大流为0。然后，利用bfs函数寻找增广路径，如果找到了从源节点到汇节点的路径，则计算该路径上的最小剩余容量。接着，更新增广路径上的边的剩余容量，并将最小剩余容量累加到最大流中。重复以上操作，直到不存在从源节点到汇节点的增广路径。
最后，在main函数中设置源节点和汇节点，并调用edmondsKarp函数来计算最大流。打印结果即为最大流的值。
该算法的时间复杂度为O(V * E^2)，其中V是节点数量，E是边数量。算法使用BFS来寻找增广路径，因此最坏情况下每次BFS操作的时间复杂度为O(E)。在最多O(V)次BFS操作中，可能会进行O(E)次更新操作。因此，总体时间复杂度为O(V * E^2)。
1.2Edmonds-Karp算法的c代码和python代码示例
#include <stdio.h> #include <stdbool.h> #include <limits.h> #define V 6 // 定义图的节点数量 // 使用邻接矩阵来表示图的边 int graph[V][V] = { {0, 16, 13, 0, 0, 0}, {0, 0, 10, 12, 0, 0}, {0, 4, 0, 0, 14, 0}, {0, 0, 9, 0, 0, 20}, {0, 0, 0, 7, 0, 4}, {0, 0, 0, 0, 0, 0} }; bool bfs(int residualGraph[V][V], int source, int sink, int parent[]) { bool visited[V]; memset(visited, 0, sizeof(visited)); int queue[V]; int front = 0, rear = 0; queue[rear++] = source; visited[source] = true; parent[source] = -1; while (front != rear) { int u = queue[front++]; for (int v = 0; v < V; ++v) { if (!visited[v] && residualGraph[u][v] > 0) { queue[rear++] = v; parent[v] = u; visited[v] = true; } } } return visited[sink]; } int edmondsKarp(int source, int sink) { int residualGraph[V][V]; for (int u = 0; u < V; ++u) { for (int v = 0; v < V; ++v) { residualGraph[u][v] = graph[u][v]; } } int maxFlow = 0; int parent[V]; while (bfs(residualGraph, source, sink, parent)) { int pathFlow = INT_MAX; // 找到增广路径上的最小剩余容量 for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; pathFlow = (pathFlow < residualGraph[u][v]) ? pathFlow : residualGraph[u][v]; } // 更新增广路径上的边的剩余容量 for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; residualGraph[u][v] -= pathFlow; residualGraph[v][u] += pathFlow; } maxFlow += pathFlow; } return maxFlow; } int main() { int source = 0; int sink = 5; int maxFlow = edmondsKarp(source, sink); printf("Max Flow: %d\n", maxFlow); return 0; }
from collections import deque V = 6 # 定义图的节点数量 # 使用邻接矩阵来表示图的边 graph = [ [0, 16, 13, 0, 0, 0], [0, 0, 10, 12, 0, 0], [0, 4, 0, 0, 14, 0], [0, 0, 9, 0, 0, 20], [0, 0, 0, 7, 0, 4], [0, 0, 0, 0, 0, 0] ] def bfs(residualGraph, source, sink, parent): visited = [False] * V queue = deque() queue.append(source) visited[source] = True parent[source] = -1 while queue: u = queue.popleft() for v in range(V): if not visited[v] and residualGraph[u][v] > 0: queue.append(v) parent[v] = u visited[v] = True return visited[sink] def edmondsKarp(source, sink): residualGraph = [row[:] for row in graph] maxFlow = 0 parent = [None] * V while bfs(residualGraph, source, sink, parent): pathFlow = float('inf') # 找到增广路径上的最小剩余容量 v = sink while v != source: u = parent[v] pathFlow = min(pathFlow, residualGraph[u][v]) v = parent[v] # 更新增广路径上的边的剩余容量 v = sink while v != source: u = parent[v] residualGraph[u][v] -= pathFlow residualGraph[v][u] += pathFlow v = parent[v] maxFlow += pathFlow return maxFlow source = 0 sink = 5 maxFlow = edmondsKarp(source, sink) print("Max Flow:", maxFlow)
2.Ford-Fulkerson算法
Ford-Fulkerson算法是一种用于解决最大流问题的经典算法。该算法通过不断寻找增广路径，并更新路径上的边的流量来逐步增加流量，直到找不到更多的增广路径为止。最终得到的流量即为图的最大流。
算法的基本思想是从初始流量为0的图开始，重复以下步骤：
1. 使用深度优先搜索（DFS）或广度优先搜索（BFS）在残余图中寻找一条从源节点到汇节点的增广路径。增广路径是指路径上所有边的剩余容量大于0，并且路径中的最小剩余容量定义了该路径的瓶颈。
2. 如果找到增广路径，则通过该路径上的瓶颈值来增加流量。具体做法是遍历增广路径上的每条边，将瓶颈值加到该边的流量上，并且将瓶颈值作为反向边的流量进行减少。
3. 重复步骤1和步骤2，直到找不到增广路径。此时，算法终止，并且得到的最大流即为图的最大流。
Ford-Fulkerson算法的关键在于如何选择增广路径。在每次搜索增广路径时，可以使用DFS或BFS来寻找路径，具体取决于选择哪种搜索策略。此外，也可以使用不同的策略来选择增广路径，例如随机选择或优先选择剩余容量最大的路径。
需要注意的是，Ford-Fulkerson算法的时间复杂度取决于增广路径的选择策略。在最坏的情况下，其时间复杂度可能会非常高，但通过使用一些优化技巧，如Edmonds-Karp算法中的BFS，可以将时间复杂度限制在O(V^2E)，其中V是节点数量，E是边数量。
Ford-Fulkerson算法是解决最大流问题的经典算法，对于许多流网络应用都是有效并可行的。
2.1Ford-Fulkerson算法c++代码示例
#include <iostream> #include <vector> #include <queue> #include <limits.h> using namespace std; // 定义图的边的数据结构 struct Edge { int v; // 边的终点 int capacity; // 边的容量 int flow; // 边的当前流量 int reverse; // 反向边在邻接表中的下标 }; // 使用邻接表来表示图 class Graph { private: int V; // 图的节点数量 vector<vector<Edge>> adjacencyList; // 邻接表 public: Graph(int V) { this->V = V; adjacencyList.resize(V); } // 添加边到邻接表中 void addEdge(int u, int v, int capacity) { Edge directEdge = { v, capacity, 0, adjacencyList[v].size() }; Edge reverseEdge = { u, 0, 0, adjacencyList[u].size() }; adjacencyList[u].push_back(directEdge); adjacencyList[v].push_back(reverseEdge); } // 使用BFS寻找从源节点到汇节点的增广路径，并返回是否找到路径 bool bfs(int source, int sink, vector<int>& parent) { vector<bool> visited(V, false); queue<int> q; q.push(source); visited[source] = true; parent[source] = -1; while (!q.empty()) { int u = q.front(); q.pop(); for (const auto& edge : adjacencyList[u]) { int v = edge.v; int capacity = edge.capacity; int flow = edge.flow; if (!visited[v] && capacity > flow) { q.push(v); parent[v] = u; visited[v] = true; } } } return visited[sink]; } // 使用DFS遍历增广路径，并更新路径上的边的流量 int dfs(int u, int sink, int minCapacity, vector<int>& parent) { if (u == sink) return minCapacity; for (auto& edge : adjacencyList[u]) { int v = edge.v; int capacity = edge.capacity; int flow = edge.flow; int reverse = edge.reverse; if (capacity > flow && parent[v] == u) { int updatedFlow = dfs(v, sink, min(minCapacity, capacity - flow), parent); if (updatedFlow > 0) { edge.flow += updatedFlow; adjacencyList[v][reverse].flow -= updatedFlow; return updatedFlow; } } } return 0; } // 使用Ford-Fulkerson算法求解最大流 int fordFulkerson(int source, int sink) { vector<int> parent(V, -1); // 存储路径的父节点 int maxFlow = 0; while (bfs(source, sink, parent)) { int minCapacity = INT_MAX; // 在增广路径上找到瓶颈值（最小剩余容量） for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; for (auto& edge : adjacencyList[u]) { if (edge.v == v) { minCapacity = min(minCapacity, edge.capacity - edge.flow); break; } } } // 更新增广路径上的边的流量 for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; for (auto& edge : adjacencyList[u]) { if (edge.v == v) { edge.flow += minCapacity; adjacencyList[v][edge.reverse].flow -= minCapacity; break; } } } maxFlow += minCapacity; } return maxFlow; } }; int main() { int V = 6; // 图的节点数量 Graph graph(V); // 添加边到图中 graph.addEdge(0, 1, 16); graph.addEdge(0, 2, 13); graph.addEdge(1, 2, 10); graph.addEdge(1, 3, 12); graph.addEdge(2, 1, 4); graph.addEdge(2, 4, 14); graph.addEdge(3, 2, 9); graph.addEdge(3, 5, 20); graph.addEdge(4, 3, 7); graph.addEdge(4, 5, 4); int source = 0; int sink = 5; int maxFlow = graph.fordFulkerson(source, sink); cout << "Max Flow: " << maxFlow << endl; return 0; }
该代码使用了邻接表来表示图，使用了Edge结构体来存储边的信息，包括终点、容量、流量和反向边的下标。Graph类实现了添加边、使用BFS查找增广路径、使用DFS遍历增广路径和主要的Ford-Fulkerson算法函数。在main函数中创建了一个Graph对象，并添加了边。然后调用fordFulkerson函数来计算最大流，并输出结果。
Ford-Fulkerson算法的核心思想就是不断寻找增广路径并更新路径上的边的流量，直到找不到增广路径为止。其中，BFS用于寻找增广路径，DFS用于遍历增广路径。通过不断地更新路径上的边的流量，最终得到的流量即为图的最大流。
2.2Ford-Fulkerson算法的c代码和python代码示例
#include <stdio.h> #include <stdbool.h> #include <limits.h> #define V 6 // 边的数据结构 struct Edge { int v; // 边的终点 int capacity; // 边的容量 int flow; // 边的当前流量 int reverse; // 反向边的下标 }; // 图的数据结构 struct Graph { int numNodes; // 节点数量 struct Edge *adjacencyList[V]; // 邻接表 }; // 创建边 struct Edge *createEdge(int v, int capacity, int reverse) { struct Edge *edge = (struct Edge *)malloc(sizeof(struct Edge)); edge->v = v; edge->capacity = capacity; edge->flow = 0; edge->reverse = reverse; return edge; } // 添加边到图中 void addEdge(struct Graph *graph, int u, int v, int capacity) { graph->adjacencyList[u] = createEdge(v, capacity, graph->adjacencyList[v] ? graph->adjacencyList[v]->reverse : 0); graph->adjacencyList[v] = createEdge(u, 0, graph->adjacencyList[u] ? graph->adjacencyList[u]->reverse : 0); } // 使用BFS寻找从源节点到汇节点的增广路径，并返回是否找到路径 bool bfs(struct Graph *graph, int source, int sink, int parent[]) { bool visited[V] = { false }; int queue[V]; int front = 0, rear = 0; visited[source] = true; parent[source] = -1; queue[rear++] = source; while (front < rear) { int u = queue[front++]; for (struct Edge *edge = graph->adjacencyList[u]; edge != NULL; edge = graph->adjacencyList[u]) { int v = edge->v; int capacity = edge->capacity; int flow = edge->flow; if (!visited[v] && capacity > flow) { parent[v] = u; visited[v] = true; queue[rear++] = v; } u = edge->v; } } return visited[sink]; } // 使用DFS遍历增广路径，并更新路径上的边的流量 int dfs(struct Graph *graph, int u, int sink, int minCapacity, int parent[]) { if (u == sink) return minCapacity; for (struct Edge *edge = graph->adjacencyList[u]; edge != NULL; edge = graph->adjacencyList[u]) { int v = edge->v; int capacity = edge->capacity; int flow = edge->flow; int reverse = edge->reverse; if (capacity > flow && parent[v] == u) { int updatedFlow = dfs(graph, v, sink, min(minCapacity, capacity - flow), parent); if (updatedFlow > 0) { edge->flow += updatedFlow; graph->adjacencyList[v]->flow -= updatedFlow; return updatedFlow; } } u = edge->v; } return 0; } // 使用Ford-Fulkerson算法求解最大流 int fordFulkerson(struct Graph *graph, int source, int sink) { int parent[V]; int maxFlow = 0; while (bfs(graph, source, sink, parent)) { int minCapacity = INT_MAX; // 在增广路径上找到瓶颈值（最小剩余容量） for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; struct Edge *edge = graph->adjacencyList[u]; while (edge && edge->v != v) { edge = graph->adjacencyList[u]; } if (edge) { minCapacity = min(minCapacity, edge->capacity - edge->flow); } } // 更新增广路径上的边的流量 for (int v = sink; v != source; v = parent[v]) { int u = parent[v]; struct Edge *edge = graph->adjacencyList[u]; while (edge && edge->v != v) { edge = graph->adjacencyList[u]; } if (edge) { edge->flow += minCapacity; graph->adjacencyList[v]->flow -= minCapacity; } } maxFlow += minCapacity; } return maxFlow; } int main() { struct Graph graph; graph.numNodes = V; for (int i = 0; i < V; i++) { graph.adjacencyList[i] = NULL; } // 添加边到图中 addEdge(&graph, 0, 1, 16); addEdge(&graph, 0, 2, 13); addEdge(&graph, 1, 2, 10); addEdge(&graph, 1, 3, 12); addEdge(&graph, 2, 1, 4); addEdge(&graph, 2, 4, 14); addEdge(&graph, 3, 2, 9); addEdge(&graph, 3, 5, 20); addEdge(&graph, 4, 3, 7); addEdge(&graph, 4, 5, 4); int source = 0; int sink = 5; int maxFlow = fordFulkerson(&graph, source, sink); printf("Max Flow: %d\n", maxFlow); return 0; }
from collections import defaultdict class Graph: def __init__(self, numNodes): self.numNodes = numNodes self.adjacencyList = defaultdict(list) def addEdge(self, u, v, capacity): directEdge = {"v": v, "capacity": capacity, "flow": 0, "reverse": len(self.adjacencyList[v])} reverseEdge = {"v": u, "capacity": 0, "flow": 0, "reverse": len(self.adjacencyList[u])} self.adjacencyList[u].append(directEdge) self.adjacencyList[v].append(reverseEdge) def bfs(self, source, sink, parent): visited = [False] * self.numNodes queue = [] queue.append(source) visited[source] = True parent[source] = -1 while queue: u = queue.pop(0) for edge in self.adjacencyList[u]: v = edge["v"] capacity = edge["capacity"] flow = edge["flow"] if not visited[v] and capacity > flow: queue.append(v) parent[v] = u visited[v] = True return visited[sink] def dfs(self, u, sink, minCapacity, parent): if u == sink: return minCapacity for edge in self.adjacencyList[u]: v = edge["v"] capacity = edge["capacity"] flow = edge["flow"] reverse = edge["reverse"] if capacity > flow and parent[v] == u: updatedFlow = self.dfs(v, sink, min(minCapacity, capacity - flow), parent) if updatedFlow > 0: edge["flow"] += updatedFlow self.adjacencyList[v][reverse]["flow"] -= updatedFlow return updatedFlow return 0 def fordFulkerson(self, source, sink): parent = [-1] * self.numNodes maxFlow = 0 while self.bfs(source, sink, parent): minCapacity = float("inf") for v in range(sink, source, -1): u = parent[v] for edge in self.adjacencyList[u]: if edge["v"] == v: minCapacity = min(minCapacity, edge["capacity"] - edge["flow"]) break for v in range(sink, source, -1): u = parent[v] for edge in self.adjacencyList[u]: if edge["v"] == v: edge["flow"] += minCapacity self.adjacencyList[v][edge["reverse"]]["flow"] -= minCapacity break maxFlow += minCapacity return maxFlow if __name__ == "__main__": V = 6 # 节点数量 graph = Graph(V) # 添加边到图中 graph.addEdge(0, 1, 16) graph.addEdge(0, 2, 13) graph.addEdge(1, 2, 10) graph.addEdge(1, 3, 12) graph.addEdge(2, 1, 4) graph.addEdge(2, 4, 14) graph.addEdge(3, 2, 9) graph.addEdge(3, 5, 20) graph.addEdge(4, 3, 7) graph.addEdge(4, 5, 4) source = 0 sink = 5 maxFlow = graph.fordFulkerson(source, sink) print("Max Flow:", maxFlow)
六.拓扑排序
拓扑排序是一种对有向无环图（DAG）中的节点进行排序的算法。在拓扑排序中，节点表示任务或事件，有向边表示任务之间的依赖关系。拓扑排序的目的是将任务按照依赖关系的顺序进行排序，使得任何一个任务的前置任务都排在它的前面。
具体来说，拓扑排序的过程如下：
1. 找到图中入度为0的节点（即没有依赖的节点），将其加入结果列表中。
2. 删除该节点，并更新与该节点相邻的节点的入度，即将它们的入度减1。
3. 重复步骤1和步骤2，直到图中所有节点都被处理过。
如果拓扑排序能够成功完成，那么结果列表中的节点顺序就是一种满足依赖关系的排序。拓扑排序常用于任务调度、编译顺序等场景。请注意，拓扑排序只适用于有向无环图，若图中存在环路，则无法进行拓扑排序。
1.拓扑c++代码示例
#include <iostream> #include <vector> #include <queue> using namespace std; vector<int> topologicalSort(vector<vector<int>>& graph) { int numNodes = graph.size(); // 统计每个节点的入度 vector<int> inDegrees(numNodes, 0); for (int i = 0; i < numNodes; i++) { for (auto neighbor : graph[i]) { inDegrees[neighbor]++; } } // 使用队列来存储入度为0的节点 queue<int> q; for (int i = 0; i < numNodes; i++) { if (inDegrees[i] == 0) { q.push(i); } } // 进行拓扑排序的结果数组 vector<int> result; // 开始拓扑排序 while (!q.empty()) { int node = q.front(); q.pop(); result.push_back(node); // 将当前节点加入结果数组 // 更新相邻节点的入度 for (auto neighbor : graph[node]) { inDegrees[neighbor]--; // 如果入度为0，则将其加入队列中 if (inDegrees[neighbor] == 0) { q.push(neighbor); } } } return result; } int main() { vector<vector<int>> graph = {{1, 2}, {3}, {3, 4}, {4}, {}}; vector<int> result = topologicalSort(graph); cout << "拓扑排序结果: "; for (int node : result) { cout << node << " "; } return 0; }
这段代码首先统计了每个节点的入度，然后利用队列存储入度为0的节点。然后从队列中取出一个节点，并将其加入结果数组中。接着遍历该节点的相邻节点，将相邻节点的入度减1，并将入度减为0的节点加入队列。如此循环，直到队列为空，所有节点都按照拓扑排序的顺序加入到结果数组中。
最后，将结果数组输出即可得到拓扑排序的结果。
2.拓扑排序的c代码和python代码示例
#include <stdio.h> #include <stdlib.h> #define MAX_NODES 100 // 定义图的数据结构 struct Graph { int numNodes; int adjacencyMatrix[MAX_NODES][MAX_NODES]; }; // 初始化图 void initGraph(struct Graph* graph, int numNodes) { graph->numNodes = numNodes; for (int i = 0; i < numNodes; i++) { for (int j = 0; j < numNodes; j++) { graph->adjacencyMatrix[i][j] = 0; } } } // 添加边 void addEdge(struct Graph* graph, int start, int end) { graph->adjacencyMatrix[start][end] = 1; } // 拓扑排序 void topologicalSort(struct Graph* graph, int node, int* visited, int* result, int* index) { visited[node] = 1; for (int i = 0; i < graph->numNodes; i++) { if (graph->adjacencyMatrix[node][i] == 1 && visited[i] == 0) { topologicalSort(graph, i, visited, result, index); } } result[*index] = node; (*index)--; } // 调用拓扑排序算法进行排序 void performTopologicalSort(struct Graph* graph) { int numNodes = graph->numNodes; int visited[MAX_NODES] = {0}; int result[MAX_NODES]; int index = numNodes - 1; for (int i = 0; i < numNodes; i++) { if (visited[i] == 0) { topologicalSort(graph, i, visited, result, &index); } } printf("拓扑排序结果: "); for (int i = 0; i < numNodes; i++) { printf("%d ", result[i]); } printf("\n"); } int main() { // 创建一个图对象，并初始化 struct Graph graph; initGraph(&graph, 5); // 添加边 addEdge(&graph, 0, 1); addEdge(&graph, 0, 2); addEdge(&graph, 1, 3); addEdge(&graph, 2, 3); addEdge(&graph, 2, 4); addEdge(&graph, 3, 4); // 进行拓扑排序 performTopologicalSort(&graph); return 0; }
from collections import deque # 拓扑排序 def topologicalSort(graph): numNodes = len(graph) # 统计每个节点的入度 inDegrees = [0] * numNodes for neighbors in graph.values(): for neighbor in neighbors: inDegrees[neighbor] += 1 # 使用队列来存储入度为0的节点 queue = deque() for node in range(numNodes): if inDegrees[node] == 0: queue.append(node) # 进行拓扑排序的结果列表 result = [] # 开始拓扑排序 while queue: node = queue.popleft() result.append(node) # 将当前节点加入结果列表 # 更新相邻节点的入度 for neighbor in graph.get(node, []): inDegrees[neighbor] -= 1 # 如果入度为0，则将其加入队列中 if inDegrees[neighbor] == 0: queue.append(neighbor) return result def main(): # 创建一个有向图 graph = { 0: [1, 2], 1: [3], 2: [3, 4], 3: [4], 4: [] } # 进行拓扑排序 result = topologicalSort(graph) # 输出拓扑排序结果 print("拓扑排序结果:", result) if __name__ == "__main__": main()
六.图的匹配
图的匹配是图论中的一个重要概念，用于描述在一个图中找到一组边，使得这些边互不相邻。这组边被称为匹配。
具体来说，对于一个无向图，图的匹配是指选择图中的一些边，使得这些边没有公共顶点。换句话说，对于任意两条边来说，它们都不相邻。
匹配在很多实际应用中都有重要的作用。例如，在社交网络中，可以利用匹配来寻找用户之间的潜在关系；在电子电路设计中，可以利用匹配来寻找电路中满足特定条件的连接方式。
在图论中，有很多算法可以用来寻找图的匹配，其中最著名的算法之一是匈牙利算法（Hungarian algorithm）。匈牙利算法可以在二分图中寻找最大的匹配，即找到尽可能多的不相邻的边。其他常用的匹配算法还包括最大流算法（如Edmonds-Karp算法（5.1.2））和深度优先搜索算法（1.1）。
1.匈牙利算法
匈牙利算法（Hungarian algorithm），也称为增广路径算法，是解决二分图最大匹配问题的经典算法之一。匈牙利算法的目标是找到一个最大的匹配，即找到尽可能多的互不相邻的边。
具体来说，匈牙利算法是通过不断寻找增广路径来不断扩大匹配的。增广路径是指一条路径，路径的起点和终点都是未匹配的顶点，且路径上的边交替属于匹配和非匹配边。通过寻找增广路径，可以将原有的匹配中的某些边移除，并加入新的边，从而使匹配数量增加。
匈牙利算法的基本步骤如下：
1. 初始化一个空的匹配集合。
2. 对于每个未匹配的顶点，尝试寻找一条增广路径。
3. 如果找到增广路径，则将原匹配中的边移除，并加入新的边。
4. 如果无法找到增广路径，则结束算法，得到最大匹配。
匈牙利算法通过使用深度优先搜索或广度优先搜索来查找增广路径。它可以在多项式时间内解决二分图最大匹配问题，时间复杂度为O(V^3)，其中V是顶点的数量。
匈牙利算法的应用非常广泛，比如在任务分配、稳定婚姻匹配、社交网络分析等领域都有应用。此外，匈牙利算法也是其他一些更复杂算法的基础，如KM算法（也称为Kuhn-Munkres算法），它可以在带权二分图上求解最大权匹配问题。
1.1匈牙利算法c++代码示例
#include <iostream> #include <vector> #include <cstring> using namespace std; #define MAX_NODES 100 // 最大节点数 // 图的数据结构 vector<int> graph[MAX_NODES]; // 顶点的匹配关系数组 int match[MAX_NODES]; // 记录顶点是否已被访问过的数组 bool visited[MAX_NODES]; // 初始化图 void initGraph(int numNodes) { for (int i = 0; i < numNodes; i++) { graph[i].clear(); } } // 添加边 void addEdge(int u, int v) { graph[u].push_back(v); } // 在当前匹配中寻找增广路径 bool findAugmentingPath(int node) { for (int i = 0; i < graph[node].size(); i++) { int neighbor = graph[node][i]; // 如果邻居节点未被访问过，则将其标记为已访问 if (!visited[neighbor]) { visited[neighbor] = true; // 如果邻居节点未匹配或能在与其相邻的节点中找到增广路径，则进行匹配 if (match[neighbor] == -1 || findAugmentingPath(match[neighbor])) { match[neighbor] = node; return true; } } } return false; } // 使用匈牙利算法找到最大匹配 int maximumMatching(int numNodes) { // 初始化顶点的匹配关系 memset(match, -1, sizeof(match)); int count = 0; // 记录匹配的边的数量 for (int i = 0; i < numNodes; i++) { // 初始化记录顶点是否已被访问过的数组 memset(visited, false, sizeof(visited)); // 在当前顶点的邻居中寻找增广路径 if (findAugmentingPath(i)) { count++; } } return count; } int main() { int numNodes = 4; // 初始化图 initGraph(numNodes); // 添加边 addEdge(0, 1); addEdge(1, 2); addEdge(2, 0); addEdge(2, 3); // 使用匈牙利算法找到最大匹配 int maxMatching = maximumMatching(numNodes); cout << "最大匹配数: " << maxMatching << endl; return 0; }
这段代码首先定义了一个全局的图数据结构，使用邻接表表示图的连接关系。然后定义了顶点的匹配关系数组match和记录顶点是否已被访问过的数组visited。
匈牙利算法采用递归的方式，在每一次递归中查找增广路径来扩大匹配。函数findAugmentingPath用于在当前匹配中寻找增广路径。在该函数中，遍历当前节点的邻居节点，如果邻居节点未被访问过，则继续递归地寻找增广路径。如果邻居节点未匹配或能在与其相邻的节点中找到增广路径，则进行匹配，将邻居节点与当前节点进行匹配。
函数maximumMatching用于使用匈牙利算法找到最大匹配。在该函数中，遍历所有节点，对于每个节点，使用findAugmentingPath来查找增广路径，并进行匹配。
最后，在main函数中，初始化图，并添加边。然后使用匈牙利算法找到最大匹配，并将结果输出。
该代码的实现基于匈牙利算法的思想，通过不断寻找增广路径来扩大匹配集合。通过递归和回溯的方式，在遍历图中的顶点时，不断尝试寻找增广路径，并进行匹配，直到无法再找到增广路径为止。这样就可以得到最大的匹配数。
1.2匈牙利算法的c代码和python代码示例
#include <stdio.h> #include <stdbool.h> #define MAX_NODES 100 // 最大节点数 // 图的数据结构 int graph[MAX_NODES][MAX_NODES]; // 顶点的匹配关系数组 int match[MAX_NODES]; // 记录顶点是否已被访问过的数组 bool visited[MAX_NODES]; // 初始化图 void initGraph(int numNodes) { for (int i = 0; i < numNodes; i++) { for (int j = 0; j < numNodes; j++) { graph[i][j] = 0; } } } // 添加边 void addEdge(int u, int v) { graph[u][v] = 1; } // 在当前匹配中寻找增广路径 bool findAugmentingPath(int node, int numNodes) { for (int i = 0; i < numNodes; i++) { if (graph[node][i] && !visited[i]) { visited[i] = true; if (match[i] == -1 || findAugmentingPath(match[i], numNodes)) { match[i] = node; return true; } } } return false; } // 使用匈牙利算法找到最大匹配 int maximumMatching(int numNodes) { // 初始化顶点的匹配关系 for (int i = 0; i < numNodes; i++) { match[i] = -1; } int count = 0; for (int i = 0; i < numNodes; i++) { // 初始化记录顶点是否已被访问过的数组 for (int j = 0; j < numNodes; j++) { visited[j] = false; } if (findAugmentingPath(i, numNodes)) { count++; } } return count; } int main() { int numNodes = 4; // 初始化图 initGraph(numNodes); // 添加边 addEdge(0, 1); addEdge(1, 2); addEdge(2, 0); addEdge(2, 3); // 使用匈牙利算法找到最大匹配 int maxMatching = maximumMatching(numNodes); printf("最大匹配数: %d\n", maxMatching); return 0; }
def find_augmenting_path(node, graph, match, visited): num_nodes = len(graph) for i in range(num_nodes): if graph[node][i] and not visited[i]: visited[i] = True if match[i] == -1 or find_augmenting_path(match[i], graph, match, visited): match[i] = node return True return False def maximum_matching(graph): num_nodes = len(graph) match = [-1] * num_nodes count = 0 for i in range(num_nodes): visited = [False] * num_nodes if find_augmenting_path(i, graph, match, visited): count += 1 return count def main(): num_nodes = 4 # 初始化图 graph = [[0] * num_nodes for _ in range(num_nodes)] # 添加边 graph[0][1] = 1 graph[1][2] = 1 graph[2][0] = 1 graph[2][3] = 1 # 使用匈牙利算法找到最大匹配 max_matching = maximum_matching(graph) print("最大匹配数:", max_matching) if __name__ == "__main__": main()
总结
像最小费用流、割边和割点、有向无环图的计数等等图算法，还可以参考一些算法教育网站和在线资源，例如GeeksforGeeks、Stack Overflow、算法导论等，它们提供了大量的算法学习资料、教程和示例代码。
后续还会出一期关键字的使用
