邻接表的深度优先遍历与广度优先遍历

接上篇。

此篇我们将介绍邻接表的思想及两种遍历的代码。

首先明确邻接表的存储方式：

邻接表中存在两种结构：顶点表节点和边表节点。

顶点表节点是存储当前节点，其后的一串边表节点是此点的邻接点。

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>

using namespace std;

const int MaxSize=100;
const int VERTEXNUM=20;

template<class T>
struct ArcNode
{
    int adjvex;
    struct ArcNode<T> *next;
};

template<class T>
struct VertexNode
{
    char ver;
    struct ArcNode<T> *firstedge;
};

此后的遍历仍需用到队列，故在此我们需要再写一个队列

typedef struct{
    int *Qbase;
    int front,rear;
}SqQueue;

void InitQueue(SqQueue &Q){
    Q.Qbase = (int *)malloc(sizeof(int) *VERTEXNUM);

    if(!Q.Qbase)
        return ;

    Q.rear = Q.front = -1;
}

void EnQueue(SqQueue &Q, int i){
    Q.Qbase[Q.rear ++] = i;
}

void DeQueue(SqQueue &Q, int &i){
    i = Q.Qbase[Q.front ++];
}

int QueueEmpty(SqQueue Q){
    if(Q.front == Q.rear)
        return 1;
    return 0;
}

接下来开始写邻接表类：

template<class T>
class ALGraph
{
public:
    ALGraph(T a[],int n,int e);
    ~ALGraph(){}      //默认析构
    void DFSTraverse();
    void Deep(int v[],int a);
    void BFSTraverse(int a);
private:
    VertexNode<T> adjlist[MaxSize];
    int vertexnum,arcnum;
    int visited[MaxSize];
};

在构造函数中，我们将图以邻接表的形式存储起来：

template<class T>
ALGraph<T>::ALGraph(T a[],int e,int n)
{
    int i,j,k;
    vertexnum=n;
    arcnum=e;
    for(i=0;i<arcnum;i++)
    {
        adjlist[i].ver=a[i];
        adjlist[i].firstedge=NULL;
    }
    for(k=0;k<vertexnum;k++)
    {
        cout<<"输入第"<<k+1<<"条边："<<endl;
        cin>>i>>j;
        struct ArcNode<T> *s=new struct ArcNode<T>;
        s->adjvex=j;
        s->next=adjlist[i].firstedge;
        adjlist[i].firstedge=s;
    }
}

邻接表与邻接矩阵的深度优先遍历写法类似，也是将所有点逐一遍历，代码如下：

template<class T>
void  ALGraph<T>::DFSTraverse()
{
    int i;
    for(i=0;i<arcnum;i++)
    {
        visited[i]=0;
    }
    std::cout<<"深度优先遍历:"<<std::endl;
    Deep(visited,0);
}
template<class T>
void   ALGraph<T>::Deep(int v[],int a)
{
    int j;
    struct ArcNode<T> *p=adjlist[a].firstedge;
    cout<<adjlist[a].ver<<endl;
    visited[a]=1;
    while(p!=NULL)
    {
        j=p->adjvex;
        if(visited[j]==0)   Deep(visited,j);
        p=p->next;
    }
}

广度优先遍历：

   1. 初始化一个队列，初始化visited。

   2. 将第一个点输出并入栈，将此点visited赋为1.定义一个顶点表节点类型指针p，将其赋为当前节点。

   3. 当队列不为空时弹出栈顶元素并查找p->next且visited为0的点，找到后，输出，赋值visited，入栈。p指向下一个相关节点

   4. 循环3

template<class T>
void ALGraph<T>::BFSTraverse(int a)
{
    SqQueue Q;
    int j;
    for(int i=0;i<arcnum;i++)
    {
        visited[i]=0;
    }
    std::cout<<"广度优先遍历:"<<std::endl;
    cout<<adjlist[a].ver<<endl;
    visited[a]=1;
    InitQueue(Q);
    EnQueue(Q,a);
    struct ArcNode<T> *p=adjlist[a].firstedge;
    while(!QueueEmpty(Q))
    {
        DeQueue(Q,a);
        p=adjlist[a].firstedge;
        while(p!=NULL)
        {
            j=p->adjvex;
            //cout<<j<<"    "<<"Sign!";
            if(visited[j]==0)
            {
                cout<<adjlist[j].ver<<endl;
                visited[j]=1;
                EnQueue(Q,j);
            }
            p=p->next;
        }
    }
}

主函数：

int main()
{
    int e,n;
    cout<<"输入点的个数：";
    cin>>e;
    cout<<"输入边的个数：";
    cin>>n;
    char  s[e];
    for(int i=0;i<e;i++)
    {
        cout<<"第"<<i+1<<"个点：";
        cin>>s[i];
    }
    ALGraph<char> a(s,e,n);
    a.DFSTraverse();
    a.BFSTraverse(0);
    return 0;
}

原创。未经允许请勿转载