Prim's Algorithm..How to identify connectivity

May 21, 2016 at 3:49am
Hi.

I need to know how can I identify connectivity of two nodes? Please give me some hint or code to understand this.

Thanks
May 21, 2016 at 12:31pm
Prim's algorithm works over a graph, which is the structure identifying the connectivity of nodes. You must have a graph defined.

Three common ways to do it are:
   - a 2D array
   - a std::map (or equivalent)
   - a linked list of nodes

For example, the following graph:
    โ”Œโ”€โ”€โ”
    โ”‚  โ†“
    โ””โ”€(0)โ†โ”€โ†’(1)โ”€โ”€โ†’(2)    
       โ†‘           โ”‚
       โ””โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”˜

can be described by the 2D array:
1
2
3
4
5
{
  { 1, 1, 0 },
  { 1, 0, 1 },
  { 1, 0, 0 }
}

where rowโ†’column.

Hope this helps.
May 22, 2016 at 3:02pm
Thanks
Topic archived. No new replies allowed.