邻接矩阵的深度优先遍历与广度优先遍历——代码详解

由于比较仓促所以直接以代码的形式来讲解，所用为c++中的模板类。

· 首先是此代码中用到的头文件：

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

· 初始矩阵大小：

const int MaxSize=100;

· 因为邻接矩阵的广度优先遍历会用到队列，所以我们先写一个队列：

（别忘记定义队列大小）

const int VERTEXNUM=20;
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  MGraph
{
public:
    MGraph(T a[],int n,int e);
    ~MGraph(){}
    void DFSTraverse();
    void BFSTraverse(int v);
    void DeepTra(int v[],int n);
private:
    T   vertex[MaxSize];             //节点数组
    int  arc[MaxSize][MaxSize];      //矩阵
    int vertexNum,arcNum;            //节点数与边数
    int visited[MaxSize];            //访问记录
};

· 现在来写邻接矩阵的构造函数，先初始化一个为0的矩阵。矩阵的行列代表图中一边的起点与终点。若此边存在，此处值赋为1.

template<class T>
MGraph<T>::MGraph(T a[],int n,int e)
{
    int i,j;
    vertexNum=n;
    arcNum=e;
    for(i=0;i<vertexNum;i++)
    {
        vertex[i]=a[i];
    }

    for(i=0;i<vertexNum;i++)
        for(j=0;j<vertexNum;j++)
    {
        arc[i][j]=0;
    }

    for(int k=0;k<arcNum;k++)
    {
        std::cout<<"输入第"<<k+1<<"条边："<<std::endl;
        std::cin>>i>>j;
        arc[i][j]=1;
        arc[j][i]=1;
    }
}

· 接下来进行深度优先遍历。当每遍历过一个点去遍历下一个点时，为了确认下一个点是否被遍历过，我们需要借助visited数组，当i未被遍历过时，visited[i]=0;当i已经被遍历过时，visited[i]=1.

由于遍历采用的是递归遍历，为了visited数组传参，我们用一个函数对visited进行初始化：

template<class T>
void  MGraph<T>::DFSTraverse()
{
    int i;
    for(i=0;i<vertexNum;i++)
    {
        visited[i]=0;
    }
    std::cout<<"深度优先遍历:"<<std::endl;
    for(i=0;i<vertexNum;i++)
    {
        if(visited[i]==0)
            DeepTra(visited,0);
    }
}

template<class T>
void MGraph<T>::DeepTra(int v[],int n)
{
    int i;
    visited[n]=1;
    std::cout<<vertex[n];
    for(i=0;i<vertexNum;i++)
    {
        if(arc[n][i]!=0&&visited[i]==0)
        {
            DeepTra(visited,i);
        }
    }
}

·  广度优先遍历算法：

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

   2. 将第一个点输出并入栈，将此点visited赋为1.

   3. 当队列不为空时弹出栈顶元素并查找与元素相关且visited为0的点，找到后，输出，赋值visited，入栈。

   4. 循环3

template<class T>
void MGraph<T>::BFSTraverse(int v)
{
    SqQueue Q;
    Q.front=Q.rear=-1;
    int i;
    for(i=0;i<vertexNum;i++)
    {
        visited[i]=0;
    }
    std::cout<<std::endl;
    std::cout<<"广度优先遍历："<<std::endl;
    std::cout<<vertex[v];
    visited[v]=1;
    InitQueue(Q);
    EnQueue(Q,v);
    while(!QueueEmpty(Q))
    {
        DeQueue(Q,v);
        for(int i=0;i<vertexNum;i++)
            if(arc[v][i]==1&&visited[i]==0)
        {
            std::cout<<vertex[i];
            visited[i]=1;
            EnQueue(Q,i);
        }
    }
}

· 主函数：

int main()
{

    int e,n;
    std::cout<<"点的个数："<<"  ";
    std::cin>>e;

    std::cout<<"边的个数："<<"  ";
    std::cin>>n;

    char  s[e];
    for(int i=0;i<e;i++)
    {
        std::cout<<"输入第"<<i+1<<"个点：";
        std::cin>>s[i];
    }
    MGraph<char> m(s,e,n);
    m.DFSTraverse();
    m.BFSTraverse(0);
    return 0;
}

此为原创，未经允许请勿转载