Possible Solution
GraphMst
In this task you had the option of implementing Kruskal's algorithm or Prim's algorithm. We provide sample solutions using each below.
Kruskal's algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 | static Pq makeEdgesPq(Graph g);
static bool hasPath(Graph g, Vertex src, Vertex dest);
static bool doHasPath(Graph g, Vertex v, Vertex dest, bool *visited);
Graph GraphMst(Graph g) {
Graph mst = GraphNew(g->nV);
Pq pq = makeEdgesPq(g);
while (mst->nE < g->nV - 1 && !PqIsEmpty(pq)) {
struct edge e = PqExtract(pq);
if (!hasPath(mst, e.v, e.w)) {
GraphInsertEdge(mst, e);
}
}
PqFree(pq);
if (mst->nE == g->nV - 1) {
return mst;
} else {
GraphFree(mst);
return NULL;
}
}
static Pq makeEdgesPq(Graph g) {
Pq pq = PqNew();
for (int i = 0; i < g->nV; i++) {
for (int j = i + 1; j < g->nV; j++) {
if (g->edges[i][j] != 0.0) {
PqInsert(pq, (struct edge){i, j, g->edges[i][j]});
}
}
}
return pq;
}
static bool hasPath(Graph g, Vertex src, Vertex dest) {
bool *visited = calloc(g->nV, sizeof(bool));
assert(visited != NULL); // lazy error checking
bool res = doHasPath(g, src, dest, visited);
free(visited);
return res;
}
static bool doHasPath(Graph g, Vertex v, Vertex dest, bool *visited) {
visited[v] = true;
if (v == dest) {
return true;
}
for (int w = 0; w < g->nV; w++) {
if (g->edges[v][w] != 0.0 && !visited[w] &&
doHasPath(g, w, dest, visited)) {
return true;
}
}
return false;
}
|
Prim's algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | Graph GraphMst(Graph g) {
Graph mst = GraphNew(g->nV);
bool *inMst = calloc(g->nV, sizeof(bool));
assert(inMst != NULL); // lazy error checking
Pq pq = PqNew();
// We choose to start at vertex 0
inMst[0] = true;
for (int i = 0; i < g->nV; i++) {
if (g->edges[0][i] != 0.0) {
PqInsert(pq, (struct edge){0, i, g->edges[0][i]});
}
}
while (mst->nE < g->nV - 1 && !PqIsEmpty(pq)) {
struct edge e = PqExtract(pq);
if (!inMst[e.w]) {
GraphInsertEdge(mst, e);
int v = e.w
inMst[v] = true;
for (int i = 0; i < g->nV; i++) {
if (g->edges[v][i] != 0.0 && !inMst[i]) {
PqInsert(pq, (struct edge){v, i, g->edges[v][i]});
}
}
}
}
PqFree(pq);
free(inMst);
if (mst->nE == g->nV - 1) {
return mst;
} else {
GraphFree(mst);
return NULL;
}
}
|
planGrid1
The simplest way to solve this is to use GraphMst from the previous task.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 | static double distance(struct place p1, struct place p2);
int planGrid1(struct place cities[], int numCities,
struct place powerPlant,
struct powerLine powerLines[]) {
int powerPlantId = numCities;
Graph g = GraphNew(numCities + 1);
for (int i = 0; i < numCities; i++) {
double dist = distance(cities[i], powerPlant);
GraphInsertEdge(g, (struct edge){i, powerPlantId, dist});
for (int j = i + 1; j < numCities; j++) {
dist = distance(cities[i], cities[j]);
GraphInsertEdge(g, (struct edge){i, j, dist});
}
}
Graph mst = GraphMst(g);
int n = 0;
for (int i = 0; i < numCities; i++) {
if (GraphIsAdjacent(mst, i, powerPlantId)) {
powerLines[n++] = (struct powerLine){cities[i], powerPlant};
}
for (int j = i + 1; j < numCities; j++) {
if (GraphIsAdjacent(mst, i, j) != 0.0) {
powerLines[n++] = (struct powerLine){cities[i], cities[j]};
}
}
}
GraphFree(mst);
GraphFree(g);
return n;
}
static double distance(struct place p1, struct place p2) {
int dx = p1.x - p2.x;
int dy = p1.y - p2.y;
return sqrt(dx * dx + dy * dy);
}
|