chenglong7997

就拿这个图做实验了

?

#include<iostream>

#include<vector>

#include<queue>

 

using namespace std;

 

struct ArcNode{             //弧结点结构

    int adjvex;             //邻接顶点

    ArcNode *nextarc;       //下一条弧

};

 

template <class T>

struct VertextNode{         //表头结点结构

    T Vertext;          //顶点

    ArcNode* firstArc;      //第一条弧

};

 

const int MAXSIZE=10;

template<class T>

class ALGraph{

public:

    ALGraph(T a[],int n,int e);

    ~ALGraph();

    void DFS(int v);

    void BFS(int v);

     

    vector<int> visited;

private:

    VertextNode<T> adjlist[MAXSIZE];      //顶点

    int vNum,arcNum;                    //顶点和弧的数目

     

};

 

template <class T>

ALGraph<T>::ALGraph(T a[],int n,int e){

    vNum=n;

    arcNum=e;

    visited.assign(vNum,0);

    for(int k=0;k<n;k++){                //k是局部变量

        adjlist[k].Vertext=a[k];        //初始化顶点

        adjlist[k].firstArc=NULL;       //初始化弧

    }

    cout<<"Input the vertexts of each arc."<<endl;

    int i,j;

    for(int k=0;k<e;k++){

        cin>>i>>j;

        ArcNode *arc=new ArcNode;

        arc->adjvex=j;

        arc->nextarc=adjlist[i].firstArc;        //头插法建立链表

        adjlist[i].firstArc=arc;

    }

}

/*可发看到建立邻接表的时间复杂度为O(n+e)*/

?

<br>

?

template <class T>

void ALGraph<T>::DFS(int v){

 

    cout<<adjlist[v].Vertext<<endl;                 

    visited[v]=1;

    ArcNode *p=adjlist[v].firstArc;

    while(p){

        int j=p->adjvex;

        if(visited[j]==0)

            DFS(j);

        p=p->nextarc;

    }

}

 

template <class T>

void ALGraph<T>::BFS(int v){

    queue<int> q;             //一个空队列

     

    cout<<adjlist[v].Vertext<<endl;

    visited[v]=1;

    q.push(v);          //v入队

    while(!q.empty()){

        int h=q.front();        //获取队首元素

        q.pop();            //队首元素出队

        ArcNode *p=adjlist[h].firstArc;

        while(p){

            int j=p->adjvex;

            if(visited[j]==0){

                cout<<adjlist[j].Vertext<<endl;

                visited[j]=1;

                q.push(j);      //元素入队

            }

            p=p->nextarc;

        }

    }

}

 

int main(){

    int arr[6]={0,1,2,3,4,5};

    ALGraph<int> *g=new ALGraph<int>(arr,6,6);

    cout<<"<<----------DFS-------------->>"<<endl;

    g->DFS(0);

    g->visited.assign(6,0);

    cout<<"<<----------BFS-------------->>"<<endl;

    g->BFS(0);

    return 0;

}