欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

B00015 C++实现的图类

程序员文章站 2022-03-26 19:26:40
代码来自:github - obscure76/graph: c++ graphs。 graph.h文件内容如下: #include #include

代码来自: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();
};
graph.cpp文件内容如下:
#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;
}