Comment écrire l'algorithme d'arbre couvrant minimum en utilisant C#

Comment écrire l'algorithme d'arbre couvrant minimum en utilisant C#

L'algorithme d'arbre couvrant minimum est un algorithme important de la théorie des graphes, qui est utilisé pour résoudre le problème de connectivité des graphiques. En informatique, un arbre couvrant minimum fait référence à un arbre couvrant d'un graphe connecté dans lequel la somme des poids de toutes les arêtes de l'arbre couvrant est la plus petite.

Cet article expliquera comment utiliser C# pour écrire l'algorithme d'arbre couvrant minimum et fournira des exemples de code spécifiques.

Tout d'abord, nous devons définir une structure de données graphique pour représenter le problème. En C#, vous pouvez utiliser une matrice de contiguïté pour représenter un graphique. Une matrice de contiguïté est un tableau bidimensionnel dans lequel chaque élément représente le poids d'une arête entre deux sommets. S'il n'y a pas d'arête entre deux sommets, cette valeur peut être définie sur une identité spécifique, telle que l'infini.

Ce qui suit est un exemple de code qui utilise une matrice de contiguïté pour représenter un graphique :

class Graph
{
    private int[,] matrix;  // 邻接矩阵
    private int numVertices; // 顶点数量

    public Graph(int numVertices)
    {
        this.numVertices = numVertices;
        matrix = new int[numVertices, numVertices];
    }

    public void AddEdge(int startVertex, int endVertex, int weight)
    {
        matrix[startVertex, endVertex] = weight;
        matrix[endVertex, startVertex] = weight;
    }

    public int GetEdge(int startVertex, int endVertex)
    {
        return matrix[startVertex, endVertex];
    }
}

Ensuite, nous devons implémenter un algorithme d'arbre couvrant minimum pour trouver l'arbre couvrant avec le poids total minimum. Parmi eux, les algorithmes Prim et Kruskal sont deux algorithmes d'arbre couvrant minimum couramment utilisés. Dans cet article, nous présenterons l'algorithme de Prim.

L'idée de base de l'algorithme de Prim est de partir de n'importe quel sommet, de sélectionner en continu l'arête ayant le plus petit poids parmi les arêtes connectées à l'arbre couvrant actuel, et de connecter cette arête à l'arbre couvrant. Répétez ce processus jusqu'à ce que tous les sommets aient rejoint l'arbre couvrant.

Ce qui suit est un exemple de code pour implémenter un arbre couvrant minimum à l'aide de l'algorithme de Prim :

class PrimMST
{
    private Graph graph;
    private int[] key;         // 存储对应顶点的权值
    private bool[] mstSet;     // 存储对应顶点是否已加入生成树

    public PrimMST(Graph graph)
    {
        this.graph = graph;
        int numVertices = graph.GetNumVertices();
        key = new int[numVertices];
        mstSet = new bool[numVertices];
    }

    private int MinKey()
    {
        int min = int.MaxValue;
        int minIndex = -1;

        for (int v = 0; v < graph.GetNumVertices(); v++)
        {
            if (mstSet[v] == false && key[v] < min)
            {
                min = key[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    public void CalculateMST(int startVertex)
    {
        for (int v = 0; v < graph.GetNumVertices(); v++)
        {
            key[v] = int.MaxValue;
            mstSet[v] = false;
        }

        key[startVertex] = 0;

        for (int count = 0; count < graph.GetNumVertices() - 1; count++)
        {
            int u = MinKey();

            if (u == -1)
            {
                break;
            }

            mstSet[u] = true;

            for (int v = 0; v < graph.GetNumVertices(); v++)
            {
                int weight = graph.GetEdge(u, v);

                if (weight > 0 && mstSet[v] == false && weight < key[v])
                {
                    key[v] = weight;
                }
            }
        }

        PrintMST();
    }

    private void PrintMST()
    {
        Console.WriteLine("Edge     Weight");
        for (int v = 1; v < graph.GetNumVertices(); v++)
        {
            Console.WriteLine($"{v} - {key[v]}");
        }
    }
}

Enfin, nous devons écrire du code pour utiliser ces classes au point d'entrée du programme et le tester.

class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph(5);
        graph.AddEdge(0, 1, 2);
        graph.AddEdge(0, 3, 6);
        graph.AddEdge(1, 2, 3);
        graph.AddEdge(1, 3, 8);
        graph.AddEdge(1, 4, 5);
        graph.AddEdge(2, 4, 7);
        graph.AddEdge(3, 4, 9);

        PrimMST mst = new PrimMST(graph);
        mst.CalculateMST(0);
    }
}

Exécutez le code ci-dessus et les bords et les poids de l'arbre couvrant minimum seront affichés.

Ci-dessus sont les étapes et un exemple de code pour écrire l'algorithme d'arbre couvrant minimum en utilisant C#. En comprenant les principes derrière l'algorithme et en effectuant les ajustements appropriés en fonction des besoins réels, vous pouvez mieux utiliser l'algorithme pour résoudre les problèmes correspondants dans des applications pratiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!