성형 도면 의 깊이 와 넓이

비교적 간단 한 실현, 그림 은 인접 행렬 의 저장 방식 을 사용 하고 복제 구조 함수 와 과부하 연산 자 를 추가 하지 않 았 다.
#include 
#include
#include
using namespace std;
struct Node
{
    int data;
    Node *next;
    Node(){next=NULL;}
    Node(int item,Node *link=NULL)
    {
        data=item;
        next=link;
    }
};
class LinkQueue
{
protected:
    Node *front,*rear;
    int count;
public:
    LinkQueue(){rear=front=new Node();count=0;}
    virtual ~LinkQueue();
    int length()const{return count;}
    bool Empty()const{return count==0;}
    void Clear();
    void Traverse()const;
    bool OutQueue(int &e);
    bool GetHead(int &e)const;
    bool InQueue(const int &e);
    LinkQueue(const LinkQueue &copy);
    LinkQueue&operator=(const LinkQueue &copy);
};
LinkQueue::~LinkQueue()
{
    Clear();
}
void LinkQueue::Clear()
{
    int tmp;
    while(!Empty())
        OutQueue(tmp);
}
void LinkQueue::Traverse()const
{
    for(Node *tmp=front->next;tmp!=NULL;tmp=tmp->next)
        cout<data<<' ';
}
bool LinkQueue::OutQueue(int &e)
{
    if(!Empty())
    {
        Node *tmp=front->next;
        e=tmp->data;
        front->next=tmp->next;
        if(rear==tmp)
            rear=front;
        delete tmp;
        count--;
        return true;
    }
    else
        return false;
}
bool LinkQueue::GetHead(int &e)const
{
    if(!Empty())
    {
        Node *tmp=front->next;
        e=tmp->data;
        return true;
    }
    else
        return false;
}
bool LinkQueue::InQueue(const int &e)
{
    Node *tmp=new Node(e);
    rear->next=tmp;
    rear=tmp;
    count++;
    return true;
}
LinkQueue::LinkQueue(const LinkQueue&copy)
{
    rear=front=new Node();
    count=0;
    for(Node *tmp=copy.front->next;tmp!=NULL;tmp=tmp->next)
        InQueue(tmp->data);
}
LinkQueue&LinkQueue::operator=(const LinkQueue&copy)
{
    if(&copy!=this)
    {
        Clear();
        for(Node *tmp=copy.front->next;tmp!=NULL;tmp=tmp->next)
            InQueue(tmp->data);
    }
    return *this;
}
class AdjMatrixDirGraph
{
protected:
    int vexNum,edgeNum;                             //      
    int **Matrix;                                   //    
    int *elems;                                     //    
    mutable bool *tag;                              //         
    void DestroyHelp();                             //     
    void DFS(int v)const;                           //   v        
    void BFS(int v)const;                           //   v        
public:
    AdjMatrixDirGraph(int es[],int vertexNum=10);   //       es,     vertexNum,   0    
    AdjMatrixDirGraph(int vertexNum=10);            //       vertexNum   0    
    ~AdjMatrixDirGraph();                           //    
    void DFSTraverse()const;                        //          
    void BFSTraverse()const;                        //          
    bool GetElem(int v,int &e)const;                //      
    bool SetElem(int v,const int &e);               //       
    int GetVexNum()const{return vexNum;}            //      
    int GetEdgeNum()const{return edgeNum;}          //      
    int FirstAdjVex(int v)const;                    //    v        
    int NextAdjVex(int v1,int  v2)const;            //    v1    v2       
    void InsertEdge(int v1,int v2);                 //     v1 v2  
    void DeleteEdge(int v1,int v2);                  //     v1 v2  
    bool GetTag(int v)const;                        //    v   
    void SetTag(int v,bool val)const;               //  v1    val
    void Display()const;                            //      
};
void AdjMatrixDirGraph::DestroyHelp()
{
    delete[] elems;
    delete[] tag;
    for(int i=0;idelete []Matrix[i];
    delete []Matrix;
}
void AdjMatrixDirGraph::DFS(int v)const
{
    SetTag(v,true);
    int e;
    GetElem(v,e);
    cout<' ';
    for(int w=FirstAdjVex(v);w>=0;w=NextAdjVex(v,w))
        if(!GetTag(w))
            DFS(w);
}
void AdjMatrixDirGraph::DFSTraverse()const
{
    int v;
    for(v=0;vfalse);
    cout<<"    :";
    for(v=0;vif(!GetTag(v))
            DFS(v);
}
void AdjMatrixDirGraph::BFS(int v)const
{
    SetTag(v,true);
    int e;
    GetElem(v,e);
    cout<' ';
    LinkQueue q;
    q.InQueue(v);
    while(!q.Empty())
    {
        int u,w;
        q.OutQueue(u);
        for(w=FirstAdjVex(u);w>=0;w=NextAdjVex(u,w))
        {
            if(!GetTag(w))
            {
                SetTag(w,true);
                GetElem(w,e);
                cout<' ';
                q.InQueue(w);
            }
        }
    }
}
void AdjMatrixDirGraph::BFSTraverse()const
{
    int v;
    for(v=0;vfalse);
    cout<<"    :";
    for(v=0;vif(!GetTag(v))
            BFS(v);
}
AdjMatrixDirGraph::AdjMatrixDirGraph(int es[],int vetexNum)
{
    if(vetexNum<=0)
        throw runtime_error("         0");
    vexNum=vetexNum,edgeNum=0;
    Matrix=new int*[vexNum];
    elems=new int[vexNum];
    tag=new bool[vexNum];
    for(int i=0;inew int[vexNum];
    for (int u = 0; u < vexNum; u++)
        for (int v = 0; v < vexNum; v++)
            Matrix[u][v] = 0;
    for(int i=0;ifor(int i=0;ifalse;
}
AdjMatrixDirGraph::AdjMatrixDirGraph(int vetexNum)
{
    if(vetexNum<0)
        throw runtime_error("         0");
    vexNum=vetexNum,edgeNum=0;
    Matrix=new int*[vexNum];
    elems=new int[vexNum];
    tag=new bool[vexNum];
    for(int i=0;inew int[vexNum];
    for (int u = 0; u < vexNum; u++)
        for (int v = 0; v < vexNum; v++)
            Matrix[u][v] = 0;
    for(int i=0;ifalse;
}
AdjMatrixDirGraph::~AdjMatrixDirGraph()
{
    DestroyHelp();
}
bool AdjMatrixDirGraph::GetElem(int v,int &e)const
{
    if(v<0||v>=vexNum)
        return false;
    else
    {
        e=elems[v];
        return true;
    }
}
bool AdjMatrixDirGraph::SetElem(int v,const int &e)
{
    if(v<0||v>=vexNum)
        return false;
    else
    {
        elems[v]=e;
        return true;
    }
}
int AdjMatrixDirGraph::FirstAdjVex(int v)const
{
    int i=0;
    while(Matrix[v][i]==0&&iif(Matrix[v][i]==1)
        return i;
    return -1;
}
int AdjMatrixDirGraph::NextAdjVex(int v1,int v2)const
{
    while(Matrix[v1][++v2]==0&&v2if(Matrix[v1][v2]==1)
        return v2;
    return -1;
}
void AdjMatrixDirGraph::InsertEdge(int v1,int v2)
{
    if(v1<0||v1>=vexNum) throw runtime_error("v1   ");
    if(v2<0||v2>=vexNum) throw runtime_error("v2   !");
    if(v1==v2) throw runtime_error("v1    v2!");
    if(Matrix[v1][v2]==0&&Matrix[v2][v1]==0)
        edgeNum++;
    Matrix[v1][v2]=1;
    Matrix[v2][v1]=1;
}
void AdjMatrixDirGraph::DeleteEdge(int v1,int v2)
{
    if(v1<0||v1>=vexNum) throw runtime_error("v1   !");
    if(v2<0||v2>=vexNum) throw runtime_error("v2   !");
    if(v1==v2) throw runtime_error("v1    v2!");
    if(Matrix[v1][v2]==1&&Matrix[v2][v1]==1)
        edgeNum--;
    Matrix[v1][v2]=0;
    Matrix[v2][v1]=0;
}
bool AdjMatrixDirGraph::GetTag(int v)const
{
    if(v<0||v>=vexNum)
        throw runtime_error("v   ");
    else
        return tag[v];
}
void AdjMatrixDirGraph::SetTag(int v,bool val)const
{
    if(v<0||v>=vexNum)
        throw runtime_error("v   ");
    else
        tag[v]=val;
}
void AdjMatrixDirGraph::Display()const
{
    for(int i=0;ifor(int j=0;jcout<' ';
        cout<int main()
{
    int vetexNum,edgeNum,v1,v2;
    cout<<"       :";
    cin>>vetexNum;
    int es[vetexNum];
    for(int i=0;icout<<"        "<"     :";
        cin>>es[i];
    }
    AdjMatrixDirGraph g(es,vetexNum);
    cout<<"       :";
    cin>>edgeNum;
    for(int i=0;icout<<"         "<1<<"       (     ):";
        scanf("%d %d",&v1,&v2);
        g.InsertEdge(v1,v2);
    }
    g.Display();
    g.DFSTraverse();
    g.BFSTraverse();
    return 0;
}

좋은 웹페이지 즐겨찾기