无向图连通分量的计算

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

评论

2 楼 jaychang 2010-07-29  

guooscar 写道

这位大哥很happy么~发的一个接一个的

呵呵，以前是放在另一个博客里的，全部粘贴过来了

1 楼 guooscar 2010-07-29  

这位大哥很happy么~发的一个接一个的