1024programmer Asp.Net Among the 10 algorithms commonly used in program development, how many have you used?

Among the 10 algorithms commonly used in program development, how many have you used?

Among the 10 algorithms commonly used in program development, how many have you used?

When writing programs, understanding and using different algorithms is crucial to solving problems. Below are 10 commonly used algorithms in C#, each accompanied by sample code and detailed instructions.

1. Bubble Sort:

Bubble sort is a simple comparison sort algorithm that traverses the array multiple times and gradually floats larger elements to the end of the array.

public static void BubbleSort(int[] arr)
 {
     int n = arr.Length;
     for (int i = 0; i < n - 1; i++)
     {
         for (int j = 0; j  arr[j + 1])
             {
                 int temp = arr[j];
                 arr[j] = arr[j + 1];
                 arr[j + 1] = temp;
             }
         }
     }
 }

2. Quick Sort:

Quicksort is an efficient divide-and-conquer sorting algorithm that sorts by selecting a pivot element and dividing the array into smaller and larger parts.

public static void QuickSort(int[] arr, int low, int high)
 {
     if (low < high)
     {
         int partitionIndex = Partition(arr, low, high);
         QuickSort(arr, low, partitionIndex - 1);
         QuickSort(arr, partitionIndex + 1, high);
     }
 }

 public static int Partition(int[] arr, int low, int high)
 {
     int pivot = arr[high];
     int i = low - 1;

     for (int j = low; j < high; j++)
     {
         if (arr[j] < pivot)
         {
             i++;
             int temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
         }
     }

     int swap = arr[i + 1];
     arr[i + 1] = arr[high];
     arr[high] = swap;

     return i + 1;
 }

3. Merge Sort:

Merge sort is a stable divide-and-conquer sorting algorithm. It divides the array into two halves, sorts them separately and then merges them.

public static void MergeSort(int[] arr)
 {
     int n = arr.Length;
     if(n>1)
     {
         int mid = n / 2;
         int[] left = new int[mid];
         int[] right = new int[n - mid];

         for (int i = 0; i < mid; i++)
             left[i] = arr[i];
         for (int i = mid; i < n; i++)
             right[i - mid] = arr[i];

         MergeSort(left);
         MergeSort(right);

         int i = 0, j = 0, k = 0;
         while (i < mid && j < (n - mid))
         {
             if (left[i] < right[j])
                 arr[k++] = left[i++];
             else
                 arr[k++] = right[j++];
         }
         while (i < mid)
             arr[k++] = left[i++];
         while (j < (n - mid))
             arr[k++] = right[j++];
     }
 }

4. Binary Search:

Binary search is an efficient search algorithm that requires finding specific elements in an ordered array.

public static int BinarySearch(int[] arr, int target)
 {
     int low = 0, high = arr.Length - 1;
     while (low <= high)
     {
         int mid = (low + high) / 2;
         if (arr[mid] == target)
             return mid;
         else if (arr[mid] < target)
             low = mid + 1;
         else
             high = mid - 1;
     }
     return -1;
 }

5. Depth-First Search (DFS):

DFS is a graph traversal algorithm that starts at a starting node, follows a path as far as possible, and then goes back and continues the search.

using System;
 using System.Collections.Generic;

 public class Graph
 {
     private int V;
     private List[] adj;

     publicGraph(int v)
     {
         V = v;
         adj = new List[v];
         for (int i = 0; i < v; i++)
             adj[i] = new List();
     }

     public void AddEdge(int v, int w)
     {
         adj[v].Add(w);
     }

     public void DFS(int v)
     {
         bool[] visited = new bool[V];
         DFSUtil(v, visited);
     }

     private void DFSUtil(int v, bool[] visited)
     {
         visited[v] = true;
         Console.Write(v + " ");

         foreach (var n in adj[v])
         {
             if (!visited[n])
                 DFSUtil(n, visited);
         }
     }
 }

6. Breadth-First Search (BFS):

