基于邻接表的图的遍历

（1）建立一个邻接表存储的图；（2）输出图的邻接表；（3）输出各顶点的度（若是有向图，输出各顶点的入度、出度和度）；（4）对图进行深度优先、广度优先遍历。
【测试数据】
（1）

输入图的种类：2
输入图的顶点数和边数：5 5
输入各条边：0 1 0 3 1 2 2 3 2 4

（2）

输入图的种类：0
输入图的顶点数和边数：3 4
输入各条边：0 1 0 2 1 0 1 2

#include <iostream>
#include <malloc.h>
#include <queue>
using namespace std;

#define VertexType int
#define MaxVertexNum 20 //最大顶点数

queue<int>Q;                    //辅助队列

enum GraphType {
   DG, UDG};       //DG表示有向图，UDG表示无向图

typedef struct ArcNode          //边结点
{
   
    int adjvex;                 //邻接点的下标
    struct ArcNode *nextarc;    //后继链指针
} ArcNode;

typedef struct VNode            //顶点结点
{
   
    VertexType data;            //顶点数据
    ArcNode *firstarc;          //边链头指针
} VNode, AdjList[MaxVertexNum];

typedef struct
{
   
    AdjList vertices;           //邻接表
    int vexnum,arcnum;          //顶点数和边数
    int kind;             //图种类标志
} ALGraph;

//建立有向图
void CreateDGGraph(ALGraph &G)
{
   
    // cout<<0<<endl;
    int m, n;                   //边<Vm,Vn>的下标
    ArcNode *vm, *vn;           //构成边<Vm,Vn>的两个顶点
    cout << "请输入顶点数和边数：";
    cin >> G.vexnum >> G.arcnum;

    //获取顶点信息
    for(int i=0; i<G.vexnum; i++)
    {
   
        G.vertices[i].data=i;
        G.vertices[i].firstarc=NULL;
    }

    //建立邻接表，采用头插法
    for(int i=0; i<G.arcnum; i++)
    {
   
        cout << "请输入<Vi,Vj>的下标：";
        cin >> m >> n;
        vm=(ArcNode*)malloc(sizeof(ArcNode));
        vm->adjvex=n;

        vm->nextarc=NULL;
        if(G.vertices[m].firstarc==NULL)
        {
   
            vn=G.vertices[m].firstarc=vm;
        }
        else
        {
   
            vn=vn->nextarc=vm;
        }
    }
}

//建立无向图
void CreateUDGGraph(ALGraph &G)
{
   
    int m, n;                  //边<Vm,Vn>的下标
    ArcNode *pe;

    cout << "请输入顶点数和边数：";
    cin >> G.vexnum >> G.arcnum;

    //获取顶点信息
    for(int i=0; i<G.vexnum; i++)
    {
   
        G.vertices[i].data=i;
        G.vertices[i].firstarc=NULL;
    }

    //建立邻接表，采用头插法
    for(int i=0; i<G.arcnum; i++)
    {
   
        cout << "请输入<Vi,Vj>的下标：";
        cin >> m >> n;
        pe=(ArcNode*)malloc(sizeof(ArcNode));
        pe->adjvex=n;

        pe->nextarc=G.vertices[m].firstarc;
        G.vertices[m].firstarc=pe;

        pe=(ArcNode*)malloc(sizeof(ArcNode));
        pe->adjvex=m;
        pe->nextarc=G.vertices[n].firstarc;
        G.vertices[n].firstarc=pe;
    }
}

void PrintALGraph(ALGraph &G)
{
   
    ArcNode *p;
    for (int i=0; i<G.vexnum; i++)
    {
   
        cout << "顶点" << G.vertices[i].data <<" : ";
        for (p=G.vertices[i].firstarc; p!=NULL; p=p->nextarc)
            cout << p->adjvex <<" ";
        if (p==NULL)
            cout << endl;
    }
}
void PrintDU(ALGraph &G)
{
   
    ArcNode *p;
    if(G.kind==2)
        for(int i=0; i<G.vexnum; i++)
        {
   
            cout<<"顶点："<<i;
            int cnt=0;
            cout<<" 度 ：";
            for(p=G.vertices[i].firstarc; p!=NULL; p=p->nextarc)
                cnt++;
            if(p==NULL)
                cout<<cnt<<endl;
        }
    else
    {
   
        int cnt1[G.vexnum]= {
   0},cnt2[G.vexnum]= {
   0},cnt[G.vexnum]= {
   0};
        for(int i=0; i<G.vexnum; i++)
        {
   
            cout<<"顶点："<<i;

            cout<<" 出度 ：";
            for(p=G.vertices[i].firstarc; p!=NULL; p=p->nextarc)
                cnt1[i]++;
            if(p==NULL)
                cout<<cnt1[i];
            cout<<" 入度 ：";
            if(i!=G.vexnum-1)
            {
   

                ArcNode *pp;
                pp=G.vertices[i].firstarc;
                for(int j=0; j<G.vexnum; j++)
                {
   
                    for(p=G.vertices[j].firstarc; p!=NULL; p=p->nextarc)
                        if(p->adjvex==pp->adjvex)
                            cnt2[i]++;
                }
            }
            else
            {
   
                for(int j=0; j<G.vexnum-1; j++)
                    cnt2[i]+=cnt1[j]-cnt2[j];
            }
            cout<<cnt2[i];

            cnt[i]=cnt1[i]+cnt2[i];
            cout<<" 度 ："<<cnt[i]<<endl;
        }
    }
}

