精品伊人久久大香线蕉,开心久久婷婷综合中文字幕,杏田冲梨,人妻无码aⅴ不卡中文字幕

#include<iostream.h>
typedef char vextype;
const MAXVER=21;
typedef struct listnode      
{ 
 int adjvex;
 struct listnode* next;  
}listnode;//表結點                         
            
typedef struct
{   
 vextype data;
 listnode  *first;
}headnode;//頭結點

typedef struct
{ 
 headnode vexs[MAXVER];
    int vexnum,arcnum;
} ALgraph;//圖

void createALgraph(ALgraph &G)
{
    int i, s, d;
    listnode *p,*q;
    cout<<"輸入圖的頂點數和邊數：";
    cin>>G.vexnum>>G.arcnum;
    for(i=1;i<=G.vexnum;i++)
    { 
  cout<<"\n輸入第"<<i<<"個頂點信息："; 
  cin>>G.vexs[i].data;
  G.vexs[i].first=NULL;
    } //輸入第i個結點值并初始化第i個單鏈表為空  
 for(i=1; i<=G.arcnum; i++)
    { 
  cout<<"\n輸入第"<<i<<"條邊的始點和終點：";
        cin>>s>>d;//s為始點，d為終點
        p=new listnode;        p->adjvex=d;
        p->next=G.vexs[s].first;
        G.vexs[s].first=p;
  //將新建的以d為信息的表結點p插入s單鏈表的頭結點后
        q=new listnode;        
  q->adjvex=s;
        q->next=G.vexs[d].first;
        G.vexs[d].first=q;
  //將新建的以s為信息的表結點q插入d單鏈表的頭結點后
    }
}

int visited[MAXVER];//定義全局數組遍歷visited
void dfs(ALgraph G, int v)//被遍歷的圖G采用鄰接表作為存儲結構，v為出發頂點編號
{ 
 listnode *p;
 cout<<G.vexs[v].data;
 visited[v]=1;
 p=G.vexs[v].first;
 while(p!=NULL)
 {
  if(visited[p->adjvex]==0)  dfs(G,p->adjvex);
  //若p所指表結點對應的鄰接頂點未訪問則遞歸地從該頂點出發調用dfs
  p=p->next;
    }
}

void dfsTraverse(ALgraph G)
{ 
 int v;
 //遍歷圖之前初始化各未訪問的頂點
 for(v=1; v<=G.vexnum; v++)
  visited[v]=0;
 //從各個未被訪問過的頂點開始進行深度遍歷
 for(v=1;v<=G.vexnum;v++)
  if(visited[v]==0)   dfs(G,v);
}

void dsfComp(ALgraph G)
{  int v;
   //遍歷G以前，初始化visited數組為0
   for(v=1;v<=G.vexnum;v++)
         visited[v]=0;
   for(v=1;v<=G.vexnum;v++)
      if(visited[v]==0)
      {
    cout<<endl<<"\n一個深度遍歷連通分量為：";
          dfs(G,v);
   }
}

void BFS(ALgraph G, int v)
//從頂點編號v出發，廣度遍歷鄰接表存儲的圖G
{  
 int queue[MAXVER], front ,rear;
    listnode* p;
    front=rear=0;
    cout<<G.vexs[v].data;
    visited[v]=1;
    queue[++rear]=v;
    while(front!=rear)
 { 
  v=queue[++front];
  p=G.vexs[v].first;
  while(p!=NULL)
  {  
   if(visited[p->adjvex]==0)
   { 
    v=p->adjvex;
    cout<<G.vexs[v].data;
    visited[v]=1;
    queue[++rear]=v;
   }
   p=p->next;
  }
 }
}

void BFSTraverse(ALgraph G)
{
 int v;
 //遍歷G以前，初始化visited數組為0
 for(v=1;v<=G.vexnum;v++)
  visited[v]=0;
 for(v=1;v<=G.vexnum;v++)
  if(visited[v]==0)
   BFS(G,v);
}

void BFSComp(ALgraph G)
{ 
 int v;
 //遍歷G以前，初始化visited數組為0
 for(v=1;v<=G.vexnum;v++)
  visited[v]=0;
 for(v=1;v<=G.vexnum;v++)
  if(visited[v]==0)
  {
   cout<<endl<<"\n一個廣度遍歷連通分量為：";
   BFS(G,v);
  }
}

void main()
{
 ALgraph g;
 createALgraph(g);
 cout<<endl<<"深度遍歷結果為：";
 dfsTraverse(g);
 dsfComp(g);
 cout<<endl<<"廣度遍歷結果為：";
 BFSTraverse(g);
 BFSComp(g);
 cout<<endl;
}