#include <iostream>
#include "graph.h"

using namespace std;


void main(void)
{
    Graphs* g = new Graphs;
    GraphFactory fac;

    Vertex* a = fac.MakeVertex('a');
    Vertex* b = fac.MakeVertex('b');
    Vertex* c = fac.MakeVertex('c');
    Vertex* d = fac.MakeVertex('d');
    Vertex* e = fac.MakeVertex('e');
    Vertex* f = fac.MakeVertex('f');
    Vertex* G = fac.MakeVertex('g');
    Vertex* h = fac.MakeVertex('h');
    Vertex* i = fac.MakeVertex('i');

    a->Add_Edge(fac.MakeEdge(a, b, 35));
    a->Add_Edge(fac.MakeEdge(a, e, 247));

    b->Add_Edge(fac.MakeEdge(b, a, 35));
    b->Add_Edge(fac.MakeEdge(b, c, 126));
    b->Add_Edge(fac.MakeEdge(b, f, 150));


    c->Add_Edge(fac.MakeEdge(c, b, 126));
    c->Add_Edge(fac.MakeEdge(c, d, 117));
    c->Add_Edge(fac.MakeEdge(c, f, 162));
    c->Add_Edge(fac.MakeEdge(c, G, 220));

    d->Add_Edge(fac.MakeEdge(d, c, 117));

    e->Add_Edge(fac.MakeEdge(e, a, 247));
    e->Add_Edge(fac.MakeEdge(e, f, 82));
    e->Add_Edge(fac.MakeEdge(e, h, 98));

    f->Add_Edge(fac.MakeEdge(f, b, 150));
    f->Add_Edge(fac.MakeEdge(f, c, 162));
    f->Add_Edge(fac.MakeEdge(f, e, 82));
    f->Add_Edge(fac.MakeEdge(f, G, 154));
    f->Add_Edge(fac.MakeEdge(f, h, 120));

    G->Add_Edge(fac.MakeEdge(G, c, 220));
    G->Add_Edge(fac.MakeEdge(G, f, 154));
    G->Add_Edge(fac.MakeEdge(G, i, 106));


    h->Add_Edge(fac.MakeEdge(h, e, 98));
    h->Add_Edge(fac.MakeEdge(h, f, 120));

    i->Add_Edge(fac.MakeEdge(i, G, 106));


    g->Add_Vertex(a);
    g->Add_Vertex(b);
    g->Add_Vertex(c);
    g->Add_Vertex(d);
    g->Add_Vertex(e);
    g->Add_Vertex(f);
    g->Add_Vertex(G);
    g->Add_Vertex(h);
    g->Add_Vertex(i);

    g->BFS(a);
}



#include <list>
#include <stack>
#include <queue>

using namespace std;
typedef char mt;

class Vertex;
class Edge;
class Graphs;

enum visit {visited,notVisited};

class Vertex
{
public:
    mt data;
    int visited;

    list<Edge*> adList;

    Vertex(mt d=0):adList(0){
        >        visited = notVisited;
    }
    ~Vertex(){
        adList.clear();
    }
    void Add_Edge(Edge* e){
        adList.push_back(e);
    }

};

class Edge
{
public:
    int weight;
    Vertex* from;
    Vertex* to;

    Edge(){}
    Edge(Vertex* f, Vertex* t,int w) :weight(0), from(f), to(t){    }
    ~Edge(){ from = NULL; to = NULL; }
};

class Graphs
{
private:
    list<Vertex*> vertices;
public:
    Graphs() :vertices(0){ }
    ~Graphs(){
        vertices.clear();
    }
    void Add_Vertex(Vertex* v){
        vertices.push_back(v);
    }
    void TestPrint() ;
    void DFS(Vertex* v);
    void BFS(Vertex* v);
};
void Graphs::TestPrint()
{
    list<Vertex*>::iterator vIter;
    for (vIter = vertices.begin(); vIter != vertices.end(); vIter++){
        cout << (*vIter)->data << endl;
    }
}
void Graphs::DFS(Vertex* v)
{
    list<Edge*>::iterator eIter;
    cout << v->data<<" ";
    v->visited = visited;
    for (eIter = v->adList.begin(); eIter != v->adList.end(); ++eIter){
        if ((*eIter)->to != NULL && (*eIter)->to->visited == notVisited)
            DFS((*eIter)->to);
    }
}
void Graphs::BFS(Vertex* v)
{
    list<Edge*>::iterator eIter;
    queue<Vertex*> que;
    Vertex* cur;
    que.push(v);

    while (!que.empty()){
        cur = que.front();
        if (cur->visited == visited){
            que.pop();
            continue;
        }
        cout << cur->data << " ";
        cur->visited = visited;
        que.pop();
        eIter = cur->adList.begin();
        while (eIter != cur->adList.end()){
            if ((*eIter)->to->visited == notVisited){
                que.push((*eIter)->to);
            }
            ++eIter;
        }
    }

}
class GraphFactory
{
public:
    Edge* MakeEdge(Vertex* f, Vertex* t, int w){
        return new Edge( f, t,w);
    }
    Vertex* MakeVertex(mt d){
        return new Vertex(d);
    }
};