I tried to allow decimal value in the result but however it still shows 0, what am i missing in the following codes?
I have declared the weight variable as a float value, but it won't convert as i input decimal in my graph.AddEdge(). Is there any error in my variable passing parameters?
#include <iostream>
#include <vector>
#include <list>
#include <utility> // for pair<>
#include <iomanip> // for setw()
#include <cmath> // for floor
#include <chrono>
using namespace std;
using namespace std::chrono;
/////////////// MinHeap ////////////////
struct HeapNode{
int key, element;
HeapNode():key(0),element(0){};
HeapNode(int key, int element):key(key),element(element){};
};
class BinaryHeap{
private:
vector<HeapNode> heap;
void swap(struct HeapNode &p1, struct HeapNode &p2);
int FindPosition(int node);
int GetParentNode(int node){return std::floor(node/2);};
public:
BinaryHeap(){heap.resize(1);};
BinaryHeap(int n){
heap.resize(n 1); // to store vertex and its distance
}
// Min-Priority Queue
void MinHeapify(int node, int length);
void BuildMinHeap(vector<int> array);
void DecreaseKey(int node, int newKey);
void MinHeapInsert(int node, int key);
int ExtractMin();
int Minimum(){return heap[1].element;};
bool IsHeapEmpty(){return (heap.size()<=1);};
};
int BinaryHeap::FindPosition(int node){
int idx = 0;
for (int i = 1; i < heap.size(); i ) {
if (heap[i].element == node) {
idx = i;
}
}
return idx;
}
void BinaryHeap::MinHeapInsert(int node, int key){
heap.push_back(HeapNode(node,key));
DecreaseKey(node, key);
}
void BinaryHeap::DecreaseKey(int node, int newKey){
int index_node = FindPosition(node); // search the index of node
if (newKey >= heap[index_node].key) {
cout << "new key is not smaller than current key\n";
return;
}
heap[index_node].key = newKey; // update key
// to check whether subtree fulfill minheap condition
while (index_node > 1 && heap[GetParentNode(index_node)].key > heap[index_node].key) {
swap(heap[index_node], heap[GetParentNode(index_node)]);
index_node = GetParentNode(index_node);
}
}
void BinaryHeap::swap(struct HeapNode &p1, struct HeapNode &p2){
struct HeapNode temp = p1;
p1 = p2;
p2 = temp;
}
int BinaryHeap::ExtractMin(){
if (IsHeapEmpty()) {
std::cout << "error: heap is empty\n";
exit(-1);
}
int min = heap[1].element;
// let min store the element, and return min
// delete the first element/vertex
heap[1] = heap[heap.size()-1]; // put the last element in the first position of heap
heap.erase(heap.begin() heap.size()-1); // delete the last element
MinHeapify(1, (int)heap.size()); // rearrange heap since heap[1] has the biggest value
return min;
}
void BinaryHeap::BuildMinHeap(std::vector<int> array){
// store array in heap (do not use heap[0])
for (int i = 0; i < array.size(); i ) {
heap[i 1].element = i; // let the idx in array as element
heap[i 1].key = array[i]; // let the value in array as key
}
for (int i = (int)heap.size()/2; i >= 1 ; i--) {
MinHeapify(i, (int)heap.size()-1); // length-1, since heap start from 1
}
}
void BinaryHeap::MinHeapify(int node, int length){
int left = 2*node, // get the left child
right = 2*node 1, // get the right child
smallest; // smallest will keep the smallest weight among vertices
if (left <= length && heap[left].key < heap[node].key)
smallest = left;
else
smallest = node;
if (right <= length && heap[right].key < heap[smallest].key)
smallest = right;
if (smallest != node) { // if the node key is not the smallest
swap(heap[smallest], heap[node]); // swap to get the smallest
MinHeapify(smallest, length); // rearrange the heap tree
}
}
/////////////// Prim's Algorithm /////////////////
static const int maxDistance = 100;
class Graph_MST{
private:
int num_vertex;
vector<list<pair<int,float> > > AdjList;
vector<int> predecessor, distance;
vector<bool> visited;
void InitializeSingleSource(int Start); // Let Start as the begin point
void PrintDataArray(vector<int> array);
public:
Graph_MST():num_vertex(0){};
Graph_MST(int n):num_vertex(n){
AdjList.resize(num_vertex);
}
void AddEdge(int from, int to, float weight);
void Prim_MinQueue(int Start);
friend class BinaryHeap;
};
void Graph_MST::InitializeSingleSource(int Start){
distance.resize(num_vertex);
predecessor.resize(num_vertex);
for (int i = 0; i < num_vertex; i ) {
distance[i] = maxDistance;
predecessor[i] = -1;
}
distance[Start] = 0; // set the starting vertex distance as 0, ExtractMin begins from starting vertex
}
void Graph_MST::Prim_MinQueue(int Start){
InitializeSingleSource(Start);
BinaryHeap minQueue(num_vertex);
minQueue.BuildMinHeap(distance); // use minQueue to handle distance[]
visited.resize(num_vertex, false); // initializa visited[] as {0,0,0,...,0}
while (!minQueue.IsHeapEmpty()) {
int u = minQueue.ExtractMin();
visited[u] = true;
for (list<pair<int, float> >::iterator itr = AdjList[u].begin();
itr != AdjList[u].end(); itr ) {
if (visited[(*itr).first] == false && (*itr).second < distance[(*itr).first]) {
distance[(*itr).first] = (*itr).second;
predecessor[(*itr).first] = u;
minQueue.DecreaseKey((*itr).first, distance[(*itr).first]);
}
}
}
/////// print result /////////
cout << setw(3) << "v1" << " - " << setw(3) << "v2"<< " : weight\n";
int i = (Start 1)%num_vertex;
while (i != Start) {
cout << setw(3) << predecessor[i] << " - " << setw(3) << i
<< " : " << setw(3) << distance[i] <<"\n";
i = ( i)%num_vertex; // After 6, 6 1 = 7, error:bad_access
}
}
void Graph_MST::AddEdge(int from, int to, float weight){
AdjList[from].push_back(std::make_pair(to,weight));
AdjList[to].push_back(std::make_pair(from,weight));
}
int main(){
Graph_MST graph(12);
graph.AddEdge(0, 1, 0.9); //ab
graph.AddEdge(0, 2, 0.7); //ac
graph.AddEdge(1, 3, 0.6); //bd
graph.AddEdge(1, 6, 0.7); //bg
graph.AddEdge(2, 3, 0.8); //cd
graph.AddEdge(2, 4, 0.6); //ce
graph.AddEdge(2, 5, 0.3); //cf
graph.AddEdge(3, 7, 0.5); //dh
graph.AddEdge(3, 5, 0.8); //df
graph.AddEdge(3, 9, 0.1); //dj
graph.AddEdge(4, 5, 0.5); //ef
graph.AddEdge(5, 9, 0.2); //fj
graph.AddEdge(5, 11, 0.3); //fh
graph.AddEdge(6, 8, 0.7); //gi
graph.AddEdge(7, 8, 0.4); //hi
graph.AddEdge(7, 11, 0.5); //hl
graph.AddEdge(7, 10, 0.3); //hk
graph.AddEdge(8, 10, 0.7); //ik
graph.AddEdge(8, 11, 0.8); //il
graph.AddEdge(9, 11, 0.5); //jl
graph.AddEdge(10, 11, 0.9); //kl
cout << "MST found by Prim_MinQueue:\n";
auto start = high_resolution_clock::now();
graph.Prim_MinQueue(2);
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
cout << "Time taken by function: "
<< duration.count() << " microseconds" << endl;
return 0;
}
//ref source: http://alrightchiu.github.io/SecondRound/minimum-spanning-treeprims-algorithm-using-min-priority-queue.html
Example output is shown:
CodePudding user response：
You're using a vector<int> instead of using a vector<float> for distance. You need to use vector<float> so that the elements are stored as float as shown below:
class Graph_MST{
private:
//other members here as before
vector<float> distance; //vector<int> changed to vector<float>
//other members here as before
};
class BinaryHeap{
private:
//other members here as before
public:
void BuildMinHeap(vector<float> array); //argument changed to vector<float>
};
void BinaryHeap::BuildMinHeap(std::vector<float> array){//argument changed to vector<float>
//code here as before
}
The output of the modified program can be seen here:
MST found by Prim_MinQueue:
new key is not smaller than current key
v1 - v2 : weight
2 - 3 : 0.8
2 - 4 : 0.6
2 - 5 : 0.3
1 - 6 : 0.7
3 - 7 : 0.5
7 - 8 : 0.4
3 - 9 : 0.1
7 - 10 : 0.3
7 - 11 : 0.5
2 - 0 : 0.7
3 - 1 : 0.6
Time taken by function: 147 microseconds