suppose that i have a un-directed graph with 10 vertices and 24 edges which connects with each other, as an example if i give an input like this (this is not the actual one, actual one is 10*10)
int graph[][] = new int[][]{{0, 0, 0, 0, 0, 0},
{0, 0, 2, 0, 6, 0},
{0, 2, 0, 3, 8, 5},
{0, 0, 3, 0, 0, 7},
{0, 6, 8, 0, 0, 9},
{0, 0, 5, 7, 9, 0}};
so i want to find the minimum connectors in order to connect specific vertices ex: vertices 0,2,4. currently i applied the prims algorithm in order to get the minimum connectors through out all the edges of the graph, but as i don't want all the edges to be included in my MST i need some help achieving this.
please help.
So you have 6 vertices and 7 undirected weighted edges:
1 ←→ 2 (w=2)
1 ←→ 4 (w=6)
2 ←→ 3 (w=3)
2 ←→ 4 (w=8)
2 ←→ 5 (w=5)
3 ←→ 5 (w=7)
4 ←→ 5 (w=9)
You need to connect vertices 0, 2, and 4, so you build a new graph with those 3 vertices, and find the shortest paths between them.
0 ←→ 2 (no edge)
0 ←→ 4 (no edge)
2 ←→ 4 (w=8)
That of course cannot be done, since there are no edges to vertex 0.
So let's try vertices 1, 3, and 5 instead:
1 ←→ 3 (w=5, 1 ←→ 2 ←→ 3)
1 ←→ 5 (w=7, 1 ←→ 2 ←→ 5)
3 ←→ 5 (w=7, 3 ←→ 5)
Now apply a minimum spanning tree (MST) to that:
1 ←→ 3 ←→ 5 (w=12)
Expanding back to original graph:
1 ←→ 2 ←→ 3 ←→ 5 (w=12)