论坛 › 数据结构与算法 › 图的深度遍历和广度遍历

Code_mzh 发表于 2018-2-20 20:18:44

图的深度遍历和广度遍历

#include <iostream>
using namespace std;
#define MAXSIZE 100

typedef int ElemType;
typedef char VertexType;
typedef struct MGraph{
    VertexType vertex;///顶点表
    ElemType arc;///邻接矩阵，可看作边表
    ElemType vertexNum, arcNum;///vertexNum是顶点数，arcNum是边数
};
intvisited;//标记数组
intvisited1;
void CreateMGraph(MGraph *G){
    int i ,j ,k;
    cout<<"输入边数和顶点数：";
    cin>>G->arcNum>>G->vertexNum;
    //输入顶点
    cout<<"输入顶点"<<endl;
    for(i = 0;i < G->vertexNum;i++)
    {
      cin>>G->vertex;
    }
    //初始化矩阵
    for(i = 0;i < G->vertexNum; i++)
    {
      for(j = 0; j <G->vertexNum; j++)
      {
            G->arc=0;
      }

    }
    ///输入由顶点构成的边
    cout<<"请输入与边关联的两个顶点的序号："<<endl;
    for(k = 0;k <G->arcNum;k++)
    {
      cin>>i>>j;
      G->arc=1;//有边则赋值为1
      G->arc=1;
    }
    cout<<"输出邻接矩阵:"<<endl;
    //输出矩阵
    for(i = 0;i < G->vertexNum; i++)
    {
      for(j = 0; j <G->vertexNum; j++)
      {
            cout<<G->arc<<"\t";
      }
      cout<<endl;
    }
}

/// 邻接矩阵的深度递归算法
void DFSTravese(MGraph *G,int v){
    int w;
   cout<<G->vertex<<"\t";
    visited=1;
   for(w = 0;w < G->vertexNum; w++)
      {
            if(G->arc == 1 && !visited )
            {
                DFSTravese(G,w);
            }
      }
}

///邻接矩阵的深度遍历操作
void DFSTravese(MGraph *G){
    int v;
    for(v= 0;v < G->vertexNum; v++)
    {
      visited = 0;
    }
    for(v =0;v <G->vertexNum; v++)
    {
            if(!visited)
            {
                DFSTravese(G,v);
            }
    }
}

///队列的操作
typedef struct Qnode{
    ElemType *base;
    int front;
    int rear;
};

///初始化队列
int InitQueue(Qnode *q){
    q->base=new ElemType;
    if(!q->base)
    {
      cout<<"开辟空间失败"<<endl;
    }
    q->front=q->rear=0;
}

///插入队列
int InsertQueue(Qnode *q,ElemType *e){
    if((q->rear+1)%MAXSIZE == q->front)
    {
      cout<<"队列已满，不能插入"<<endl;
      return 0;
    }
    q->base=*e;
    q->rear=(q->rear+1)%MAXSIZE;
}

///删除队列
void DeleteQueue(Qnode *q,ElemType *e){
    if((q->front)%MAXSIZE == q->rear)
    {
      cout<<"队列已空"<<endl;
    }
    *e=q->base;
    q->front=(q->front+1)%MAXSIZE;
}

///邻接矩阵的广度优先遍历
void BFSTravese(MGraph G,int v){
    Qnode q;
    int w;
    cout<<G.vertex<<"\t";///先将第一个结点输出
    visited1=1;
    InitQueue(&q);///初始化队列
    InsertQueue(&q,&v);///插入队列
    while(q.rear != q.front)///只要队列不为空就一直开始出队列
    {
      DeleteQueue(&q,&v);///删除刚才输出的队列
      for(w =0; w <G.vertexNum; w++)
      {
            if(G.arc == 1 && visited1 == 0)
            {
                cout<<G.vertex<<"\t";
                visited1=1;
                InsertQueue(&q,&w);
                //BFSTravese(G,e);
            }
      }

    }
}
int main() {
    MGraph G;
    CreateMGraph(&G);
    cout<<"输出遍历的顶点:"<<endl;
    DFSTravese(&G,0);
    cout<<endl;
    cout<<"输出遍历的顶点:"<<endl;
    BFSTravese(G,0);
    return 0;
}

Kitty喜欢小鱼干 发表于 2018-8-9 22:14:37

来关注一波{:5_109:}

查看完整版本: 图的深度遍历和广度遍历