無向圖的廣度優先搜索（采用鄰接表存儲）C++實現

 

// 無向圖的廣度優先搜索（采用鄰接表存儲）.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include<iostream>

#define MAX 100

#define MAXQ 50

using namespace std;

struct edgeNode

{

 int no; //邊端的序號

 char info; //邊端的名稱

 struct edgeNode * next; //下一個

};

struct vexNode

{

 char info;  //節點名稱

 struct edgeNode *link; //與之相連的端點

};

//存儲節點信息

vexNode adjlist[MAX];

//循環隊列

int queue[MAXQ];

//訪問標志

bool visited[MAX];

//建立鄰接表存儲

void createGraph(vexNode *adjlist)

{

 int n,e;

 cout<<"請輸入節點數：";

 cin>>n;

 cout<<"請輸入邊數：";

 cin>>e;

 int i;

 for(i=1;i<=n;i++)

 {

  cout<<"請輸入節點"<<i<<"的名稱：";

  cin>>adjlist[i].info;

  adjlist[i].link = NULL;

 }

 edgeNode *p1,*p2;

   int v1,v2;

 for(i=1;i<=e;i++)

 {

  cout<<"請輸入邊"<<i<<"的二端的節點序號：";

  cin>>v1>>v2;

  p1 = (edgeNode*)malloc(sizeof(edgeNode));

  p2 = (edgeNode*)malloc(sizeof(edgeNode));

  p1->no = v1;

  p1->info = adjlist[v1].info;

  p1->next = adjlist[v2].link;

  adjlist[v2].link = p1;

  p2->no = v2;

  p2->info = adjlist[v2].info;

  p2->next = adjlist[v1].link;

  adjlist[v1].link = p2;

 }

}

//廣度優先搜索無向無權圖

void BFS(vexNode *adjlist,int *queue,bool *visited)

{

 int front,rear,v1;

 cout<<"請輸入從哪個序號的點開始搜索：";

 cin>>v1;

 front = 0;

 rear = 1;

 queue[rear] = v1;

 int i;

 //訪問標志清空

 for(i=1;i<MAX;i++)

  visited[i] = false;

 visited[v1] = true;

 cout<<"廣度優先搜索次序為："<<endl;

 cout<<"節點"<<v1<<",名稱"<<adjlist[v1].info<<endl;

 int vx;

 edgeNode *p;

 while(front != rear)

 {

  front = (front + 1)%MAXQ;

  vx = queue[front];

  p = adjlist[vx].link;

  while(p!=NULL)

  {

   if(!visited[p->no])

   {

    visited[p->no] = true;

    cout<<"節點"<<p->no<<",名稱"<<adjlist[p->no].info<<endl;

    rear = (rear + 1)%MAXQ;

    queue[rear] = p->no;

   }

   p=p->next;

  }

 }

}

int _tmain(int argc, _TCHAR* argv[])

{

 int cases;

 cout<<"請輸入案例的個數：";

 cin>>cases;

 while(cases--)

 {

  //創建鄰接表

  createGraph(adjlist);

  //廣度優先搜索

  BFS(adjlist,queue,visited);

 }

 system("pause");

 return 0;

}

---------------------------------------------程序測試--------------------------------------------------------

                   

 

                 

請輸入案例的個數：1

請輸入節點數：8

請輸入邊數：10

請輸入節點1的名稱：r

請輸入節點2的名稱：s

請輸入節點3的名稱：t

請輸入節點4的名稱：u

請輸入節點5的名稱：v

請輸入節點6的名稱：w

請輸入節點7的名稱：x

請輸入節點8的名稱：y

請輸入邊1的二端的節點序號：1 2

請輸入邊2的二端的節點序號：1 3

請輸入邊3的二端的節點序號：2 4

請輸入邊4的二端的節點序號：3 5

請輸入邊5的二端的節點序號：3 6

請輸入邊6的二端的節點序號：5 6

請輸入邊7的二端的節點序號：5 8

請輸入邊8的二端的節點序號：6 7

請輸入邊9的二端的節點序號：6 8

請輸入邊10的二端的節點序號：7 8

請輸入從哪個序號的點開始搜索：2

廣度優先搜索次序為：

節點2,名稱s

節點4,名稱u

節點1,名稱r

節點3,名稱t

節點6,名稱w

節點5,名稱v

節點8,名稱y

節點7,名稱x

請按任意鍵繼續. .

 

作者 heyongluoyao8