Please help with this question about Trees and Graghs(algorithm). Thank you! Doe
ID: 3688928 • Letter: P
Question
Please help with this question about Trees and Graghs(algorithm). Thank you!
Does either Prim's or Kruskal's algorithm work if there are negative edge weights? Explain. Give an algorithm to find a maximum spanning tree in a connected undirected graph. You are given a set of N sticks, which are lying on top of each other in some configuration. Each stick is represented by its two endpoints, which are ordered triple representing its x, y, and z coordinates. No stick is vertical, and a stick may be picked up only if there is no stick on top of it. Give an algorithm that determines whether it is possible to pick up all the sticks, and if so, provides a sequence of stick pickups that accomplishes this.Explanation / Answer
Prim’s and Kruskal’s algorithms with negative edge weights:
Start
Find MST (tree, graph) {
for each weight nearer to or adjacent to vertex v {
if (weight is unknown) {
let w2 = weight of the edge connecting the vertex v to vertex w;
if ( vertex v->distance + w2 < weight->distance) {
// get the latest values for weight
let weigth->distance = vertex v.distance + w2;
w2->pathCost = vertex v;
w2->numberOfPaths = vertex v -> numberOfPaths;
} // end if
else if ( vertex v->distance + w2 == weight -> distance)
weight -> numberOfPaths = weight -> numberOfPaths + vertex v -> numberOfPaths;
} // end if
} // end for loop
removeStickAtTop() {
topStick = topStick – 1; // pop a stick at the top
// only the top stick can be removed
}
PickupSticks (numberOfSticks N integer) {
bool feasibility;
let N = 20
Start with 20 sticks in a pack
r1 = rand() % 20 + 1
let r1 = a random number from 1 to 20
stick 1 = r1
int [] stickArray = new int[20];
let stickArray be an array of size 20 integers to represent each stick by a number
for loop from 1 to 20
for (int i = 1; i<= 20; i++) {
stickArray[i] = rand()%20 + 1;
print “stick at location” + i + “ is “ + stickArray[i];
}
placeSticks();
feasibility = removeStickAtTop();
return feasibility;
}