欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的深度优先和广度优先

程序员文章站 2022-03-03 11:51:39
...
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MVNum 100
#define MAXQSIZE 100                        //最大队列长度
typedef int Vtype;           //顶点的数据类型 
typedef struct 
{
    Vtype vexs[MVNum];              //顶点表 
    int  arcs[MVNum][MVNum];        //邻接矩阵
    int  vexnum,arcnum;             //图的点数和边数  
}Graph;

//----队列的定义及操作--------
typedef struct{
    int *base;                          //初始化的动态分配存储空间
    int front;                              //头指针,若队列不空,指向队头元素
    int rear;                               //尾指针,若队列不空,指向队尾元素的下一个位置
}sqQueue;
void InitQueue(sqQueue &Q){
    //构造一个空队列Q
    Q.base = new int[MAXQSIZE];
    if(!Q.base)     exit(1);                //存储分配失败
    Q.front = Q.rear = 0;
}//InitQueue

void EnQueue(sqQueue &Q, int e){
    //插入元素e为Q的新的队尾元素
    if((Q.rear + 1) % MAXQSIZE == Q.front)
        return;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
}//EnQueue

bool QueueEmpty(sqQueue Q){
    //判断是否为空队
    if(Q.rear == Q.front)
        return true;
    return false;
}//QueueEmpty

void DeQueue(sqQueue &Q, int &u){
    //队头元素出队并置为u 
    u = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
}//DeQueue  
//-------------------

bool visited[MVNum];                    //访问标志数组
int FirstAdj(Graph G,int v)            //返回邻接点 
{
  int i;
  for(i=0;i<G.vexnum;i++)
    {
        if(G.arcs[v][i]==1&&visited[i]==false)
        return i;
     } 
     return -1;
} 

int NextAdj(Graph G,int v,int w)       // 返回v相对于w的下一个邻接点
{
  int i;
  for(i=w;i<G.vexnum; i++)
  {
    if(G.arcs[v][i]==1&&visited[i]==false)
    return i;
  }
  return -1;
}

int localvex(Graph G,int v)             //定位点 
{
    for(int i=0;i<G.vexnum;++i)
     if(G.vexs[i]==v) return i;
     return -1;
}

//创建邻接矩阵 
void CreateUDN(Graph &G)
{
    int i,j,k;
    cout<<"请输入总顶点数和总边数" ;
    cin>>G.vexnum>>G.arcnum;
    cout<<endl;
    cout<<"输入点的信息";
    for(i=0;i<G.vexnum;++i)
     cin>>G.vexs[i];
    for(i=0;i<G.vexnum;++i)               //初始化矩阵,边的权值皆为0 
       for(j=0;j<G.vexnum;++j)
       G.arcs[i][j]=0;
       for(k=0;k<G.arcnum;++k)           //以边 构造邻接矩阵
       {
        int v1,v2;
        cout<<"输入第"<<(k+1)<<"边依附的顶点";
        cin>> v1>>v2;
        i=localvex(G,v1); j=localvex(G,v2);  //确定v1,v2的位置 
            G.arcs[j][i]=G.arcs[i][j]=1;
       } 
}
 //邻接矩阵的深度优先遍历 
 void DFS(Graph G,Vtype v)
 {
    int w;
    cout<< G.vexs[v] << "    ";visited[v]=true;
    for(w=0;w<G.vexnum;++w)                                           //////
    if((G.arcs[v][w]==1)&&(!visited[w])) DFS(G,w);
  } 

      //按广度优先非递归遍历连通图G 
 void BFS (Graph G, int v){ 
    memset(visited,false,sizeof(visited));
    sqQueue Q;
    int u;                                              //权值 
    int w;

    cout << G.vexs[v] << "  ";    visited[v] = true;                            //访问第v个顶点,并置访问标志数组相应分量值为true 
    InitQueue(Q);                                                               //辅助队列Q初始化,置空         
    EnQueue(Q, v);                                                              //v进队 
    while(!QueueEmpty(Q)){                                                  //队列非空 
        DeQueue(Q, u);                                                          //队头元素出队并置为u
        for(w = FirstAdj(G, u); w >= 0; w = NextAdj(G, u, w)){
            if(!visited[w]){                                                    //w为u的尚未访问的邻接顶点 
              visited[w] = true;                    //访问w,并置访问标志数组相应分量值为true 
                EnQueue(Q, w);  cout << G.vexs[w] << "  ";                                                  //w进队 
            } 
        }
    } 
}

  int main(){
    Graph G;
    CreateUDN(G);
    cout << endl;
    cout << "无向图G创建完成!" << endl << endl;

    cout << "请输入遍历无向图G的起始点:";
    Vtype c;
    cin >> c;

    int i;
    for(i = 0 ; i < G.vexnum ; ++i){
        if(c == G.vexs[i])
            break;
    }
    cout << endl;
    while(i >= G.vexnum){
        cout << "该点不存在,请重新输入!" << endl;
        cout << "请输入遍历连通图的起始点:";
        cin >> c;
        for(i = 0 ; i < G.vexnum ; ++i){
            if(c == G.vexs[i])
                break;
        }
    }
    cout << "深度优先搜索遍历无向图G结果:" << endl;
    DFS(G , i);

    cout << "广度优先搜索遍历连通图结果:" << endl;
    BFS(G , i);
    cout <<endl;
    return 0;
}