[讨论]图搜索+拓扑排序... - C语言论坛

中学者

等　级：版主
威　望：20
帖　子：3554
专家分：80
注　册：2007-9-14
结帖率：33.33%

楼主

问题点数：0 回复次数：17

[讨论]图搜索+拓扑排序...

用C接口我也来模拟一下OO....和DevC++通过..

/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http:// **
*****************************************************************/
#include<vector>
#include<queue>
#include<stack>
#include<iostream>

namespace graph
{
int gtime=0;  //  时间戳
enum COLOR { white, gray, black };  // 用于边的分类

template<typename _Ty>  // 顶点结构
struct vertex
{
    _Ty name;
    int value;
    int d;
    int time;
    vertex* parent,*next;
    COLOR color;
};

template<typename _Ty>
int getValue(vector<vertex<_Ty> >& g,_Ty ch)  //  返回把顶点名字的映射到向量的值
{
    for(int i=0;i<static_cast<int>(g.size());++i)
        if( g[i].name == ch) return g[i].value;
    return -1;
}

template<typename _Ty>
void createGraph(vector<vertex<_Ty> >& g,const int size_)  //  创建一个图
{
    std::cout<<"please input the name of vertex: \n";
    for(int i=0;i<size_;++i)
    {
        vertex<_Ty> vtex;
        std::cin>>vtex.name;
        vtex.d=vtex.time=0;
        vtex.next = vtex.parent=0;
        vtex.color = white;
        vtex.value = i;
        g.push_back(vtex);
    }
}

template<typename _Ty>
void addedge(vector<vertex<_Ty> >& g,const _Ty v,const _Ty u)  //  用于添有无向边
{
    int u_t=getValue(g,u),v_t=getValue(g,v);
    if(u_t!=-1&&v_t!=-1)
    {
    vertex<_Ty>* vtex=new vertex<_Ty>;
    vtex->d=vtex->time=0;
    vtex->parent =0;
    vtex->color = white;
    vtex->value = u_t;
    vtex->next = g[v_t].next;
    g[v_t].next = vtex;
    }
}

template<typename _Ty>
void waddedge(vector<vertex<_Ty> >& g,const _Ty v,const _Ty u)  //  用于添加无向边
{
    addedge(g,v,u);
    addedge(g,u,v);
}

template<typename _Ty>
void bfs(vector<vertex<_Ty> >& g,const _Ty s)  // 广度优先搜索
{
    std::queue<vertex<_Ty>*> que;
    que.push(&g[s]);
    g[s].color=gray;
    for(vertex<_Ty>* u ; !que.empty(); )
    {
        u = que.front();
        que.pop();
        for(vertex<_Ty>* check=g[u->value].next;check;check=check->next)
            if(g[check->value].color ==white)
            {
                g[check->value].color = gray;
                g[check->value].d = g[u->value].d+1;
                g[check->value].parent = &g[u->value];
                que.push(&g[check->value]);
            }
        g[u->value].color = black;
    }
}

template<typename _Ty>
void dfsVisite(vector<vertex<_Ty> >& g,const vertex<_Ty>& v)  //深度优先搜索
{// 递归版
    gtime+=1;
    g[v.value].d=gtime;
    g[v.value].color=gray;
    for(vertex<_Ty>* check=g[v.value].next;check;check=check->next)
        if(g[check->value].color==white)
        {
            g[check->value].parent=&g[v.value];
            dfsVisite(g,g[check->value]);
        }
    g[v.value].color=black;
    g[v.value].time=gtime=gtime+1;
}
template<typename _Ty>
void dfsVisite(vector<vertex<_Ty> >& g,const vertex<_Ty>& v,int)
{//用栈消递归版
    std::stack<vertex<_Ty>*> stk;
    gtime+=1;
    g[v.value].d=gtime;
    g[v.value].color=gray;
    stk.push(&g[v.value]);
    for(vertex<_Ty>* out;!stk.empty(); )
    {
        out=stk.top(),stk.pop();
        for(vertex<_Ty>* check=g[out->value].next;check;check=check->next)
            if(g[check->value].color==white)
        {
            g[check->value].color=gray;
            g[check->value].d=gtime=gtime+1;
            g[check->value].parent=&g[out->value];
            stk.push(&g[out->value]);
            out=&g[check->value];
            check=g[out->value].next;
        }
        g[out->value].color=black;
        g[out->value].time=gtime=gtime+1;
    }
}

template<typename _Ty>
void dfs(vector<vertex<_Ty> >& g)  //  深度搜索
{
    for(int i=0;i<static_cast<int>(g.size());++i)
        if(g[i].color==white)
        dfsVisite(g,g[i]);
}
template<typename _Ty>
void dfs(vector<vertex<_Ty> >& g,int w)
{
    for(int i=0;i<static_cast<int>(g.size());++i)
        if(g[i].color==white)
        dfsVisite(g,g[i],w);
}


template<typename _Ty>
void print(vector<vertex<_Ty> >& g)  //  输出图
{
    for(int i=0;i<static_cast<int>(g.size());++i)
    std::cout<<g[i].name<<": "
                <<g[i].d<<","<<g[i].time<<std::endl;
}

template<typename _Ty>
void freeGraph(vector<vertex<_Ty> >& g)  //  释放图
{
    if( !g.empty())
    {
        for(int i=0;i<static_cast<int>(g.size());++i)
        for(vertex<_Ty>* v=g[i].next,*t;v;)
        {
            t = v;
            v=v->next;
            delete t;
        }
            g.clear();
    }
}
}
int main(int argc, char *argv[])
{
    using graph::addedge;
    std::vector<graph::vertex<char> > v;
    std::cout<<"please input the size of graph: \n";
    int size_;
    std::cin>>size_;
    graph::createGraph(v,size_);
    std::cout<<"please input the number of edge: \n";
    std::cin>>size_;
    std::cout<<"please input edge which you want to link: \n";
    char chv,chu;
    for(int i=0;i<size_;++i)
    {
        std::cin>>chv>>chu;
        addedge(v,chv,chu);
    }
    graph::dfs(v);
    graph::print(v);
    graph::freeGraph(v);
    system("PAUSE");
    return EXIT_SUCCESS;
}

[[it] 本帖最后由中学者于 2008-5-31 17:22 编辑 [/it]]

[[it] 本帖最后由中学者于 2008-5-31 22:35 编辑 [/it]]