B00015 C++实现的图类

代码来自：github - obscure76/graph: c++ graphs。

graph.h文件内容如下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<climits>
#define maxsize 100
using namespace std;


class vertex
{
    private:
        pair<int, vertex=""> > v;
    public:
        vertex(){};
        vertex(int);
        bool addadjvertex(int);
        friend bool operator==(vertex const &, vertex const &);
        friend bool operator<(vertex const &,  vertex const &);
        friend bool operator>(vertex const &,  vertex const &);
};

class edge
{
    private:
        int weight;
        int src;
        int dst;
    public:
        edge(){};
        edge(int, int, int);
        ~edge(){};
        friend bool operator==(edge const &,  edge const &);
        //friend bool operator<(edge const &,  edge const &);
        //friend bool operator>(edge const &,  edge const &);
        int getweight();
        int getsource();
        int getdest();
};

class graph
{
    private:
        map<int, int=""> > vertices;
        list<edge> edges;
        set<int> visited;
    public:
        graph();
        bool addvertex(int);
        bool addedge(int, int, int);
        bool deletevertex(int);
        void print();
        void bfs();
        void dfstraversal();
        void dfs(int, list<int>);
        void pathsum(int);
        void findpath(int, int, char *, int, int);
        void bellman();
        list<int> topologicalsort();
        void topo();
};

#include<graph.h>

vertex::vertex(int v)
{
}
bool vertex::addadjvertex(int v) 
{
}

list<int> order;
bool operator==(vertex const &v1, vertex const &v2)
{
    return true;
}
bool operator<(vertex const &v1, vertex const &v2)
{
    return true;
}

bool operator>(vertex const &v1, vertex const &v2)
{
    return true;
}

edge::edge(int a, int s1, int s2)
{
    weight = a;
    src = s1;
    dst = s2;
}

int edge::getweight(){return weight;}
int edge::getsource(){return src;}
int edge::getdest(){return dst;}

bool operator==( edge const &e1, edge const & e2)
{
    if(e1.weight==e2.weight && e1.src==e2.src && e1.dst == e2.dst)
        return true;
    return false;
}


graph::graph(){}

bool graph::addvertex(int v)
{
    list<int> adjlist;
    vertices.insert(pair<int, list<int> >(v, adjlist));    
}
bool graph::addedge(int wt, int s, int d)
{
    edges.push_back(edge(wt, s, d));
    map<int, list<int> >::iterator sit = vertices.find(s);
    if(sit!=vertices.end())
        sit->second.push_back(d);
    else
    {
        list<int> adjlist;
        adjlist.push_back(d);
        vertices.insert(pair<int, list<int> >(s, adjlist));
    }
    sit = vertices.find(d);
    if(sit == vertices.end())
    {
        list<int> adjlist1;
        vertices.insert(pair<int, list<int> >(d, adjlist1));
    }
}
bool graph::deletevertex(int v)
{
}
void graph::print()
{
    map<int, list<int> >::iterator it;
    for(it = vertices.begin();it!=vertices.end();it++)
    {	
        cout<<"node "<<it->first<<'-';
        for(list<int>::iterator lit = it->second.begin();lit!=it->second.end();lit++)
            cout<<*lit<<',';
        cout<<endl;
    }
}
void graph::bfs()
{
    queue<int> q;
    visited.clear();
    q.push(vertices.begin()->first);
    visited.insert(vertices.begin()->first);
    cout<<"\n bfs traversal :";
    while(q.size() > 0)
    {
        int v = q.front();
        q.pop();
        list<int> adjlist = vertices.find(v)->second;
        list<int>::iterator it;
        set<int>::iterator sit;
        for(it = adjlist.begin();it!=adjlist.end();it++)
        {
            sit = visited.find(*it);
            if(sit!=visited.end())
                continue;
            visited.insert(*it);
            q.push(*it);
        }
        cout<<v<<" ";
    }
}

void graph::dfstraversal()
{
    visited.clear();
    cout<<"\ndfs traversal :";
    map<int, list<int> >::iterator it;
    for(it = vertices.begin();it!=vertices.end();it++)
    {
        if(visited.find(it->first) != visited.end())
            continue;
        visited.insert(it->first);
        dfs(it->first, it->second);
    }
    cout<<endl;
}

void graph::dfs(int v, list<int> adj)
{
    list<int>::iterator lit;
    for(lit = adj.begin();lit!=adj.end();lit++)
    {
        if(visited.find(*lit) != visited.end())
            continue;
        visited.insert(*lit);
        dfs(*lit, vertices.find(*lit)->second);
    }
    cout<<v<<' ';
    order.push_front(v);
}

void graph::pathsum(int sum)
{
    char *str;
    str = (char *)malloc(100);
    memset(str, 0, 100);
    visited.clear();
    map<int, list<int> >::iterator it;
    it = vertices.begin();
    findpath(sum, 0, str, 0, it->first);
}

void graph::findpath(int sum, int cval, char *str, int in, int curr)
{
    if(curr+cval > sum)
        return;
    if(cval+curr == sum)
    {
        str[in] = '0' + curr;
        str[in+1] = '\0';
        cout<<str<<endl;
        visited.insert(curr);
        if(visited.find(curr)==visited.end())
            findpath(sum, 0, str, 0, curr);
    } else {
        cval += curr;
        //cout<<"cval now"<<cval<<'\t';
        str[in] = '0'+curr;
        map<int, list<int> >::iterator it;
        it = vertices.find(curr);
        if(it==vertices.end())
            return;
        list<int> adj = it->second;
        for(list<int>::iterator lit = adj.begin();lit!=adj.end();lit++)
            findpath(sum, cval, str, in+1, *lit);
        for(list<int>::iterator lit = adj.begin();lit!=adj.end();lit++)
        {
            if(visited.find(*lit)==visited.end())
            {
                visited.insert(*lit);
                findpath(sum, 0, str, 0, *lit);
            }
        }
    }
}

void graph::bellman()
{
    order.clear();
    dfstraversal();
    map<int, int> vd;
    map<int, list<int> >::iterator it;
    int vlen = vertices.size();
    for(it = vertices.begin();it!=vertices.end();it++)
        vd.insert(pair<int, int>(it->first, int_max));
    vd.find(vertices.begin()->first)->second = 0;
    list<int>::iterator lit;
    for(lit=order.begin();lit!=order.end();lit++)
    {
        list<edge>::iterator it;
        for(it = edges.begin();it!=edges.end();it++)
        {
            int src = it->getsource();
            int dst = it->getdest();
            int wt = it->getweight();
            if(src!=*lit)
                continue;
            if(vd.find(dst)->second > vd.find(src)->second+wt)
                vd.find(dst)->second = vd.find(src)->second+wt;
        }
    }
    map<int, int>::iterator mit;
    for(mit = vd.begin();mit!=vd.end();mit++)
        cout<<mit->first<<" at dist "<<mit->second<<endl;
}

list<int> graph::topologicalsort()
{
    order.clear();
    dfstraversal();
    for(list<int>::iterator it = order.begin();it!=order.end();it++)
        cout<<*it;
    return order;
}

void graph::topo()
{
    order.push_back(4);
}

int main()
{
    graph g;
    g.addedge(1,1,2);
    g.addedge(1,1,3);
    g.addedge(1,2,4);
    g.addedge(1,2,5);
    g.addedge(1,3,6);
    g.addedge(1,3,8);
    g.print();
    g.bfs();
    g.dfstraversal();
    g.pathsum(8);
    cout<<endl;
    g.topologicalsort();
    cout<<endl;
    g.bellman();
    return 0;
}