摘要：Share interest, spread happiness, increase knowledge, leave a beautiful!
分享兴趣，传播快乐，增长见闻，留下美好！
亲爱的您，这里是LearningYard新学苑。
今天小编给您带来
【周周记：数学建模学习（36）】
欢迎您的访问！
Share interest, spread happiness, increase knowledge, leave a beautiful!
Dear, this is LearningYard New Academy.
Today, the editor brings you
"Weekly Diary: Learning Mathematical Modeling (36)"
Welcome to your visit!
数学常规算法之图论
The conventional algorithms in mathematics: Graph Theory
深度优先搜索（DFS）
Depth-First Search (DFS)
步骤：
Steps:
1.从一个顶点开始，标记为已访问。
Step 1: Start from a vertex and mark it as visited.
2.选择一个相邻的未访问顶点，标记为已访问，然后递归地对这个顶点进行DFS。
Step 2: Select an adjacent vertex that has not been visited, mark it as visited, and then perform a recursive DFS on this vertex.
3.如果没有未访问的相邻顶点，回溯到上一个顶点。
Step 3: If there are no adjacent vertices that have not been visited, return to the previous vertex.
4.重复步骤2和3，直到所有顶点都被访问。
Step 4: Repeat steps 2 and 3 until all vertices have been visited.
Implementation:
广度优先搜索（BFS）
Breadth-First Search (BFS)
步骤：
Steps:
1.从一个顶点开始，标记为已访问，并将其加入队列。
Step 1: Start from a vertex and mark it as visited, then add it to the queue.
2.从队列中取出一个顶点，访问其所有未访问的相邻顶点，并将这些相邻顶点标记为已访问，然后加入队列。
Step 2: Take a vertex from the queue, visit all its unvisited adjacent vertices, mark them as visited, and then add them to the queue.
3.重复步骤2，直到队列为空。
Step 3: Repeat step 2 until the queue is empty.
Implementation:
Steps:
1. 为每个顶点分配一个 tentative distance 值：所有顶点的 tentative distance 都设为无穷大，除了起始顶点，其 tentative distance 设为0。
Step 1: Assign a tentative distance value to each vertex: set the tentative distance of all vertices to infinity, except for the starting vertex, which is set to 0.
2. 设置一个未访问顶点集合，包含所有顶点。
Step 2: Create a set of unvisited vertices that includes all vertices.
3. 从未访问顶点集合中选择 tentative distance 最小的顶点，标记为已访问，并从集合中移除。
Step 3: Select the vertex with the smallest tentative distance from the set of unvisited vertices, mark it as visited, and remove it from the set.
4. 对于这个顶点的每个未访问的相邻顶点，计算其 tentative distance，如果小于当前的 tentative distance，则更新。
Step 4: For each unvisited adjacent vertex of this vertex, calculate its tentative distance, and if it is less than the current tentative distance, update it.
5. 重复步骤3和4，直到未访问顶点集合为空。
Step 5: Repeat steps 3 and 4 until the set of unvisited vertices is empty.
Implementation:
Bellman-Ford算法:
Bellman-Ford Algorithm:
步骤：
Steps:
1. 为每个顶点分配一个 distance 值：所有顶点的 distance 都设为无穷大，除了起始顶点，其 distance 设为0。
Step 1: Assign a distance value to each vertex: set the distance of all vertices to infinity, except for the starting vertex, which is set to 0.
2. 对图中的每条边进行 V-1 次松弛操作，其中 V 是顶点数。
Step 2: Perform relaxation operations on each edge in the graph V-1 times, where V is the number of vertices.
3. 检查图中是否存在负权环，如果存在，则算法终止。
Step 3: Check if there is a negative weight cycle in the graph; if one exists, the algorithm terminates.
Floyd-Warshall算法:
Floyd-Warshall Algorithm:
步骤：
Steps:
1. 为每个顶点对 (i, j) 分配一个 distance 值：如果 i 和 j 之间有直接的边，则 distance 为边的权重；否则为无穷大。
Step 1: Assign a distance value to each pair of vertices (i, j): if there is a direct edge between i and j, the distance is the weight of the edge; otherwise, it is infinity.
2. 对于每个顶点 k，更新所有顶点对 (i, j) 的 distance，如果通过 k 的路径更短，则更新。
Step 2: For each vertex k, update the distance of all pairs of vertices (i, j), updating if the path through k is shorter.
Implementation:
Kruskal算法:
Kruskal's Algorithm:
步骤：
Steps:
1. 将图中的边按权重从小到大排序。
Step 1: Sort all the edges in the graph in non-decreasing order of their weights.
2. 从排序后的边列表中选择边，如果这条边不会形成环，则将其加入最小生成树。
Step 2: Select edges from the sorted list and add them to the minimum spanning tree if they do not form a cycle.
3. 重复步骤2，直到最小生成树包含所有顶点。
Step 3: Repeat step 2 until the minimum spanning tree includes all vertices.
Implementation:
Prim算法:
Prim's Algorithm:
步骤：
Steps:
1. 从一个顶点开始，将其加入最小生成树。
Step 1: Start with an arbitrary vertex and add it to the minimum spanning tree.
2. 选择最小生成树中顶点的最小权重边，如果这条边的另一个顶点不在最小生成树中，则将其加入最小生成树。
Step 2: Select the edge with the smallest weight that connects a vertex in the minimum spanning tree to a vertex outside of it, and add this edge and its corresponding vertex to the minimum spanning tree.
3. 重复步骤2，直到最小生成树包含所有顶点。
Step 3: Repeat step 2 until the minimum spanning tree contains all vertices.
Implementation:
Ford-Fulkerson算法:
Ford-Fulkerson Algorithm:
步骤：
Steps:
1. 初始化所有边的流为0。
Step 1: Initialize the flow of all edges to 0.
2. 找到一个从源点到汇点的增广路径。
Step 2: Find an augmenting path from the source to the sink.
3. 沿着增广路径增加流，直到无法找到增广路径。
Step 3: Increase the flow along the augmenting path until no more augmenting paths can be found.
Implementation:
Edmonds-Karp算法:
Edmonds-Karp Algorithm:
步骤：
Steps:
1. 初始化所有边的流为0。
Step 1: Initialize the flow in all edges to 0.
2. 使用BFS找到一个从源点到汇点的增广路径。
Step 2: Use Breadth-First Search (BFS) to find an augmenting path from the source to the sink.
3. 沿着增广路径增加流，直到无法找到增广路径。
Step 3: Increase the flow along the augmenting path until no more augmenting paths can be found.
Implementation:
Hungarian Algorithm:
步骤：
Steps:
1. 为二分图的每个顶点分配一个标签，初始时所有标签都设为0。
Step 1: Assign a label to each vertex of the bipartite graph, with all labels initially set to 0.
2. 选择一个未匹配的顶点，尝试找到一个增广路径。
Step 2: Select an unmatched vertex and attempt to find an augmenting path.
3. 如果找到增广路径，则更新匹配；否则，调整标签，使得更多的顶点可以被匹配。
Step 3: If an augmenting path is found, update the matching; otherwise, adjust the labels to allow more vertices to be matched.
4. 重复步骤2和3，直到所有顶点都被匹配。
Step 4: Repeat steps 2 and 3 until all vertices are matched.
Implementation:
今天的分享就到这里了。
如果您对今天的文章有独特的看法，
欢迎给我们留言，
让我们相约明天，
祝您今天过得开心！
That's all for today's share.
If you have a unique view of today's article,
Please leave us a message,
Let's meet tomorrow,
Have a nice day!
本文由LearningYard新学苑原创，如有侵权，请联系删除。
参考资料：哔哩哔哩
翻译：文心一言
来源：LearningYard学苑
