無向圖連通分量的計算

#include<iostream>
#define MAX_VERTEX_NUM 50

using namespace std;

typedef char VerType;

typedef struct ArcNode                 //定義弧結點所在位置，
{
  int adj;
  int info;
  ArcNode *next;
}ArcNode;

typedef struct VerNode          //定義頂點(頂點資料，頂點所指向第一條弧的指針)
{
  VerType data;
  ArcNode *first;
}VerNode;

typedef struct AdjList      //圖的定義
{
  VerNode VerNodes[MAX_VERTEX_NUM]; //頂點集
  int verNum,arcNum;        //頂點數，弧數
}AdjList;

typedef struct Queue      //FIFO隊列
{
  int Item[MAX_VERTEX_NUM];
  int front,rear;
}Queue;

int visited[MAX_VERTEX_NUM];    //頂點通路标志數組

//定位某一結點的位置,找不到傳回0
int LocateGraph(const AdjList *g,const char data)
{
  for(int i=1;i<=g->verNum;i++)
  {
     if(g->VerNodes[i].data==data)
         return i;
  }
  return 0;
}

//初始化隊列
void InitQueue(Queue *Q)
{
  for(int i=1;i<=MAX_VERTEX_NUM;i++)
  {
     Q->Item[i]=0;
  }
  Q->front=Q->rear=1;
}


//建立圖的鄰接表
void CreateAdjList(AdjList *g)
{
  int s,d,weigth;
  char sChar,dChar;
  ArcNode *q=NULL;
  cout<<"輸入圖的頂點數,弧數\n";
  cin>>g->verNum>>g->arcNum;
  cout<<"輸入每個頂點的資訊\n";
  //初始化頂點
  for(int i=1;i<=g->verNum;i++)
  {
     cin>>g->VerNodes[i].data;
     g->VerNodes[i].first=NULL;
  }
  //初始化弧
  for(i=1;i<=g->arcNum;i++)
  {
     cout<<"輸入第"<<i<<"條弧的起始,目的,弧的權值"<<endl;
     cin>>sChar>>dChar>>weigth;
     s=LocateGraph(g,sChar);
     d=LocateGraph(g,dChar);       //定位該頂點的位置
     q=(ArcNode *)malloc(sizeof(ArcNode));
     q->adj=d;q->info=weigth;
     q->next=g->VerNodes[s].first;
     g->VerNodes[s].first=q;
  }
}

//初始化通路标志數組,0為未通路過相應的頂點i
void InitVisited(AdjList *g)
{
  for(int i=1;i<=g->verNum;i++)
  {
     visited[i]=0;
  }
}

//通路頂點值
void visit(AdjList *g,int v)
{
  cout<<g->VerNodes[v].data<<endl;
}

//廣度周遊圖從v頂點開始
void BFS(AdjList *g,int v)
{
  ArcNode *q=NULL;
  Queue *Q=(Queue *)malloc(sizeof(Queue));
  InitQueue(Q);       
  Q->Item[Q->rear]=v;visit(g,v);visited[v]=1;
  Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;
  while(Q->front!=Q->rear)                   //隊列不為空
  {
     v=Q->Item[Q->front];                   //取隊首元素
     Q->front=(Q->front+1)%MAX_VERTEX_NUM;
     q=g->VerNodes[v].first;
     while(q!=NULL)                         //同一層上（廣度搜尋的層）還有其他元素,則通路頂點，入隊
     {
       if(!visited[q->adj])
      {
         visit(g,q->adj);
         visited[q->adj]=1;
         Q->Item[Q->rear]=q->adj;
         Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;
         q=q->next;
      }
   }
}

}

//廣度周遊圖
int BFSTransfer(AdjList *g)
{
  int count=0;
  InitVisited(g);
  for(int i=1;i<=g->verNum;i++)
  {
     if(!visited[i])
     {
        BFS(g,i);
        count++;
     }
  }
  return count;
}

int main()
{
  int count;
  AdjList *g=(AdjList*)malloc(sizeof(AdjList));
  CreateAdjList(g);
  if((count=BFSTransfer(g))!=1)
     cout<<"為非連通圖,連通分量為"<<count<<endl;
  else
    cout<<"為連通通"<<endl;
   return 0;
}