【数据结构】以邻接矩阵作存储结构，求连通分量的个数，设计算法求图G的深度，深度优先序列输出

刺骨的言语ヽ痛彻心扉 2022-06-05 01:06 51阅读 0赞

#include <iostream>
    #define  MaxVerNum  100   
    typedef char ElemType;
    using namespace std; 
    typedef struct 
    {    ElemType vexs[MaxVerNum];
         int  arcs[MaxVerNum][MaxVerNum];
         int  vernum, arcnum;
    }AMGraph;
    int LocateVex(AMGraph G,ElemType v)
    {
    	for(int i=0;i<G.vernum;i++)
    	{
    		if(G.vexs[i]==v)
    		return i;
    	}
    }
    void  CreateUDG(AMGraph  &G)
    {   int i,j,k;
        ElemType v1,v2;
        cout<<"请依次输入图的顶点数和边数！\n";
        cin>>G.vernum >>G.arcnum;
        for (i=0;i<G.vernum;i++){
    	    cout<<"请输入顶点值；\n";
            cin>>G.vexs[i];
    		}  
        for (i=0;i< G.vernum;i++)
            for (j=0;j<G.vernum;j++)
                G.arcs[i][j]=0;    
        for (k=1;k<=G.arcnum;k++)
          {   cout<<"请输入一条边；\n";
    	      cin>>v1>>v2; 
              i=LocateVex(G,v1);j=LocateVex(G,v2);
              G.arcs[i][j]=G.arcs[j][i]=1;
          }
    }
    bool  visited[MaxVerNum];   
    int e=0;
    void  DFS(AMGraph G,int v)  
      {  int w;
         cout<<G.vexs[v];    visited[v]=true;  
          for ( w=0; w<G.vernum; w++ ) { 
               
               
    		    if(G.arcs[v][w]==1)
                  e++;
                if(G.arcs[v][w]==1&&!visited[w])
    			  DFS(G,w);
    		   
    		
      }
    }
    void DFSTraverse(AMGraph G)
       {   int v=0;
           for (v=0;v<G.vernum;v++) 
                visited[v]=false;
           for (v=0;v<G.vernum;v++) 
                if (!visited[v])   {   DFS(G,v); }
       }
    int  DFSTraverse1(AMGraph G)
       {   int k=0,v;
           for (v=0;v<G.vernum;v++) 
                visited[v]=false;
           for (v=0;v<G.vernum;v++) 
                if (!visited[v])   { k++;   DFS(G,v); }
            e=e/2;
            return  k;
       }
    
    
    int main()
    {
    	AMGraph G;
    	int m;
    	CreateUDG(G);
    	cout<<"该图按深度优先序列输出为；";
    	m=DFSTraverse1(G);
    	cout<<"\n该图的连通分量数为；"<<m;
    	cout<<"\n该图的边数为；"<<e;
    }