c++数据结构--构造无向图（算法6.1），深度和广度遍历

实验内容：

实现教材算法6.2利用邻接矩阵构造无向图的算法，提供从邻接矩阵获得邻接表的功能，在此基础上进行深度优先遍历和广度优先遍历。

实验步骤：

（1）按照实验要求编写代码，构造无向图。
创建所示无向图
屏幕输出邻接矩阵
0 1 0 0 0 1
1 0 1 1 0 0
0 1 0 1 1 0
0 1 1 0 1 0
0 0 1 1 0 1
1 0 0 0 1 0

深度优先遍历

屏幕输出： 1 2 3 4 5 6

广度优先遍历

屏幕输出：1 2 6 3 4 5
（2）输入验收用例，验证其输出结果。

#include <iostream>
#ifndef DATA_STRUCTURE_STATUS_H
#include <stdio.h>
//状态码
#define TRUE              1
#define FALSE            0
#define OK                  1
#define ERROR           0
#endif
#ifndef OVERFLOW
#define OVERFLOW    -2
#endif // OVERFLOW
#ifndef NULL
#define NULL((void*) 0)
#endif // NULL
typedef int Status;
#define MaxInt 32767  //表示极大值
#define MVNum 100     //表示最大顶点数
using namespace std;

//图的邻接矩阵存储表示：
typedef int VerTexType;//顶点字符类型
typedef int ArcType;    //边的权值
typedef struct
{
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum,arcnum;//图的当前点数和边数
}AMGraph;

typedef string OtherInfo;

//图的邻接表存储表示：
typedef struct ArcNode//边结构
{
    int adjvex;
    struct ArcNode *nextarc;
    OtherInfo info;//其他信息
}ArcNode;

typedef struct VNode//顶点结构
{
    VerTexType data;//存储顶点信息
    ArcNode *firstarc;
}VNode,AdjList[MVNum];

typedef struct
{
    AdjList vertics;//邻接表
    int vexnum,arcnum;//顶点数和弧数
    int kind;
}ALGraph;

bool visited[MVNum];

int LocateVex(AMGraph G,VerTexType u)
{//定位每个顶点的位置
    int i;
    for(i=0;i<G.vexnum;i++)
    {
        if(u==G.vexs[i])
            return i;
    }
    return -1;
}

//构建无向网：
Status CreateUDN(AMGraph &G)
{
    cout<<"请输入图的顶点数目，边数目:";
    cin>>G.vexnum>>G.arcnum;//输入当前的顶点数目和边的数目
    for(int i=0;i<G.vexnum;i++)
    {
        cout<<"请输入第"<<i<<"个顶点：";
        cin>>G.vexs[i];//初始化点的信息
    }
    for(int i=0;i<G.vexnum;i++)
    {
        for(int j=0;j<G.vexnum;j++)
        {
            G.arcs[i][j]=MaxInt;//初始化邻接矩阵
        }
    }
    int i,j;
    int v1,v2,w;
    for(int k=0;k<G.arcnum;k++)
    {
        cout<<"边:";
        cin>>v1>>v2>>w;
        i=LocateVex(G,v1);
        j=LocateVex(G,v2);
        G.arcs[i][j]=w;
        G.arcs[j][i]=G.arcs[i][j];
    }
    return OK;
}

//邻接矩阵转换成邻接表
void change(AMGraph G,ALGraph &p)
{
    int i,j;
    ArcNode *q;
    for(i=0;i<G.vexnum;i++)
    {
        p.vertics[i].firstarc=NULL;
    }
    for(i=0;i<G.vexnum;i++)
    {
        for(j=0;j<G.vexnum;j++)
        {
            if(G.arcs[i][j])
            {
                q=new ArcNode;
                q->adjvex=j;
                q->nextarc=p.vertics[j].firstarc;
                p.vertics[j].firstarc=q;
            }
        }
    }
}

//深度优先遍历：
void DFS_AM(AMGraph G,int v)
{

    cout<<v+1;
    visited[v]=true;
    for(int w=0;w<G.vexnum;w++)//依次检查邻接矩阵所在的行
    {
        if(G.arcs[v][w]!=0&&(!visited[w]))
            DFS_AM(G,w);//w是v的邻接点，如果w未访问，则递归调用DFS
    }
}

//广度优先遍历：
void BFS(AMGraph G,int v)
{
    for(int i=0;i<G.vexnum;i++)
    {
        visited[i]=false;
    }
    int Q[MaxInt];
    cout<<G.vexs[v];
    visited[v]=true;
    int w,u;
    int front=-1,rear=-1;
    Q[++rear]=v;
    while(front!=rear)
    {
        u=Q[++front];
        for(w=0;w<G.vexnum;w++)
        {
            if((!visited[w])&&(G.arcs[u][w]==1))
            {
                cout<<G.vexs[w];
                visited[w]=true;
                Q[++rear]=w;
            }
        }
    }
}

int main()
{
    cout<<"无向网图"<<endl;
    cout<<"1.构建网图"<<endl;
    cout<<"2.输出邻接矩阵"<<endl;
    cout<<"3.深度优先遍历"<<endl;
    cout<<"4.广度优先遍历"<<endl;
    int n,a;
    AMGraph G;
    ALGraph P;
    while(1)
    {
        cout<<"请输入你的选择："<<endl;
        cin>>n;
        if(n==1)
        {
            CreateUDN(G);
            cout<<"操作完成！"<<endl;
        }
        else if(n==2)
        {
            cout<<"邻接矩阵为：";
            for(int i=0;i<G.vexnum;i++)
            {
                cout<<endl;
                for(int j=0;j<G.vexnum;j++)
                {
                    if(G.arcs[i][j]==MaxInt)
                    {
                        cout<<"0 ";
                    }
                    else
                    {
                        cout<<G.arcs[i][j]<<" ";
                    }

                }
            }
            cout<<"\n操作完成"<<endl;
        }
        else if(n==3)
        {
            cout<<"深度优先遍历为：";
            DFS_AM(G,0);
            cout<<"\n操作完成！"<<endl;
        }
        else if(n==4)
        {
            cout<<"广度优先遍历为：";
            BFS(G,0);
            cout<<"\n操作完成"<<endl;
        }
        else if(n==5)
        {
            cout<<"本次操作结束"<<endl;
            break;
        }
    }
    return 0;
}