//求图中顶点v的第一个邻接点，若有则返回顶点下标。若v没有邻接点或图中不存在v，则返回-1
int FirstNeighbor(ALGraph G, int v)
{
   
    ArcNode *next=G.vertices[v].firstarc;
    if(next)
    {
   
        return next->adjvex;
    }
    return -1;
}

//返回除顶点v外的下一个顶点w
int NextNeighbor(ALGraph G, int v, int w)
{
   
    ArcNode *next=G.vertices[v].firstarc;
    while(next)
    {
   
        if(next->adjvex==w)break;
        next=next->nextarc;
    }
    if(next)
    {
   
        ArcNode *nextNode=next->nextarc;
        if(nextNode)
        {
   
            return nextNode->adjvex;
        }
    }
    return -1;
}

void visit(ALGraph G, int v)
{
   
    cout << G.vertices[v].data << " ";
}

bool visited[MaxVertexNum];         //访问标记数组

//从顶点v出发，采用递归，广度遍历图G
void BFS(ALGraph G, int v)
{
   
    visit(G, v);
    visited[v]=true;                //设已访问标记
    Q.push(v);                      //顶点v入队
    while(!Q.empty())
    {
   
        v=Q.front();
        Q.pop();
        for(int w=FirstNeighbor(G, v); w>=0; w=NextNeighbor(G, v, w))
        {
   
            //检查v所以邻接点
            if(!visited[w])         //w为v的尚未访问的邻接顶点
            {
   
                visit(G, w);
                visited[w]=true;    //设已访问标记
                Q.push(w);          //顶点w入队
            }
        }
    }
}

//从顶点出发，进行广度优先遍历
void BFSTraverse(ALGraph G)
{
   
    for(int i=0; i<G.vexnum; i++)
    {
   
        visited[i]=false;           //访问标记数组初始化
    }

    for(int i=0; i<G.vexnum; i++)   //从0号顶点开始遍历
    {
   
        if(!visited[i])
        {
   
            BFS(G, i);              //vi未访问过，从vi开始BFS
        }
    }
}

//从顶点v出发，采用递归，深度遍历图G
void DFS(ALGraph G, int v)
{
   
    visit(G, v);                    //访问v
    visited[v]=true;                //设已访问标记
    for(int w=FirstNeighbor(G, v); w>=0; w=NextNeighbor(G, v, w))
    {
   
        //w为v的尚未访问的邻接顶点
        if(!visited[w])
        {
   
            DFS(G, w);
        }
    }
}

//从顶点出发，进行深度优先遍历
void DFSTraverse(ALGraph G)
{
   
    for(int i=0; i<G.vexnum; i++)
    {
   
        visited[i]=false;           //访问标记数组初始化
    }
    for(int i=0; i<G.vexnum; i++)   //从0号顶点开始遍历
    {
   
        if(!visited[i])
        {
   
            DFS(G, i);              //vi未访问过，从vi开始DFS
        }
    }
}
int main()
{
   
    printf("****菜 单****\n");
    printf("0、有向图\n");
    printf("2、无向图\n\n");

    printf("输入图的种类:\n");
    int tmp;
    ALGraph G;
    cin>>G.kind;
    if(G.kind==0)
    {
   

        CreateDGGraph(G);      //建立有向图
    }
    else if(G.kind==2)
    {
   
        CreateUDGGraph(G);     //建立无向图
    }
    cout << "===========================" << endl;
    PrintALGraph(G);
    cout <<endl;
    PrintDU(G);
    cout <<endl;
    cout << "广度遍历：";
    BFSTraverse(G);

    cout << endl;
    cout << "深度遍历：";
    DFSTraverse(G);
    return 0;
}