普里姆算法最小生成树

2020/01/14 40

算法

普里姆算法(Prim's algorithm),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点,且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现;并在1957年由美国计算机科学家罗伯特·普里姆独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

最小生成树

class Program
{
    static void Main(string[] args)
    {
        int[,] graph =
        {
            { 0, 7, int.MaxValue, 5, int.MaxValue, int.MaxValue, int.MaxValue },
            { 7, 0, 8, int.MaxValue, 7, int.MaxValue, int.MaxValue },
            { int.MaxValue, 8, 0, int.MaxValue, 5, int.MaxValue, int.MaxValue },
            { 5, 9, int.MaxValue, 0, 15, 6, int.MaxValue },
            { int.MaxValue, 7, 5, 15, 0, 8, 9 },
            { int.MaxValue, int.MaxValue, int.MaxValue, 6, 8, 0, 11 },
            { int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, 9, 11, 0 }
        };
        Prim(graph, 7);
    }

    static int GetMinKeyIndex(int[] keys, bool[] set, int verticesCount)
    {
        int min = int.MaxValue, minIndex = 0;
        for (int i = 0; i < verticesCount; i++)
        {
            if (!set[i] && keys[i] < min)
            {
                min = keys[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    static void Print(int[] parent, int[,] graph, int verticesCount)
    {
        int baseValue = 'A';
        Console.WriteLine("Edge\tWeight");
        for (int i = 1; i < verticesCount; i++)
            Console.WriteLine($"{(char)(baseValue + parent[i])} - {(char)(i + baseValue)}\t{graph[i, parent[i]]}");
    }

    static void Prim(int[,] graph, int verticesCount)
    {
        // 保存相关顶点下标
        int[] parent = new int[verticesCount];
        // 保存相关顶点边的权值
        int[] keys = new int[verticesCount];
        bool[] set = new bool[verticesCount];

        // 初始化
        for (int i = 0; i < verticesCount; ++i)
        {
            keys[i] = int.MaxValue;
            // mstSet[i] = false;
        }

        keys[0] = 0;
        parent[0] = -1;

        // 普里姆算法
        for (int i = 0; i < verticesCount - 1; i++)
        {
            int minKeyIndex = GetMinKeyIndex(keys, set, verticesCount);
            set[minKeyIndex] = true;
            for (int j = 0; j < verticesCount; j++)
            {
                if (graph[minKeyIndex, j] != 0 && set[j] == false && graph[minKeyIndex, j] < keys[j])
                {
                    parent[j] = minKeyIndex;
                    keys[j] = graph[minKeyIndex, j];
                }
            }
        }

        Print(parent, graph, verticesCount);
    }
}

Output

Edge	Weight
A - B	7
E - C	5
A - D	5
B - E	7
D - F	6
E - G	9
评论