封装两种DirectedGraph结构,在写泛化VDiGraphEx时考虑的不是很周全,一开始犹豫是用Vector还是Array实现对边和结点的打包,考虑到图结构的递归特性,如果用Array对空间消耗较大,另一方面映射表已经解决了时间效率问题,那么非映射表型的图决定采取其互补形式设计.


另一方面,对删除边和结点的时候,需要考虑如何做效率才高,但是主索引list与边和结点并没有相互索引的能力,所以效率不是很高,有重复索引的嫌疑.

0 主要功能已经实现.
1 没有用SmartPtr管理,但是这样也节省了很多中转时间,除了中途为了提高效率直接用指针p索引产生了难以发现的bug外,可预见的范围似乎不会造成内存泄露,因所有数据都被VChain装箱.
2 status和arc都有key,这样方便唯一化数据.
3 实现了部分BFS和DFS,有空需要改进递归实参传值,把参数内置化.另外由于时间问题,写遍历的时候第一个被加进来的结点必须能到达其他所有结点,有空再把循环索引内容实现,实现广义上的图遍历.


有空还需要去借鉴下其他比较好的实现,欢迎各位来散步的指出不足之处,非常感谢.

#ifndef VG_GRAPH

#define VG_GRAPH


#include "VGMatrix.h"
#include "VGArray.h"
#include "VGChain.h"

namespace VGAdt
{

    using VGAdt::VArray;
    template<typename VTypeN,typename VTypeE=VTypeN>
    class VDiGraph:public VGBase::VAdt
    {
    public:
        VGMatrix<VTypeE> graArr;
        VArray<VTypeN> nodeValue;
        int nodeNum;
        int maxNum;
        VDiGraph(int maxNum_,VTypeE z,VTypeE o)
        {
            nodeNum=0;
            maxNum=maxNum_;
            graArr.setKey(z,o);
            graArr.rebirth(maxNum,maxNum);
        }
        int addNode(VTypeN value_)
        {
            nodeValue[nodeNum]=value_;
            ++nodeNum;
        }
        int setValue(int i_,VTypeN value_)
        {
            if(i_>=nodeNum)
            {
                i=nodeNum;
                ++nodeNum;
            }else if(i_<=-1)
            {
                return 0;
            }
            nodeValue[i_]=value_;
            return 1;
        }
        int setArc(int i_,int j_,VTypeE weights)
        {
            if(i_>=maxNum||j_>=maxNum)
            {
                return 0;
            }
            if(i_>=nodeNum||j_>=nodeNum)
                ++nodeNum;
            graArr[i_][j_]=weights;
            return 1;
        }
        VTypeE isGo(int i_,int j_)
        {
            if(graArr[i_][j_]==graArr.VOne_)
            {
                return graArr.VOne_;
            }else
            {
                return graArr[i_][j_];
            }
        }
        int isGoBy(int i_,VTypeE w_)
        {
            for(int i=0;i!=nodeNum;i++)
            {

                if(graArr[i_][i]==w_)
                    return i;
            }
            return -1;
        }
        VArray<VTypeE>& operator [](int i_)
        {
            return graArr[i_];
        }


    };
    using VGAdt::VChain;
    template<typename VTypeN,typename VTypeE=VTypeN>
    class VDiGraphEx :public VGBase::VAdt
    {
    public:
        struct VEdge;
        struct VStatus;
        struct VArc
        {
            VStatus * end;
            VStatus * start;
            VTypeE value;
            int key;

        };
        struct VStatus
        {
            VChain<VArc*> inArc;
            VChain<VArc*> outArc;
            VTypeN value;
            int key;
            VStatus* findOut(int key_)
            {
                outArc.p=outArc.head->next;
                for(int i=0;i!=outArc.size;i++)
                {
                    if(outArc.p->elem->end->key==key_)
                    {
                        return outArc.p->elem->end;
                    }
                    outArc.p=outArc.p->next;
                }
                return 0;
            }
            int delArc(VStatus* s_)
            {
                for(int i=0;i!=inArc.size;i++)
                {
                    if(inArc[i]->end==s_||inArc[i]->start==s_)
                    {
                        delete inArc[i];
                        inArc.Del(i);
                        --i;
                    }
                }
                return 1;
            }
        };
        int vNum;
        int eNum;
    public:
        VStatus * src;
        VStatus * pos;
        VChain<VStatus*> statusList;
        VChain<VArc*> arcList;
        VDiGraphEx()
        {
            vNum=0;
            eNum=0;
            src=pos=0;

        }
        ~VDiGraphEx()
        {
            emptyArcs();
            emptyStatus();
        }
        int isGo(int key_start,int key_end)
        {
            VStatus * state_start=(*this)[key_start];
            if(state_start->findOut(key_end))
            {
                return 1;
            }else
            {
                return 0;
            }

        }
        int addStatus(int key_,VTypeN value_)
        {
            if(isNull(key_))
            {
                statusList.Insert(vNum++,new VStatus);
                statusList[vNum-1]->value=value_;
                statusList[vNum-1]->key=key_;
                return 1;
            }
            return 0;
        }
        int addArc(int key_start,int key_end,VTypeE value_)
        {
            if(isNull(key_start)||isNull(key_end))
                return 0;
            VArc * _arc = new VArc;
            _arc->start=(*this)[key_start];
            _arc->end=(*this)[key_end];
            _arc->value=value_;
            _arc->start->outArc.Push(_arc);
            _arc->end->inArc.Push(_arc);
            arcList.Push(_arc);
            ++eNum;
            return 1;
        }
        int delStatus(int key_)
        {
            statusList.p=statusList.head->next;
            for(int i=0;i!=vNum;i++)
            {
                if(statusList.p->elem->key==key_)
                {



                    for(int j=0;j!=arcList.size;j++)
                    {

                        VArc* _arc=arcList[j];

                        if(_arc->end==statusList.p->elem)
                        {
                            _arc->end->delArc(statusList.p->elem);
                            arcList.Del(j);
                            --eNum;

                            --j;

                        }else if(statusList.p->elem==_arc->start)
                        {
                            _arc->start->delArc(statusList.p->elem);
                            arcList.Del(j);
                            --eNum;
                            --j;

                        }


                    }

                    statusList.Del(i);
                    --vNum;

                    return 1;
                }
                statusList.p=statusList.p->next;
            }
            return 0;
        }
        int isNull(int key_)
        {
            statusList.p=statusList.head->next;
            for(int i=0;i!=vNum;i++)
            {
                if(statusList.p->elem->key==key_)
                {
                    return 0;
                }
                statusList.p=statusList.p->next;
            }
            return 1;
        }
        int emptyArcs()
        {
            for(int i=0;i!=eNum;i++)
            {

                delete arcList[0];
                arcList.Del(0);
            }
            return 1;
        }
        int emptyStatus()
        {

            for(int i=0;i!=vNum;i++)
            {
                delete statusList[0];
                statusList.Del(0);
            }
            return 1;
        }
        VStatus* operator [](int key_)
        {
            statusList.p=statusList.head->next;
            for(int i=0;i!=vNum;i++)
            {
                if(statusList.p->elem->key==key_)
                {
                    return statusList[i];
                }
                statusList.p=statusList.p->next;
            }
            return 0;
        }
        int travelDFS(VStatus * pos_,VTypeN * value_list,VStatus * adr_list[],int& len)
        {
            if(len==0)
            {
                if(vNum>=1)
                {
                    value_list[0]=statusList[0]->value;
                    ++len;
                    adr_list[0]=statusList[0];
                    for(int j=0;j!=statusList[0]->outArc.size;j++)
                        travelDFS(statusList[0]->outArc[j]->end,value_list,adr_list,len);
                }
                return 1;
            }
            for(int i=0;i!=len;i++)
                if(pos_==adr_list[i])
                    return 1;

            adr_list[len]=pos_;
            value_list[len]=pos_->value;
            ++len;
            for(int i=0;i!=pos_->outArc.size;i++)
                travelDFS(pos_->outArc[i]->end,value_list,adr_list,len);

            return 1;

        }
        int travelSubBFS(VStatus * pos_,VTypeN * value_list,VStatus * adr_list[],int& len)
        {

            for(int i=0;i!=len;i++)
                if(pos_==adr_list[i])
                    return 1;

            adr_list[len]=pos_;
            value_list[len]=pos_->value;
            ++len;

            return 1;

        }
        int travelBFS(VStatus * pos_,VTypeN * value_list,VStatus * adr_list[],int& len)
        {

            value_list[0]=statusList[0]->value;
            ++len;
            adr_list[0]=statusList[0];
            for(int j=0;j!=statusList[0]->outArc.size;j++)
                travelSubBFS(statusList[0]->outArc[j]->end,value_list,adr_list,len);

            int last_len=1,len_buf;
            for(;;)
            {
                len_buf=len;
                for(int i=last_len;i!=len;i++)
                    for(int j=0;j!=adr_list[i]->outArc.size;j++)
                        travelSubBFS(adr_list[i]->outArc[j]->end,value_list,adr_list,len);
                if(len==vNum)
                    return 1;
                last_len=len_buf;

            }
        }
    };


};