BFS is a graph traversal algorithm that starts from the starting node and traverses layer by layer. It first visits all adjacent nodes and then expands layer by layer.

using System;
 using System.Collections.Generic;

 public cLass Graph
 {
     private int V;
     private List[] adj;

     publicGraph(int v)
     {
         V = v;
         adj = new List[v];
         for (int i = 0; i < v; i++)
             adj[i] = new List();
     }

     public void AddEdge(int v, int w)
     {
         adj[v].Add(w);
     }

     public void BFS(int s)
     {
         bool[] visited = new bool[V];

         Queue queue = new Queue();
         visited[s] = true;
         queue.Enqueue(s);

         while (queue.Count != 0)
         {
             s = queue.Dequeue();
             Console.Write(s + " ");

             foreach (var n in adj[s])
             {
                 if (!visited[n])
                 {
                     visited[n] = true;
                     queue.Enqueue(n);
                 }
             }
         }
     }
 }

7. Dijkstra algorithm:

Dijkstra’s algorithm is an algorithm for finding the shortest path in a graph.

public class Dijkstra
 {
     private static int V = 9;

     private int MinDistance(int[] dist, bool[] sptSet)
     {
         int min = int.MaxValue;
         int minIndex = 0;

         for (int v = 0; v < V; v++)
         {
             if (!sptSet[v] && dist

 [v] <= min)
             {
                 min = dist[v];
                 minIndex = v;
             }
         }

         return minIndex;
     }

     private void PrintSolution(int[] dist)
     {
         Console.WriteLine("Vertex \t Distance from Source");
         for (int i = 0; i < V; i++)
         {
             Console.WriteLine(i + " \t " + dist[i]);
         }
     }

     public void FindShortestPath(int[,] graph, int src)
     {
         int[] dist = new int[V];
         bool[] sptSet = new bool[V];

         for (int i = 0; i < V; i++)
         {
             dist[i] = int.MaxValue;
             sptSet[i] = false;
         }

         dist[src] = 0;

         for (int count = 0; count < V - 1; count++)
         {
             int u = MinDistance(dist, sptSet);

             sptSet[u] = true;

             for (int v = 0; v < V; v++)
             {
                 if (!sptSet[v] && graph[u, v] != 0 && dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v])
                 {
                     dist[v] = dist[u] + graph[u, v];
                 }
             }
         }

         PrintSolution(dist);
     }
 }

8. Minimum Spanning Tree (MST) – Prim’s algorithm:

Prim’s algorithm is used to find the minimum spanning tree of a graph. It starts from an initial vertex and gradually expands the spanning tree.

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 algorithm:

Kruskal’s algorithm is also used to find the minimum spanning tree of a graph, which is based on edge weight ordering.

using System;
 using System.Collections.Generic;

 public class Graph
 {
     private int V, E;
     private List edges;

     public Graph(int v, int e)
     {
         V = v;
         E = e;
         edges = new List(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 mst = new List();

         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[yRoot] = xRoot;
         else
         {
             parent[yRoot] = xRoot;
             rank[xRoot]++;
         }
     }
 }

 public class Edge : IComparable
 {
     public int src, dest, weight;

     public Edge(int src, int dest, int weight)
     {
         this.src = src;
         this.dest = dest;
         this.weight = weight;
     }

     public int CompareTo(Edge other)
     {
         return weight - other.weight;
     }
 }

10.Floyd-Warshall algorithm is a dynamic programming algorithm used to solve the shortest path for all point pairs.

The following is an implementation example of the Floyd-Warshall algorithm in C#:

using System;

 classFloydWarshall
 {
     private static int INF = int.MaxValue; // represents an infinite value

     public static void FindShortestPath(int[,] graph)
     {
         int V = graph.GetLength(0);

         // Create a two-dimensional array dist to save the length of the shortest path
         int[,] dist = new int[V, V];

         //Initialize the dist array
         for (int i = 0; i < V; i++)
         {
             for (int j = 0; j < V; j++)
             {
                 dist[i, j] = graph[i, j];
             }
         }

         //Consider vertex by vertex, if the path through k vertices is shorter than the original path, update the dist array
         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];
                     }
                 }
             }
         }

         // Output the shortest path matrix
         Console.WriteLine("Shortest path matrix:");
         for (int i = 0; i < V; i++)
         {
             for (int j = 0; j < V; j++)
             {
                 if (dist[i, j] == INF)
                     Console.Write("INF\t");
                 else
                     Console.Write(dist[i, j] + "\t");
             }
             Console.WriteLine();
         }
     }

     static void Main(string[] args)
     {
         int V = 4; // number of vertices
         int[,] graph = {
             {0, 5, INF, 10},
             {INF, 0, 3, INF},
             {INF, INF, 0, 1},
             {INF, INF, INF, 0}
         };

         FindShortestPath(graph);
     }
 }

