我在过去的一天中一直在努力完成我的编程课，这是我的问题...我不知道该怎么做。
我了解Prim算法的基本概念:
1. Start at an arbitrary node (the first node will do) and
add all of its links onto a list.
2. Add the smallest link (which doesn't duplicate an existing path)
in the MST, to the Minimum Spanning Tree.
Remove this link from the list.
3. Add all of the links from the newly linked node onto the list
4. repeat steps 2 & 3 until MST is achieved
(there are no nodes left unconnected).
我已经获得了此图的实现(使用邻接表)以实现Prim的算法。问题是我不太了解实现。到目前为止，我对实现的理解如下:
作为邻接表，我们将所有节点都设置为数组形式:链接到此的是链接列表，其中包含权重，目标的详细信息，以及指向特定节点其余链接的指针:
看起来有点像这样:
[0] -> [weight = 1][Destination = 3] -> [weight = 6][Destination = 4][NULL]
[1] -> [weight = 4][Destination = 3][NULL]
and so on...
我们还有一个“Edge”结构，我认为该结构可以简化实现过程，但是我并没有真正看到它。
这是给出的代码:
GRAPH.h界面:
typedef struct {
int v;
int w;
int weight;
} Edge;
Edge EDGE (int, int, int);
typedef struct graph *Graph;
Graph GRAPHinit (int);
void GRAPHinsertE (Graph, Edge);
void GRAPHremoveE (Graph, Edge);
int GRAPHedges (Edge [], Graph g);
Graph GRAPHcopy (Graph);
void GRAPHdestroy (Graph);
int GRAPHedgeScan (Edge *);
void GRAPHEdgePrint (Edge);
int GRAPHsearch (Graph, int[]);
Graph GRAPHmst (Graph);
Graph GRAPHmstPrim (Graph);
#define maxV 8
GRAPH.c的实现:
#include <stdlib.h>
#include <stdio.h>
#include "GRAPH.h"
#define exch(A, B) { Edge t = A; A = B; B = t; }
#define max(A,B)(A>B?A:B)
#define min(A,B)(A<B?A:B)
typedef struct node *link;
struct node {
int v;
int weight;
link next;
};
struct graph {
int V;
int E;
link *adj;
};
static void sortEdges (Edge *edges, int noOfEdges);
static void updateConnectedComponent (Graph g, int from, int to, int newVal, int *connectedComponent);
Edge EDGE (int v, int w, int weight) {
Edge e = {v, w, weight};
return e;
}
link NEW (int v, int weight, link next) {
link x = malloc (sizeof *x);
x->v = v;
x->next = next;
x->weight = weight;
return x;
}
Graph GRAPHinit (int V) {
int v;
Graph G = malloc (sizeof *G);
// Set the size of the graph, = number of verticies
G->V = V;
G->E = 0;
G->adj = malloc (V * sizeof(link));
for (v = 0; v < V; v++){
G->adj[v] = NULL;
}
return G;
}
void GRAPHdestroy (Graph g) {
// not implemented yet
}
void GRAPHinsertE(Graph G, Edge e){
int v = e.v;
int w = e.w;
int weight = e.weight;
G->adj[v] = NEW (w, weight, G->adj[v]);
G->adj[w] = NEW (v, weight, G->adj[w]);
G->E++;
}
void GRAPHremoveE(Graph G, Edge e){
int v = e.v;
int w = e.w;
link *curr;
curr = &G->adj[w];
while (*curr != NULL){
if ((*curr)->v == v) {
(*curr) = (*curr)->next;
G->E--;
break;
}
curr= &((*curr)->next);
}
curr = &G->adj[v];
while (*curr != NULL){
if ((*curr)->v == w) {
(*curr) = (*curr)->next;
break;
}
curr= &((*curr)->next);
}
}
int GRAPHedges (Edge edges[], Graph g) {
int v, E = 0;
link t;
for (v = 0; v < g->V; v++) {
for (t = g->adj[v]; t != NULL; t = t->next) {
if (v < t->v) {
edges[E++] = EDGE(v, t->v, t->weight);
}
}
}
return E;
}
void GRAPHEdgePrint (Edge edge) {
printf ("%d -- (%d) -- %d", edge.v, edge.weight, edge.w);
}
int GRAPHedgeScan (Edge *edge) {
if (edge == NULL) {
printf ("GRAPHedgeScan: called with NULL \n");
abort();
}
if ((scanf ("%d", &(edge->v)) == 1) &&
(scanf ("%d", &(edge->w)) == 1) &&
(scanf ("%d", &(edge->weight)) == 1)) {
return 1;
} else {
return 0;
}
}
// Update the CC label for all the nodes in the MST reachable through the edge from-to
// Assumes graph is a tree, will not terminate otherwise.
void updateConnectedComponent (Graph g, int from, int to, int newVal, int *connectedComponent) {
link currLink = g->adj[to];
connectedComponent[to] = newVal;
while (currLink != NULL) {
if (currLink->v != from) {
updateConnectedComponent (g, to, currLink->v, newVal, connectedComponent);
}
currLink = currLink->next;
}
}
// insertion sort, replace with O(n * lon n) alg to get
// optimal work complexity for Kruskal
void sortEdges (Edge *edges, int noOfEdges) {
int i;
int l = 0;
int r = noOfEdges-1;
for (i = r-1; i >= l; i--) {
int j = i;
while ((j < r) && (edges[j].weight > edges[j+1].weight)) {
exch (edges[j], edges[j+1]);
j++;
}
}
}
Graph GRAPHmst (Graph g) {
Edge *edgesSorted;
int i;
int *connectedComponent = malloc (sizeof (int) * g->V);
int *sizeOfCC = malloc (sizeof (int) * g->V);
Graph mst = GRAPHinit (g->V);
edgesSorted = malloc (sizeof (*edgesSorted) * g->E);
GRAPHedges (edgesSorted, g);
sortEdges (edgesSorted, g->E);
// keep track of the connected component each vertex belongs to
// in the current MST. Initially, MST is empty, so no vertex is
// in an MST CC, therefore all are set to -1.
// We also keep track of the size of each CC, so that we're able
// to identify the CC with fewer vertices when merging two CCs
for (i = 0; i < g->V; i++) {
connectedComponent[i] = -1;
sizeOfCC[i] = 0;
}
int currentEdge = 0; // the shortest edge not yet in the mst
int mstCnt = 0; // no of edges currently in the mst
int v, w;
// The MST can have at most min (g->E, g->V-1) edges
while ((currentEdge < g->E) && (mstCnt < g->V)) {
v = edgesSorted[currentEdge].v;
w = edgesSorted[currentEdge].w;
printf ("Looking at Edge ");
GRAPHEdgePrint (edgesSorted[currentEdge]);
if ((connectedComponent[v] == -1) ||
(connectedComponent[w] == -1)) {
GRAPHinsertE (mst, edgesSorted[currentEdge]);
mstCnt++;
if (connectedComponent[v] == connectedComponent[w]) {
connectedComponent[v] = mstCnt;
connectedComponent[w] = mstCnt;
sizeOfCC[mstCnt] = 2; // initialise a new CC
} else {
connectedComponent[v] = max (connectedComponent[w], connectedComponent[v]);
connectedComponent[w] = max (connectedComponent[w], connectedComponent[v]);
sizeOfCC[connectedComponent[w]]++;
}
printf (" is in MST\n");
} else if (connectedComponent[v] == connectedComponent[w]) {
printf (" is not in MST\n");
} else {
printf (" is in MST, connecting two msts\n");
GRAPHinsertE (mst, edgesSorted[currentEdge]);
mstCnt++;
// update the CC label of all the vertices in the smaller CC
// (size is only important for performance, not correctness)
if (sizeOfCC[connectedComponent[w]] > sizeOfCC[connectedComponent[v]]) {
updateConnectedComponent (mst, v, v, connectedComponent[w], connectedComponent);
sizeOfCC[connectedComponent[w]] += sizeOfCC[connectedComponent[v]];
} else {
updateConnectedComponent (mst, w, w, connectedComponent[v], connectedComponent);
sizeOfCC[connectedComponent[v]] += sizeOfCC[connectedComponent[w]];
}
}
currentEdge++;
}
free (edgesSorted);
free (connectedComponent);
free (sizeOfCC);
return mst;
}
// my code so far
Graph GRAPHmstPrim (Graph g) {
// Initializations
Graph mst = GRAPHinit (g->V); // graph to hold the MST
int i = 0;
int nodeIsConnected[g->V];
// initially all nodes are not connected, initialize as 0;
for(i = 0; i < g->V; i++) {
nodeIsConnected[i] = 0;
}
// extract the first vertex from the graph
nodeIsConnected[0] = 1;
// push all of the links from the first node onto a temporary list
link tempList = newList();
link vertex = g->adj[0];
while(vertex != NULL) {
tempList = prepend(tempList, vertex);
vertex = vertex->next;
}
// find the smallest link from the node;
mst->adj[0] =
}
// some helper functions I've been writing
static link newList(void) {
return NULL;
}
static link prepend(link list, link node) {
link temp = list;
list = malloc(sizeof(list));
list->v = node->v;
list->weigth = node->weight;
list->next = temp;
return list;
}
static link getSmallest(link list, int nodeIsConnected[]) {
link smallest = list;
while(list != NULL){
if((list->weight < smallest->weight)&&(nodeIsConnected[list->v] == 0)) {
smallest = list;
}
list = list->next;
}
if(nodeIsConnected[smallest->v] != 0) {
return NULL;
} else {
return smallest;
}
}
为了清楚起见，请归档以从文件获取测试数据:
#include <stdlib.h>
#include <stdio.h>
#include "GRAPH.h"
// call with graph_e1.txt as input, for example.
//
int main (int argc, char *argv[]) {
Edge e, *edges;
Graph g, mst;
int graphSize, i, noOfEdges;
if (argc < 2) {
printf ("No size provided - setting max. no of vertices to %d\n", maxV);
graphSize = maxV;
} else {
graphSize = atoi (argv[1]);
}
g = GRAPHinit (graphSize);
printf ("Reading graph edges (format: v w weight) from stdin\n");
while (GRAPHedgeScan (&e)) {
GRAPHinsertE (g, e);
}
edges = malloc (sizeof (*edges) * graphSize * graphSize);
noOfEdges = GRAPHedges (edges, g);
printf ("Edges of the graph:\n");
for (i = 0; i < noOfEdges; i++) {
GRAPHEdgePrint (edges[i]);
printf ("\n");
}
mst = GRAPHmstPrim (g);
noOfEdges = GRAPHedges (edges, mst);
printf ("\n MST \n");
for (i = 0; i < noOfEdges; i++) {
GRAPHEdgePrint (edges[i]);
printf ("\n");
}
GRAPHdestroy (g);
GRAPHdestroy (mst);
free (edges);
return EXIT_SUCCESS;
}
提前致谢。
路加
完整文件:http://www.cse.unsw.edu.au/~cs1927/12s2/labs/13/MST.html
更新:我对此问题做了另一种尝试。这是更新的代码(上面的一项编辑，将graph_client.c更改为使用我编写的“GRAPHmstPrim”函数。
GRAPH_adjlist.c::
#include <stdlib.h>
#include <stdio.h>
#include "GRAPH.h"
#define exch(A, B) { Edge t = A; A = B; B = t; }
#define max(A,B)(A>B?A:B)
#define min(A,B)(A<B?A:B)
typedef struct _node *link;
struct _node {
int v;
int weight;
link next;
}node;
struct graph {
int V;
int E;
link *adj;
};
typedef struct _edgeNode *edgeLink;
struct _edgeNode {
int v;
int w;
int weight;
edgeLink next;
}edgeNode;
static void sortEdges (Edge *edges, int noOfEdges);
static void updateConnectedComponent (Graph g, int from, int to, int newVal, int *connectedComponent);
Edge EDGE (int v, int w, int weight) {
Edge e = {v, w, weight};
return e;
}
link NEW (int v, int weight, link next) {
link x = malloc (sizeof *x);
x->v = v;
x->next = next;
x->weight = weight;
return x;
}
Graph GRAPHinit (int V) {
int v;
Graph G = malloc (sizeof *G);
G->V = V;
G->E = 0;
G->adj = malloc (V * sizeof(link));
for (v = 0; v < V; v++){
G->adj[v] = NULL;
}
return G;
}
void GRAPHdestroy (Graph g) {
// not implemented yet
}
void GRAPHinsertE(Graph G, Edge e){
int v = e.v;
int w = e.w;
int weight = e.weight;
G->adj[v] = NEW (w, weight, G->adj[v]);
G->adj[w] = NEW (v, weight, G->adj[w]);
G->E++;
}
void GRAPHremoveE(Graph G, Edge e){
int v = e.v;
int w = e.w;
link *curr;
curr = &G->adj[w];
while (*curr != NULL){
if ((*curr)->v == v) {
(*curr) = (*curr)->next;
G->E--;
break;
}
curr= &((*curr)->next);
}
curr = &G->adj[v];
while (*curr != NULL){
if ((*curr)->v == w) {
(*curr) = (*curr)->next;
break;
}
curr= &((*curr)->next);
}
}
int GRAPHedges (Edge edges[], Graph g) {
int v, E = 0;
link t;
for (v = 0; v < g->V; v++) {
for (t = g->adj[v]; t != NULL; t = t->next) {
if (v < t->v) {
edges[E++] = EDGE(v, t->v, t->weight);
}
}
}
return E;
}
void GRAPHEdgePrint (Edge edge) {
printf ("%d -- (%d) -- %d", edge.v, edge.weight, edge.w);
}
int GRAPHedgeScan (Edge *edge) {
if (edge == NULL) {
printf ("GRAPHedgeScan: called with NULL \n");
abort();
}
if ((scanf ("%d", &(edge->v)) == 1) &&
(scanf ("%d", &(edge->w)) == 1) &&
(scanf ("%d", &(edge->weight)) == 1)) {
return 1;
} else {
return 0;
}
}
// Update the CC label for all the nodes in the MST reachable through the edge from-to
// Assumes graph is a tree, will not terminate otherwise.
void updateConnectedComponent (Graph g, int from, int to, int newVal, int *connectedComponent) {
link currLink = g->adj[to];
connectedComponent[to] = newVal;
while (currLink != NULL) {
if (currLink->v != from) {
updateConnectedComponent (g, to, currLink->v, newVal, connectedComponent);
}
currLink = currLink->next;
}
}
// insertion sort, replace with O(n * lon n) alg to get
// optimal work complexity for Kruskal
void sortEdges (Edge *edges, int noOfEdges) {
int i;
int l = 0;
int r = noOfEdges-1;
for (i = r-1; i >= l; i--) {
int j = i;
while ((j < r) && (edges[j].weight > edges[j+1].weight)) {
exch (edges[j], edges[j+1]);
j++;
}
}
}
Graph GRAPHmst (Graph g) {
Edge *edgesSorted;
int i;
int *connectedComponent = malloc (sizeof (int) * g->V);
int *sizeOfCC = malloc (sizeof (int) * g->V);
Graph mst = GRAPHinit (g->V);
edgesSorted = malloc (sizeof (*edgesSorted) * g->E);
GRAPHedges (edgesSorted, g);
sortEdges (edgesSorted, g->E);
// keep track of the connected component each vertex belongs to
// in the current MST. Initially, MST is empty, so no vertex is
// in an MST CC, therefore all are set to -1.
// We also keep track of the size of each CC, so that we're able
// to identify the CC with fewer vertices when merging two CCs
for (i = 0; i < g->V; i++) {
connectedComponent[i] = -1;
sizeOfCC[i] = 0;
}
int currentEdge = 0; // the shortest edge not yet in the mst
int mstCnt = 0; // no of edges currently in the mst
int v, w;
// The MST can have at most min (g->E, g->V-1) edges
while ((currentEdge < g->E) && (mstCnt < g->V)) {
v = edgesSorted[currentEdge].v;
w = edgesSorted[currentEdge].w;
printf ("Looking at Edge ");
GRAPHEdgePrint (edgesSorted[currentEdge]);
if ((connectedComponent[v] == -1) ||
(connectedComponent[w] == -1)) {
GRAPHinsertE (mst, edgesSorted[currentEdge]);
mstCnt++;
if (connectedComponent[v] == connectedComponent[w]) {
connectedComponent[v] = mstCnt;
connectedComponent[w] = mstCnt;
sizeOfCC[mstCnt] = 2; // initialise a new CC
} else {
connectedComponent[v] = max (connectedComponent[w], connectedComponent[v]);
connectedComponent[w] = max (connectedComponent[w], connectedComponent[v]);
sizeOfCC[connectedComponent[w]]++;
}
printf (" is in MST\n");
} else if (connectedComponent[v] == connectedComponent[w]) {
printf (" is not in MST\n");
} else {
printf (" is in MST, connecting two msts\n");
GRAPHinsertE (mst, edgesSorted[currentEdge]);
mstCnt++;
// update the CC label of all the vertices in the smaller CC
// (size is only important for performance, not correctness)
if (sizeOfCC[connectedComponent[w]] > sizeOfCC[connectedComponent[v]]) {
updateConnectedComponent (mst, v, v, connectedComponent[w], connectedComponent);
sizeOfCC[connectedComponent[w]] += sizeOfCC[connectedComponent[v]];
} else {
updateConnectedComponent (mst, w, w, connectedComponent[v], connectedComponent);
sizeOfCC[connectedComponent[v]] += sizeOfCC[connectedComponent[w]];
}
}
currentEdge++;
}
free (edgesSorted);
free (connectedComponent);
free (sizeOfCC);
return mst;
}
edgeLink newEdgeList(void) {
return NULL;
}
edgeLink addEdgeList(edgeLink list, int node, link edge) {
printf("EdgeListStart");
edgeLink temp = list;
list = malloc(sizeof(edgeNode));
list->w = node;
list->v = edge->v;
list->weight = edge->weight;
list->next = temp;
printf("EdgeListEnd");
return list;
}
edgeLink findSmallest(edgeLink waitList, int nodeIsConnected[]) {
printf("SmallestSTart");
edgeLink smallest = waitList;
int small = 99999;
while(waitList != NULL) {
if((waitList->weight < small)&&(nodeIsConnected[waitList->v] == 0)) {
smallest = waitList;
small = smallest->weight;
} else {
printf("\n\n smallest already used %d", waitList->v);
}
waitList = waitList->next;
}
printf("SmallestEnd");
if(nodeIsConnected[smallest->v] == 0){
return smallest;
} else {
printf("Returning NULL");
return NULL;
}
}
link addList(edgeLink smallest, link list, int v) {
printf(":istsatt");
link temp = list;
list = malloc(sizeof(node));
list->v = v;
list->weight = smallest->weight;
list->next = temp;
printf("Listend");
return list;
}
Graph GRAPHmstPrim (Graph g) {
Graph mst = GRAPHinit (g->V); // graph to hold the MST
int i = 0;
int v = 0;
int w = 0;
int nodeIsConnected[g->V]; // array to hold whether a vertex has been added to MST
int loopStarted = 0;
edgeLink smallest = NULL;
// initially all nodes are not in the MST
for(i = 0; i < g->V; i++) {
nodeIsConnected[i] = 0;
}
while((smallest != NULL)||(loopStarted == 0)) {
printf("v is : %d", v);
// add the very first node to the MST
nodeIsConnected[v] = 1;
loopStarted = 1;
// push all of its links onto the list
link vertex = g->adj[v];
edgeLink waitList = newEdgeList();
while(vertex != NULL) {
waitList = addEdgeList(waitList, v, vertex);
vertex = vertex->next;
}
// find the smallest edge from the list
// which doesn't duplicate a connection
smallest = findSmallest(waitList, nodeIsConnected);
// no nodes don't duplicate a connection
// return the current MST
if(smallest == NULL){
return mst;
}
// otherwise add the attributes to the MST graph
w = smallest->w;
v = smallest->v;
mst->adj[v] = addList(smallest, mst->adj[v], w);
mst->adj[w] = addList(smallest, mst->adj[w], v);
}
return mst;
}
变更摘要:
-添加了edgeList来保存可能输入到MST中的边缘
-数组nodeIsConnected []以跟踪节点是否在MST中
-选择最小节点的功能。如果没有不重复链接的节点，则返回NULL
最佳答案
看来这似乎是家庭作业，所以我不会在代码中给出整个答案。您的代码似乎在正确的轨道上。实际上，您需要做的下一步就是将临时列表中最小的链接添加到您的mst。通过从列表中添加最小的节点，您实际上是在将(部分构建的)mst连接到尚未在mst中的节点。权重最小的链接始终是将mst中的节点连接到其他节点的最便宜的方法。
当您添加最小的链接时，您将在部分构建的树中添加一个节点，并且需要更新您的临时列表。您需要将新节点的所有链接添加到列表中。完成此操作后，临时列表将包含部分构建的mst中所有节点的所有链接。您继续添加节点的过程，直到所有节点都在您的mst中。
添加最便宜的链接时，您需要检查是否将新节点连接到mst。最便宜的链接可能是连接您的mst中已经存在的2个节点。如果是这样，则需要跳过该链接，然后选择下一个最便宜的链接。实际上，有几种处理方法。您可以维护mst中已经存在的节点的集合/vector ，可以维护 bool vector 以跟踪节点的状态，或者确保您的临时列表仅包含连接新节点的链接(尽管这是最密集的方法) 。
关于c - 用于MST的Prim算法，C语言中的邻接表实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12995730/