邻接矩阵存储的无向图深度优先(DFS)广度优先(BFS)遍历

比眉伴天荒 2022-08-10 09:40 216阅读 0赞

图的两种存储方式：邻接矩阵和邻接表；  
两种遍历方式：深度优先和广度优先；

首先以一个结构体存储一个图：

struct MGraph
    {
     int vertex[maxvertex];          //存顶点
     int arc[maxvertex][maxvertex];  //存边（邻接矩阵）
     int vertexnum,arcnum;           //顶点数和边数
    };

其次是对图的初始化：

void CreatMGraph(MGraph *&G)
    {
     int i,j;
     cin1>>G->vertexnum>>G->arcnum;  //输入顶点数和边数
    
     for(i=0;i<G->vertexnum;i++)  //输入每个顶点的值
        cin1>>G->vertex[i];
     for(i=0;i<G->vertexnum;i++)  //初始化邻接矩阵
       for(j=0;j<G->vertexnum;j++)
          G->arc[i][j]=0;
    
     for(i=0;i<G->arcnum;i++)  
     {
        int n,m,w;
        cin1>>n>>m>>w;    //修改邻接矩阵中的值
        G->arc[n][m]=w;
        G->arc[m][n]=w;
     }
    }

在此之前需要定义一个全局变量的visited数组：

int visited[maxvertex];   //标记已被访问过的顶点(全局变量)
    
    //广度优先遍历
    void BFS(MGraph *&G,int v)
    {
     queue<int> q;
     int x,j;
     if(!visited[v]) //即为visited[v]==0，也就是未被访问过
     {
      cout<<G->vertex[v]<<" ";
      visited[v]=1;
      q.push(v); //被访问的顶点入队
     }
     while(!q.empty()) //队不空进循环
     {
      x=q.front(); //取队头元素
      q.pop();  //队头出队
      for(j=0;j<G->vertexnum;j++)
       if (G->arc[x][j]&&!visited[j])
       {
        cout<<G->vertex[j]<<" ";
        visited[j]=1; //标记为访问过
        q.push(j);   //被访问的顶点继续入队
       }
     }
    }
    
    //深度优先遍历
    void DFS(MGraph *&G,int v)
    {
    nt j;
     if(!visited[v]) 
     {
      cout<<G->vertex[v]<<" ";
      visited[v]=1; //标记为访问过
     }
     for(j=0;j<G->vertexnum;j++) 
      if (G->arc[v][j]&&!visited[j])//邻接矩阵的第(v,j)元素不为0
      {                             //且未被访问过则递归
       DFS(G,j);
      }
    }

此为图的邻接矩阵的输出函数：

void Print(MGraph *G)
    {
     int i,j;
     for(i=0;i<G->vertexnum;i++)
     {
      for(j=0;j<G->vertexnum;j++)
       cout<<G->arc[i][j]<<" "; cout<<endl; } }

main函数调用上面函数：

int main()
    {
     MGraph *G=new MGraph;
     CreatMGraph(G);
    
     cout<<"输出邻接矩阵:"<<endl;
     Print(G);
    
     cout<<"深度优先搜索:";
     DFS(G,0);
     cout<<endl;
    
     memset(visited,0,sizeof(visited));//非常重要！！在下一个搜索之前一定要将标志位全部重新赋值为0
     cout<<"广度优先搜索:";
     BFS(G,0);
     cout<<endl;
    
     return 0;
    }