0

我在让 Prim 的这种实现来跟踪它找到的最短路径的总权重时遇到了一些麻烦。路径似乎是正确的，但我无法弄清楚在将权重添加到存储路径的数组中时将它们求和的位置（因为它只是为了存储使用的路径而编写的）。

我尝试将 pCrawl->weight 求和，因为每个顶点都添加到 MST 中，但这似乎是图表上所有权重的总和。与值 key[] 相同。

我的问题是每次将路径添加到 MST 时可以求和什么，以反映添加所有最短路径时 MST 的总权重。

这是我正在使用的代码：http: //pastebin.com/TFLGCE0L

我制作的邻接表：http: //pastebin.com/SvgGjEPj

以及用于创建它的地图：地图

Prim 的函数如下所示：

// The main function that constructs Minimum Spanning Tree (MST)
// using Prim's algorithm
void PrimMST(struct Graph* graph) 
{
int V = graph->V;// Get the number of vertices in graph
int parent[V];   // Array to store constructed MST
int key[V];      // Key values used to pick minimum weight edge in cut

// minHeap represents set E
struct MinHeap* minHeap = createMinHeap(V);

// Initialize min heap with all vertices. Key value of
// all vertices (except 0th vertex) is initially infinite
for (int v = 1; v < V; ++v)
{
    parent[v] = -1;
    key[v] = INT_MAX;
    minHeap->array[v] = newMinHeapNode(v, key[v]);
    minHeap->pos[v] = v;
}

// Make key value of 0th vertex as 0 so that it
// is extracted first
key[0] = 0;
minHeap->array[0] = newMinHeapNode(0, key[0]);
minHeap->pos[0]   = 0;

// Initially size of min heap is equal to V
minHeap->size = V;

// In the followin loop, min heap contains all nodes
// not yet added to MST.
while (!isEmpty(minHeap))
{
    // Extract the vertex with minimum key value
    struct MinHeapNode* minHeapNode = extractMin(minHeap);
    int u = minHeapNode->v; // Store the extracted vertex number

    // Traverse through all adjacent vertices of u (the extracted
    // vertex) and update their key values
    struct AdjListNode* pCrawl = graph->array[u].head;
    while (pCrawl != NULL)
    {
        int v = pCrawl->dest;

        // If v is not yet included in MST and weight of u-v is
        // less than key value of v, then update key value and
        // parent of v
        if (isInMinHeap(minHeap, v) && pCrawl->weight < key[v])
        {
            key[v] = pCrawl->weight;
            parent[v] = u;
            decreaseKey(minHeap, v, key[v]);
        }
        pCrawl = pCrawl->next;
    }
}

使用的结构如下所示：

// A structure to represent a node in adjacency list
struct AdjListNode
{
    int dest;
    int weight;
    struct AdjListNode* next;
};

// A structure to represent an adjacency liat
struct AdjList
{
    struct AdjListNode *head;  // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
    int V;
    struct AdjList* array;
};
// Structure to represent a min heap node
struct MinHeapNode
{
    int  v;
    int key;
};

// Structure to represent a min heap
struct MinHeap
{
    int size;      // Number of heap nodes present currently
    int capacity;  // Capacity of min heap
    int *pos;     // This is needed for decreaseKey()
    struct MinHeapNode **array;
};

我觉得我在这门数据结构课程中不知所措，因此尝试使用互联网上的代码来解决这一小部分作业而没有充分理解：/

谢谢，

迈克尔

4

1 回答 1

1

你在做正确的事。最小权重的总和（来自 Prim 的）可以等于图表上所有权重的总和。考虑当图中有 4 个节点并且节点 1 位于中心并以 w 的权重连接到节点 2、3 和 4 的情况。2、3 和 4 之间没有连接。在这种情况下，Prim 的重量将为 3*w，与总重量相同。我建议您使用几种不同的情况，这样可以澄清我的意思。

编辑：

这是问题所在，您没有正确更新总和。这个 -

weightTotal += pCrawl->weight

应该 -

weightTotal += pCrawl->weight - key[v]
于 2014-05-10T22:11:08.373 回答