Prim 算法实现与赋值次数统计：最坏、平均、最好情况分析

由于 Prim 算法的实现方式可能有多种，本文将以最小堆实现 Prim 算法为例，编写 C 代码并统计赋值次数。

首先定义一个结构体表示图的边：

typedef struct {
    int start;
    int end;
    int weight;
} Edge;

其中 start 和 end 表示边的起点和终点，weight 表示边的权值。

接下来定义一个最小堆结构体，并实现相关函数：

typedef struct {
    Edge *data; // 存放边的数组
    int size; // 堆的大小
    int capacity; // 堆的容量
} MinHeap;

// 初始化最小堆
void initMinHeap(MinHeap *heap, int capacity) {
    heap->data = (Edge*)malloc(sizeof(Edge) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
}

// 向最小堆中插入一条边
void insertEdge(MinHeap *heap, Edge edge) {
    if (heap->size >= heap->capacity) {
        return;
    }
    heap->data[heap->size] = edge;
    int i = heap->size;
    while (i > 0 && heap->data[i].weight < heap->data[(i-1)/2].weight) {
        // 交换父节点和子节点
        Edge tmp = heap->data[i];
        heap->data[i] = heap->data[(i-1)/2];
        heap->data[(i-1)/2] = tmp;
        i = (i-1)/2;
    }
    heap->size++;
}

// 从最小堆中取出一条边
Edge popMinEdge(MinHeap *heap) {
    Edge minEdge = heap->data[0];
    heap->size--;
    heap->data[0] = heap->data[heap->size];
    int i = 0;
    while (i*2+1 < heap->size) {
        int left = i*2+1;
        int right = i*2+2;
        int j = left;
        if (right < heap->size && heap->data[right].weight < heap->data[left].weight) {
            j = right;
        }
        if (heap->data[i].weight <= heap->data[j].weight) {
            break;
        }
        // 交换父节点和子节点
        Edge tmp = heap->data[i];
        heap->data[i] = heap->data[j];
        heap->data[j] = tmp;
        i = j;
    }
    return minEdge;
}

// 判断最小堆是否为空
int isMinHeapEmpty(MinHeap *heap) {
    return heap->size == 0;
}

接下来是 Prim 算法的实现，以及统计赋值次数的代码：

#define MAX_N 1000 // 最大顶点数

int n; // 图的顶点数
int m; // 图的边数
int start; // Prim 算法的起点
int visited[MAX_N]; // 标记每个顶点是否被访问过
int dist[MAX_N]; // 存放每个顶点到最小生成树的距离
Edge edges[MAX_N * MAX_N]; // 存放所有边的数组
int edgeCount; // 边的数量
MinHeap heap; // 最小堆

// 初始化图
void initGraph() {
    scanf("%d %d %d", &n, &m, &start);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        edges[i].start = u;
        edges[i].end = v;
        edges[i].weight = w;
    }
    edgeCount = m;
}

// 统计赋值次数的变量
int assignCount = 0;

// Prim 算法
void prim() {
    // 初始化
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
        dist[i] = INT_MAX;
    }
    dist[start] = 0;
    visited[start] = 1;
    assignCount += 2;

    // 将起点的所有边加入最小堆中
    for (int i = 0; i < edgeCount; i++) {
        if (edges[i].start == start) {
            insertEdge(&heap, edges[i]);
            assignCount++;
        }
    }

    // 不断取出最小的边，并更新最小生成树
    while (!isMinHeapEmpty(&heap)) {
        Edge minEdge = popMinEdge(&heap);
        if (visited[minEdge.end]) {
            continue;
        }
        visited[minEdge.end] = 1;
        dist[minEdge.end] = minEdge.weight;
        assignCount += 2;

        // 将新加入的顶点的所有边加入最小堆中
        for (int i = 0; i < edgeCount; i++) {
            if (edges[i].start == minEdge.end && !visited[edges[i].end]) {
                insertEdge(&heap, edges[i]);
                assignCount++;
            }
        }
    }
}

int main() {
    initGraph();
    initMinHeap(&heap, MAX_N * MAX_N);
    prim();
    printf("Assign count: %d\n", assignCount);
    return 0;
}

以上代码实现了 Prim 算法，并统计了赋值次数。在计算赋值次数时，我们将每个变量的初始化也算作一次赋值，因此在初始化 visited 和 dist 数组时，assignCount 的值加 2。

最坏情况分析：

• 当图是一个完全图时，最坏情况下，我们需要遍历所有边，并将它们加入最小堆中。
• 在最小堆中，插入操作需要 O(log n) 的时间，删除操作也需要 O(log n) 的时间。
• 因此，最坏情况下，赋值次数为 O(m log n)。

平均情况分析：

• 在平均情况下，图的边数要少于完全图，因此赋值次数也会比最坏情况少。
• 平均情况下，赋值次数为 O(m log n)，但常数项会比最坏情况小。

最好情况分析：

• 在最好情况下，图是一个星型图，即只有一个中心节点，其他节点都与中心节点相连。
• 在这种情况下，我们只需要遍历所有与中心节点相连的边，并将其加入最小堆中。
• 最好情况下，赋值次数为 O(n)。

总结：

Prim 算法的时间复杂度取决于图的结构，最坏情况下为 O(m log n)，平均情况下为 O(m log n)，最好情况下为 O(n)。