江苏龙网

  1. 主页 > 生活百科 > >

程序开发中常用的十种算法，你用过几种？( 二 )

算法


Prim算法用于找到图的最小生成树 ， 它从一个初始顶点开始，逐渐扩展生成树 。
public class PrimMST{private static int V = 5;private int MinKey(int[] key, bool[] mstSet){int min = int.MaxValue;int minIndex = 0;for (int v = 0; v < V; v++){if (!mstSet[v] && key[v] < min){min = key[v];minIndex = v;}}return minIndex;}private void PrintMST(int[] parent, int[,] graph){Console.WriteLine("Edge t Weight");for (int i = 1; i < V; i++){Console.WriteLine(parent[i] + " - " + i + " t " + graph[i, parent[i]]);}}public void FindMST(int[,] graph){int[] parent = new int[V];int[] key = new int[V];bool[] mstSet = new bool[V];for (int i = 0; i < V; i++){key[i] = int.MaxValue;mstSet[i] = false;}key[0] = 0;parent[0] = -1;for (int count = 0; count < V - 1; count++){int u = MinKey(key, mstSet);mstSet[u] = true;for (int v = 0; v < V; v++){if (graph[u, v] != 0 && !mstSet[v] && graph[u, v] < key[v]){parent[v] = u;key[v] = graph[u, v];}}}PrintMST(parent, graph);}}9. 最小生成树 (Minimum Spanning Tree, MST) - Kruskal算法:
Kruskal算法也用于找到图的最小生成树 ， 它基于边的权重排序 。
using System;using System.Collections.Generic;public class Graph{private int V, E;private List<Edge> edges;public Graph(int v, int e){V = v;E = e;edges = new List<Edge>(e);}public void AddEdge(int src, int dest, int weight){edges.Add(new Edge(src, dest, weight));}public void KruskalMST(){edges.Sort();int[] parent = new int[V];int[] rank = new int[V];for (int i = 0; i < V; i++){parent[i] = i;rank[i] = 0;}int i = 0;int e = 0;List<Edge> mst = new List<Edge>();while (e < V - 1){Edge nextEdge = edges[i++];int x = Find(parent, nextEdge.src);int y = Find(parent, nextEdge.dest);if (x != y){mst.Add(nextEdge);Union(parent, rank, x, y);e++;}}Console.WriteLine("Edges in Minimum Spanning Tree:");foreach (var edge in mst){Console.WriteLine($"{edge.src} - {edge.dest} with weight {edge.weight}");}}private int Find(int[] parent, int i){if (parent[i] == i)return i;return Find(parent, parent[i]);}private void Union(int[] parent, int[] rank, int x, int y){int xRoot = Find(parent, x);int yRoot = Find(parent, y);if (rank[xRoot] < rank[yRoot])parent[xRoot] = yRoot;else if (rank[xRoot] > rank[yRoot])parent[yRoot] = xRoot;else{parent[yRoot] = xRoot;rank[xRoot]++;}}}public class Edge : IComparable<Edge>{public int src, dest, weight;public Edge(int src, int dest, int weight){this.src = https://www.isolves.com/it/cxkf/sf/2024-01-17/src;this.dest = dest;this.weight = weight;}public int CompareTo(Edge other){return weight - other.weight;}}10.Floyd-Warshall算法是一种用于解决所有点对最短路径的动态规划算法 。
下面是C#中的Floyd-Warshall算法的实现示例：
using System;class FloydWarshall{private static int INF = int.MaxValue; // 代表无穷大的值public static void FindShortestPath(int[,] graph){int V = graph.GetLength(0);// 创建一个二维数组dist，用于保存最短路径的长度int[,] dist = new int[V, V];// 初始化dist数组for (int i = 0; i < V; i++){for (int j = 0; j < V; j++){dist[i, j] = graph[i, j];}}// 逐个顶点考虑，如果经过k顶点路径比原路径短 ， 就更新dist数组for (int k = 0; k < V; k++){for (int i = 0; i < V; i++){for (int j = 0; j < V; j++){if (dist[i, k] != INF && dist[k, j] != INF&& dist[i, k] + dist[k, j] < dist[i, j]){dist[i, j] = dist[i, k] + dist[k, j];}}}}// 输出最短路径矩阵Console.WriteLine("最短路径矩阵：");for (int i = 0; i < V; i++){for (int j = 0; j < V; j++){if (dist[i, j] == INF)Console.Write("INFt");elseConsole.Write(dist[i, j] + "t");}Console.WriteLine();}}static void MAIn(string[] args){int V = 4; // 顶点数int[,] graph = {{0, 5, INF, 10},{INF, 0, 3, INF},{INF, INF, 0, 1},{INF, INF, INF, 0}};FindShortestPath(graph);}}在这个示例中，我们使用Floyd-Warshall算法来计算给定图的最短路径矩阵 。该算法通过考虑逐个中间顶点k，不断更新最短路径矩阵dist 。最终，我们可以获得所有点对之间的最短路径长度 。




推荐阅读


上一篇：阿里云DDOS防御如何安装

下一篇：批量执行Redis命令的四种方式！