• Skip to main content
  • Skip to primary sidebar
  • Skip to footer
  • About
  • Life
  • Tech
  • Travel
  • Work
  • Questions
  • Contact

Welcome

.

Implementing the pseudocode using matrix:

April 10, 2020 by

Questions › Implementing the pseudocode using matrix:
0
Vote Up
Vote Down
Garmaine asked 3 years ago

I need to implement the following code however in a matrix form. I need to get the source vertex and randomly generate the connected graph. However, the pseudo-code is in the list form and I am not sure if I converted it to the matrix form correctly, for the output for some reason i keep getting all the nodes to be fully explored or the color of them all becomes black?

D represents distance

π represent parents

colour = white unvisited/ grey visited/black all neighbours explored

enter image description here

     #include <iostream>
#include <limits>
#include <queue>
#include <stdlib.h>     /* srand, rand */

using namespace std;



enum  Color {white , gray, black};
struct vertex{

    Color color =white ;
   int relationship =0;
   int distance =abs(numeric_limits<int>::max());
   int parent =0;

};

void BFS(int size ,int s)
{
   //no need for first loop to initializer to defaults since they are already
    vertex g [size][size];
    int random;
    for(int i=0;i<size;i++)
    {
        for(int j=0;j<size;j++)
        {
            random =rand()%(size);
            if(j!=i and random!=i) //to make it undirected
            {
                g[i][random].relationship=1;
                g[random][i].relationship=1;

            }

        }

    }
   ///
   g[s][0].color =gray;
   g[s][0].distance=0;
   g[s][0].parent=0;
    queue <int> q;
    q.push(s);

    int u;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        g[u][0].color=black;
        for(int v=0;v<size;v++)
        {
            if (g[u][v].relationship==1 and g[v][0].color==white) {
                g[v][0].color = gray;
                g[v][0].distance = g[u][0].distance+1;
                g[v][0].parent = u;
                q.push(v);
            }


        }
    }


    for(int i = 0; i<size;i++)
    {

       for(int j =0;j<size;j++)
       {
           cout<<g[i][j].relationship <<" ";
       }
       cout<<endl;

    }
for(int i = 0; i<size;i++)
{

    cout<<" Distance of node: " << i<<" from the source is: ";
    cout<< g[i][0].distance<<" ";
    if(g[i][0].color==white)
    {
        cout<<" Color of node: " << i<<" is white";

    }
    if(g[i][0].color==gray)
    {
        cout<<" Color of node: " << i<<" is gray";

    }

    if(g[i][0].color==black){
        cout<<" Color of node: " << i<<" is black";

  }
    cout<<" parent of node: " << i<<" ";
    cout<< g[i][0].parent<<" "<<" ";
    cout<<endl;
   }

}
int main() {


    int vertices;
    cout<<"Please enter the number of vertices: "<<endl;
    cin>>vertices;
    int source;
    cout<<"Please enter the source  "<<endl;
    cin>>source;
    BFS(vertices,source);




    return 0;
}
Are you looking for the answer?
Original Question and Possible Answers can be found on `http://stackoverflow.com`

Question Tags: algorithm, breadth-first-search, c++, clrs, graph-algorithm

Please login or Register to submit your answer




Primary Sidebar

Tags

Advancements architecture beautiful life best building calling city commercial convenience employment Finances Cognitive decline Future gadgets Hidden Gems highway Home houses hydration Impact Innovations lamp lighting Mental health military tech Must-See New York City occupation Productivity recreation romance sepia shopping sippy cups smartphones social Technological breakthroughs technology toddlers Treasures turns Uncover Well-being Wonders Work Young onset dementia

Newsletter

Complete the form below, and we'll send you all the latest news.

Footer

Footer Funnies

Who knew that reading the footer could be such a hilarious adventure? As we navigate websites, books, and documents, we often stumble upon the unassuming space at the bottom, only to discover a treasure trove of amusement. In this side-splitting compilation, we present 100 jokes that celebrate the unsung hero of content – the footer. Get ready to chuckle, giggle, and maybe even snort as we dive into the world of footnotes, disclaimers, and hidden comedic gems. Brace yourself for a wild ride through the footer!

Recent

  • Unveiling the Enigma: Almost-Magical Lamp Lights Highway Turns
  • The Impact of Young Onset Dementia on Employment and Finances: Optimizing Post-Diagnostic Approaches
  • 11 Wonders of 2023 Technological Breakthrough – Unveiling the Future
  • Work from Home and Stay Mentally Sane – Achieve Productivity and Well-being
  • Hidden Gems of New York City – Uncover the Must-See Treasures!

Search

Tags

Advancements architecture beautiful life best building calling city commercial convenience employment Finances Cognitive decline Future gadgets Hidden Gems highway Home houses hydration Impact Innovations lamp lighting Mental health military tech Must-See New York City occupation Productivity recreation romance sepia shopping sippy cups smartphones social Technological breakthroughs technology toddlers Treasures turns Uncover Well-being Wonders Work Young onset dementia

Copyright © 2023