I was thinking in a way of implementing a graph in such that would let find a minimum spanning tree.Graph.h#ifndef GRAPH_H#define GRAPH_H#include <list>#include <vector>#include <utility>#include <iostream>#include <map>#include <queue>using namespace std;template <class KeyType, class WeightType>class Graph{public:    class Edge;    class Vertex;    typedef typename list<Vertex>::iterator VertexIt;    typedef typename list<Edge>::iterator EdgeIt;    class Vertex    {        friend class Graph;        Vertex(const KeyType& k);        bool addLink(const EdgeIt& e);        list<EdgeIt> incEdges;        KeyType key;    };    class Edge    {        friend class Graph;        Edge(const pair<VertexIt, VertexIt>& vp, const WeightType& w);        VertexIt adjVertexTo(const VertexIt& v);        pair<VertexIt, VertexIt> incVertices;        WeightType weight;    };    struct Link    {        Link(const pair<KeyType, KeyType>& kp, const WeightType& w);        pair<KeyType, KeyType> keyPair;        WeightType weight;    };    template <typename ItType> Graph(ItType lnBegin, const ItType& lnEnd);    ~Graph();    bool addLink(const Link& ln);    VertexIt findVertex(const KeyType& k);    void dfs(const VertexIt& v, map<KeyType, bool>& visited);    void dfs();    void bfs();    list<Vertex> vertices;    list<Edge> edges;};#include Graph.cpp#endif // GRAPH_HGraph.cpp#ifndef GRAPH_CPP#define GRAPH_CPP#include Graph.husing namespace std;template <class KeyType, class WeightType>template <typename ItType>Graph<KeyType, WeightType>::Graph(ItType lnBegin, const ItType& lnEnd){    vertices.push_back(Vertex(lnBegin->keyPair.first));    cout <<  Adding links: << endl;    for (; lnBegin != lnEnd; ++lnBegin)    {        if (addLink(*lnBegin) == true)        {            cout <<  Adding  ;        }        else        {            cout <<  Skiping ;        }        cout << lnBegin->keyPair.first             << <- << lnBegin->weight << ->             << lnBegin->keyPair.second             << endl;    }}template <class KeyType, class WeightType>Graph<KeyType, WeightType>::~Graph(){    //dtor}template <class KeyType, class WeightType>bool Graph<KeyType, WeightType>::addLink(const Link& ln){    VertexIt fKey = findVertex(ln.keyPair.first);    VertexIt sKey = findVertex(ln.keyPair.second);    VertexIt missing = vertices.end();    if (fKey != missing || sKey != missing)    {        if (fKey == missing)        {            vertices.push_back(Vertex(ln.keyPair.first));            fKey = --vertices.end();        }        if (sKey == missing)        {            vertices.push_back(Vertex(ln.keyPair.second));            sKey = --vertices.end();        }        edges.push_back(Edge(make_pair(fKey, sKey), ln.weight));        fKey->addLink(--edges.end());        sKey->addLink(--edges.end());        return true;    }    return false;}template <class KeyType, class WeightType>typename Graph<KeyType, WeightType>::VertexItGraph<KeyType, WeightType>::findVertex(const KeyType& k){    VertexIt it = vertices.begin();    VertexIt itEnd = vertices.end();    for (; it != itEnd; ++it)    {        if (it->key == k)        {            return it;        }    }    return itEnd;}template <class KeyType, class WeightType>Graph<KeyType, WeightType>::Vertex::Vertex(const KeyType& k){    key = k;}template <class KeyType, class WeightType>bool Graph<KeyType, WeightType>::Vertex::addLink(const EdgeIt& e){    incEdges.push_back(e);    return true;}template <class KeyType, class WeightType>Graph<KeyType, WeightType>::Edge::Edge(const pair<VertexIt, VertexIt>& vp, const WeightType& w) :    incVertices(vp), weight(w) { }template <class KeyType, class WeightType>Graph<KeyType, WeightType>::Link::Link(const pair<KeyType, KeyType>& kp, const WeightType& w) :    keyPair(kp), weight(w) { }template <class KeyType, class WeightType>typename Graph<KeyType, WeightType>::VertexItGraph<KeyType, WeightType>::Edge::adjVertexTo(const VertexIt& v){    if (incVertices.first == v)    {        return incVertices.second;    }    return incVertices.first;}template <class KeyType, class WeightType>void Graph<KeyType, WeightType>::dfs(){    map<KeyType, bool> visited;    dfs(vertices.begin(), visited);}template <class KeyType, class WeightType>void Graph<KeyType, WeightType>::dfs(const VertexIt& v, map<KeyType, bool>& visited){    visited[v->key] = true;    cout <<   << v->key;    typename list<EdgeIt>::iterator it = v->incEdges.begin();    typename list<EdgeIt>::iterator itEnd = v->incEdges.end();    for (; it != itEnd; ++it)    {        VertexIt w = (*it)->adjVertexTo(v);        if (!visited[w->key])        {            dfs(w, visited);        }    }}template <class KeyType, class WeightType>void Graph<KeyType, WeightType>::bfs(){    map<KeyType, bool> visited;    queue<VertexIt> q;    VertexIt v = vertices.begin();    q.push(v);    visited[v->key] = true;    cout <<   << v->key;    typename list<EdgeIt>::iterator it;    typename list<EdgeIt>::iterator itEnd;    while (!q.empty())    {        v = q.front();        q.pop();        it = v->incEdges.begin();        itEnd = v->incEdges.end();        for (; it != itEnd; ++it)        {            VertexIt w = (*it)->adjVertexTo(v);            if (!visited[w->key])            {                cout <<   << w->key;                q.push(w);                visited[w->key] = true;            }        }    }}#endifTest.cpp#include <iostream>#include Graph.husing namespace std;int main(){    typedef Graph<char, int> Graph;    typedef Graph::Link Link;    vector<Link> links;    links.push_back(Link(make_pair('A', 'B'), 2));    links.push_back(Link(make_pair('A', 'C'), 2));    links.push_back(Link(make_pair('A', 'E'), 2));    links.push_back(Link(make_pair('B', 'D'), 7));    links.push_back(Link(make_pair('B', 'F'), 7));    links.push_back(Link(make_pair('C', 'G'), 7));    links.push_back(Link(make_pair('E', 'F'), 5));    Graph myGraph(links.begin(), links.end());    myGraph.dfs();    myGraph.bfs();    return 0;}Is this implementation appropriate for finding minimum spanning tree? Could it be better?
Undirected, connected and weighted graph implementation
c++;graph