6)图[1]之邻接矩阵存储[深度遍历和广度遍历]

#include "iostream"
#include "queue"
using namespace std;

const int MaxNumVertex  = 100; //最大顶点数
typedef int elementtype;       //elementtype 为int 型
class graph{
public:
    graph();
    ~graph();
    elementtype insertvertex(elementtype v); //在图中增加一个顶点
    elementtype deletevertex(elementtype v); //在图中删除一个顶点
    elementtype insertedge(elementtype v,elementtype u);//在图中增加一条从v顶点到u顶点的弧
    elementtype deleteedge(elementtype v,elementtype u);//]在图中删除一条从v顶点到u顶点的弧
    elementtype dfs(elementtype v);//从v顶点出发进行深度优先遍历
    elementtype bfs(elementtype v);//从v顶点出发进行广度优先遍历
    elementtype travel_dfs();//深度优先遍历图
    elementtype travel_bfs();//广度优先遍历图
    elementtype locatevertex(elementtype v);//求顶点v在图g中的位序
    elementtype firstadj(elementtype v);//求图g中顶点v的第一个邻接点
    elementtype nextadj(elementtype v,elementtype m);//求图中顶点v的m邻接点之后的邻接点
    elementtype degree(elementtype v);//求图中顶点v的度数
private:
    elementtype vertex[MaxNumVertex];//顶点表
    elementtype edge[MaxNumVertex][MaxNumVertex];//图中弧的类型
    int  CurrentVertex;//当前顶点数
    bool visited[MaxNumVertex];//顶点是否被访问
};

/*
*初始化
*/
graph::graph()
{
    CurrentVertex = 0; 
    int i,j;
    for (i=MaxNumVertex-1;i>=1;i--)
    {
        for (j=MaxNumVertex-1;j>=1;j--)
        {
            edge[i][j] = 0;

        }
    }
    for (i=MaxNumVertex-1;i>=1;i--)
    {
        visited[i] = false;
    }
}


/*
*在图中增加一个顶点
*/
elementtype graph::insertvertex(elementtype v)
{
    //判断这个顶点是否已经存在
    int i;
    bool flags = true;
    for(i=1; i<=CurrentVertex; i++)
    {
        if(vertex[i]==v)
        {
            flags = false;
            break;
        }
    }
    
    if(flags)
    {
        CurrentVertex++;
        vertex[CurrentVertex] = v;
    }else{
        cout<<v<<"顶点已经存在!"<<endl;
    }
    return 0;
}

/*
*在图中删除一个顶点
*/
elementtype graph::deletevertex(elementtype v)
{
    int i,j;
    bool flags = true;
    for(i=1; i<=CurrentVertex; i++)
    {
        if(vertex[i]==v)
        {
            flags = false;
            j=i;
            while(j<CurrentVertex)
            {
                vertex[j] = vertex[j+1];
                j++;
            }
            
            CurrentVertex--;
        }

    }
    if(flags) cout<<v<<"顶点不存在!";
    return 0;
}

/*
*在图中增加一条从v顶点到u顶点的弧
*/
elementtype graph::insertedge(elementtype v,elementtype u)
{
    if(edge[v][u]!=0)
    {
        cout<<v<<"->"<<u<<"这条弧弧已经存在!"<<endl;
    }else{
        edge[v][u] = 1;
    }
    return 0;
}

/*
*在图中删除一条从v顶点到u顶点的额弧
*/
elementtype graph::deleteedge(elementtype v,elementtype u)
{
    if(edge[v][u]!=0)
    {
        edge[v][u] = 0;
    }else {
        cout<<v<<"->"<<u<<"这条弧不存在!"<<endl;
    }
    return 0;
}

/*
*顶点v在图中的位序()???
*/
elementtype graph::locatevertex(elementtype v)
{
    int i,locate=0;
    for(i=1;i<=CurrentVertex; i++)
    {
        if(vertex[i]==v)
        {
            locate = i;
            break;
        }
    }
    return locate;
}

/*
*求图中顶点v的第一个邻接点
*/
elementtype graph::firstadj(elementtype v)
{
    int u,i;
    bool flags = true;//用于判断是否存在邻接点
    for(i=1;i<=CurrentVertex;i++)
    {
        if(edge[v][i]!=0){
            u = i;
            flags = false;
            break;
        }
    }
    if(flags) u = 0;//邻接点不存在
    return u;
}

/*
*求图中顶点v的m邻接点以后的邻接点
*/
elementtype graph::nextadj(elementtype v,elementtype m)
{
    int i,u;
    bool flags = true;
    for(i=m+1;i<=CurrentVertex;i++)
    {
        if(edge[v][i]!=0)
        {
            u = i;
            flags = false;
            break;
        }
    }
    if(flags) u = 0;//邻接点不存在
    return u;
}

/*
*求图中顶点v的度数
*/
elementtype graph::degree(elementtype v)
{
    int i,num = 0;
    for (i=MaxNumVertex-1;i>=1;i--)
    {
        if(edge[v][i]!=0 || edge[i][v]!=0)num++;
    }
    return num;
}
/*
*从v顶点出发进行深度优先遍历
*/
elementtype graph::dfs(elementtype v)
{
    int w;
    cout<<v<<"->";
    visited[v] = true;//访问顶点v,并设置其访问标志
    w = firstadj(v);//求出v的第一个邻接点
    while(w!=0)
    {
        if(visited[w]==false)//顶点w还没有被访问
        {
            dfs(w);
        }
        w = nextadj(v,w);
    }
    return 0;
}

/*
*深度遍历整个图;保证访问到所有结点
*/
elementtype graph::travel_dfs()
{
    int i;
    for(i=1;i<=CurrentVertex;i++)visited[i] = false;
    for(i=1;i<=CurrentVertex;i++)
    {
        if(visited[i]==false) dfs(i);
    }
    return 0;
}

/*
*广度有限遍历
*/
elementtype graph::bfs(elementtype v0)
{
    int w,x,v;
    queue<elementtype>q;
    visited[v0] = true;
    cout<<v0<<"->";
    q.push(v0);
    while(!q.empty())
    {
        x=q.front();
        v=x;
        q.pop();
        w=firstadj(v);
        while(w!=0)
        {
            if(!visited[w])
            {
                visited[w] = true;
                cout<<w<<"->";
                q.push(w);
            }
            w = nextadj(v,w);
        }
    }
    return 0;
}

/*
*广度优先遍历
*/
elementtype graph::travel_bfs()
{
    int i;
    for(i=1;i<=CurrentVertex;i++)visited[i] = false;
    for(i=1;i<=CurrentVertex;i++)
    {
        if(visited[i]==false) bfs(i);
    }
    return 0;
}
graph::~graph()
{
}
int main()
{
    graph g;
    int i,numv,v,u,w;
    cout<<"请输入顶点数:";
    cin>>numv;
    cout<<"请依次输入顶点:";
    for(i=1;i<=numv;i++)
    {
        cin>>v;
        g.insertvertex(v);
    }

    cout<<"请输入弧的数目:";
    cin>>numv;
    
    for(i=1;i<=numv;i++)
    {
        cout<<"u->w:";
        cin>>u>>w;
        g.insertedge(u,w);
    }

    cout<<"深度遍历结果dfs:";
    g.travel_dfs();
    cout<<endl;

    cout<<"广度遍历结果bfs:";
    g.travel_bfs();
    cout<<endl;
    return 0;
}