Untitled Document

Function

vector<Edge<T> > spanningTree();

Returns the edges that use to form minimum spanning tree for the graph.

Parameters

None

Return value

Return the vector of Edge that use to form spanning tree for the graph.

Example

#include "HKUAL_graph.h"
#include <iostream>
#include <vector>
using namespace std;
using namespace HKUAL;

int main(){
    int n;
    Graph<string> g;
    g.addVertex("A");
    g.addVertex("B");
    g.addVertex("C");
    g.addVertex("D");

	 g.addEdge("A","B",3);
    g.addEdge("A","C",10);
    g.addEdge("B","C",5);
    g.addEdge("C","D",7);
    g.addEdge("A","D",2);
    vector<Edge<string> > v = g.spanningTree();
    for (int i = 0; i < v.size(); i++)
        cout << v[i].X << ' ' << v[i].Y << endl;
    return 0;
}

Output

A B
A C
C D

Time Complexity

, for the weight of all edges are 1, is number of edges and is total number of vertices.
, for the weight of edges are different, is number of edges and is total number of vertices.

Graph::spanningTree

Parameters

Return value