#endif

    VDiGraph<int,char> a(20,0,1);
    a.setArc(0,1,'a');
    a.setArc(0,2,'c');
    a.setArc(1,3,'b');
    a.setArc(2,3,'d');
    a.setArc(3,4,'e');
    while(1){
    char get;
    int i=0,j=0;
    for(;i!=3;i++){
       cin>>get;
       if((j=a.isGoBy(j,get))==-1)break;
    }
    if(i==3) cout<<"your input matchs my dfa!\n";
    }

    using VGAdt::VDiGraphEx;

    VDiGraphEx<char,char>  a;

    a.addStatus(1,'h');
    a.addStatus(2,'e');
    a.addStatus(3,'l');
    a.addStatus(4,'l');
    a.addStatus(5,'o');
    a.addStatus(6,'i');
    a.addStatus(7,'j');
    a.addStatus(8,'8');
    a.addStatus(9,'9');
    a.addStatus(10,'a');
    a.addStatus(11,'b');
    
    a.addArc(1,2,'1');
    a.addArc(2,3,'2');
    a.addArc(3,4,'3');
    a.addArc(4,5,'4');
    a.addArc(1,3,'5');
    a.addArc(1,5,'6');
    a.addArc(1,6,'7');
    a.addArc(2,3,'8');
    a.addArc(6,7,'8');
    a.addArc(6,8,'8');
    a.addArc(6,9,'8');
    a.addArc(8,10,'8');
    a.addArc(8,11,'8');
    int len=0;
    VDiGraphEx<char,char>::VStatus * adr_list[100];
char value_list[100]={0};
    a.travelBFS(0,value_list,adr_list,len);
    cout<<value_list<<":"<<len<<endl;