实验五?无向图邻接表存储结构的创建、遍历及求连通分量

实验五 无向图邻接表存储结构的创建、遍历及求连通分量

#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;
}