In this example, we use the Floyd-Warshall algorithm to calculate the shortest path matrix of a given graph. This algorithm continuously updates the shortest path matrix dist by considering intermediate vertices k one by one. Finally, we can obtain the shortest path length between all pairs of points.

for (int i = 0; i < V; i++)
{
parent[i] = i;
rank[i] = 0;
}

int i = 0;
int e = 0;

List mst = new List();

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[yRoot] = xRoot;
else
{
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
}

public class Edge : IComparable
{
public int src, dest, weight;

public Edge(int src, int dest, int weight)
{
this.src = src;
this.dest = dest;
this.weight = weight;
}

public int CompareTo(Edge other)
{
return weight – other.weight;
}
}

10.Floyd-Warshall algorithm is a dynamic programming algorithm used to solve the shortest path for all point pairs.

The following is an implementation example of the Floyd-Warshall algorithm in C#:

using System;

 classFloydWarshall
 {
     private static int INF = int.MaxValue; // represents an infinite value

     public static void FindShortestPath(int[,] graph)
     {
         int V = graph.GetLength(0);

         // Create a two-dimensional array dist to save the length of the shortest path
         int[,] dist = new int[V, V];

         //Initialize the dist array
         for (int i = 0; i < V; i++)
         {
             for (int j = 0; j < V; j++)
             {
                 dist[i, j] = graph[i, j];
             }
         }

         //Consider vertex by vertex, if the path through k vertices is shorter than the original path, update the dist array
         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];
                     }
                 }
             }
         }

         // Output the shortest path matrix
         Console.WriteLine("Shortest path matrix:");
         for (int i = 0; i < V; i++)
         {
             for (int j = 0; j < V; j++)
             {
                 if (dist[i, j] == INF)
                     Console.Write("INF\t");
                 else
                     Console.Write(dist[i, j] + "\t");
             }
             Console.WriteLine();
         }
     }

     static void Main(string[] args)
     {
         int V = 4; // number of vertices
         int[,] graph = {
             {0, 5, INF, 10},
             {INF, 0, 3, INF},
             {INF, INF, 0, 1},
             {INF, INF, INF, 0}
         };

         FindShortestPath(graph);
     }
 }

In this example, we use the Floyd-Warshall algorithm to calculate the shortest path matrix of a given graph. This algorithm continuously updates the shortest path matrix dist by considering intermediate vertices k one by one. Finally, we can obtain the shortest path length between all pairs of points.

This article is from the internet and does not represent1024programmerPosition, please indicate the source when reprinting:https://www.1024programmer.com/811174

author: admin

Previous article
Next article

Leave a Reply

Your email address will not be published. Required fields are marked *

Contact Us

Contact us

181-3619-1160

Online consultation: QQ交谈

E-mail: [email protected]

Working hours: Monday to Friday, 9:00-17:30, holidays off

Follow wechat
Scan wechat and follow us

Scan wechat and follow us

Follow Weibo
Back to top
首页
微信
电话
搜索