神秘的“圖”--資料結構

資料結構實驗：圖的有關操作

（1）鍵盤輸入資料，建立一個無向圖的鄰接表。

（2）輸出該鄰接表。

（3）采用鄰接表存儲實作無向圖的深度優先周遊。

（4）采用鄰接表存儲實作無向圖的廣度優先周遊。

代碼如下：

#include <iostream>

using namespace std;

#define MVNum 100              //最大頂點數

#define MAXQSIZE 100            //最大隊列長度

typedef char VerTexType;          //假設頂點的資料類型為字元型  

typedef int ArcType;                      //假設邊的權值類型為整型

//----隊列的定義及操作--------

typedef struct {

   ArcType* base;              //初始化的動态配置設定存儲空間

   int front;                //頭指針，若隊列不空，指向隊頭元素

   int rear;                //尾指針，若隊列不空，指向隊尾元素的下一個位置

}sqQueue;

void InitQueue(sqQueue& Q) {

   //構造一個空隊列Q

   Q.base = new ArcType[MAXQSIZE];

   if (!Q.base)     exit(1);        //存儲配置設定失敗

   Q.front = Q.rear = 0;

}//InitQueue

void EnQueue(sqQueue& Q, ArcType e) {

   //插入元素e為Q的新的隊尾元素

   if ((Q.rear + 1) % MAXQSIZE == Q.front)

       return;

   Q.base[Q.rear] = e;

   Q.rear = (Q.rear + 1) % MAXQSIZE;

}//EnQueue

bool QueueEmpty(sqQueue Q) {

   //判斷是否為空隊

   if (Q.rear == Q.front)

       return true;

   return false;

}//QueueEmpty

void DeQueue(sqQueue& Q, ArcType& u) {

   //隊頭元素出隊并置為u  

   u = Q.base[Q.front];

   Q.front = (Q.front + 1) % MAXQSIZE;

}//DeQueue                    

//--------------------------------------------------

//-------------圖的鄰接表---------------------

typedef struct ArcNode {                    //邊結點  

   int adjvex;                            //該邊所指向的頂點的位置  

   struct ArcNode* nextarc;              //指向下一條邊的指針  

}ArcNode;

typedef struct VNode {

   VerTexType data;                      //頂點資訊

   ArcNode* firstarc;                    //指向第一條依附該頂點的邊的指針  

}VNode, AdjList[MVNum];                   //AdjList表示鄰接表類型  

typedef struct {

   AdjList vertices;                     //鄰接表  

   int vexnum, arcnum;                  //圖的目前頂點數和邊數  

}ALGraph;

bool visited[MVNum];                   //通路标志數組，其初值為"false"  

int LocateVex(ALGraph G, VerTexType v) {

   //确定點v在G中的位置

   for (int i = 0; i < G.vexnum; ++i)

       if (G.vertices[i].data == v)

           return i;

   return -1;

}//LocateVex

void CreateUDG(ALGraph& G) {

   //采用鄰接表表示法，建立無向圖G

   int i, k;

   cout << "請輸入總頂點數，總邊數，以空格隔開:";

   cin >> G.vexnum >> G.arcnum;        //輸入總頂點數，總邊數  

   cout << endl;

   cout << "輸入點的名稱，如a" << endl;

   for (i = 0; i < G.vexnum; ++i) {            //輸入各點，構造表頭結點表

       cout << "請輸入第" << (i + 1) << "個點的名稱:";

       cin >> G.vertices[i].data;             //輸入頂點值  

       G.vertices[i].firstarc = NULL;      //初始化表頭結點的指針域為NULL  

   }//for

   cout << endl;

   cout << "輸入邊依附的頂點，如a b" << endl;

   for (k = 0; k < G.arcnum; ++k) {            //輸入各邊，構造鄰接表

       VerTexType v1, v2;

       int i, j;

       cout << "請輸入第" << (k + 1) << "條邊依附的頂點:";

       cin >> v1 >> v2;                     //輸入一條邊依附的兩個頂點

       i = LocateVex(G, v1);  j = LocateVex(G, v2);

       //确定v1和v2在G中位置，即頂點在G.vertices中的序号  

       ArcNode* p1 = new ArcNode;                 //生成一個新的邊結點*p1  

       p1->adjvex = j;                       //鄰接點序号為j  

       p1->nextarc = G.vertices[i].firstarc;  G.vertices[i].firstarc = p1;

       //将新結點*p1插入頂點vi的邊表頭部

       ArcNode* p2 = new ArcNode;        //生成另一個對稱的新的邊結點*p2  

       p2->adjvex = i;                       //鄰接點序号為i  

       p2->nextarc = G.vertices[j].firstarc;  G.vertices[j].firstarc = p2;

       //将新結點*p2插入頂點vj的邊表頭部  

   }//for  

}//CreateUDG

void DFS(ALGraph G, int v) {                //圖G為鄰接表類型  

   cout << G.vertices[v].data << "   ";

   visited[v] = true;    //通路第v個頂點，并置通路标志數組相應分量值為true  

   ArcNode* p = G.vertices[v].firstarc;    //p指向v的邊連結清單的第一個邊結點  

   while (p != NULL) {                      //邊結點非空  

       int w = p->adjvex;                   //表示w是v的鄰接點  

       if (!visited[w])  DFS(G, w);         //如果w未通路，則遞歸調用DFS  

       p = p->nextarc;                      //p指向下一個邊結點  

   }

}//DFS

//廣度優先周遊

void BFS(ALGraph G, int v)

{

   ArcNode* p;

   sqQueue Q;

   int u;   //記錄出隊頂點位置  

   //初始化狀态數組  

   for (int i = 0; i < G.vexnum; i++)

       visited[i] = false;

   //初始化隊列

   InitQueue(Q);

   EnQueue(Q, v);

   cout << G.vertices[v].data << " ";

   visited[v] = true;

   while (!QueueEmpty(Q))

   {

       DeQueue(Q, u);

       ArcNode* p = G.vertices[u].firstarc;

       while (p != NULL)

       {

           if (!visited[p->adjvex])

           {

               cout << G.vertices[p->adjvex].data << " ";

               visited[p->adjvex] = true;

               EnQueue(Q, p->adjvex);

           }

           p = p->nextarc;

       }

   }

}

int main() {

   cout << "************算法6.6　采用鄰接表表示圖的深度優先搜尋周遊**************" << endl << endl;

   ALGraph G;

   CreateUDG(G);

   cout << endl;

   cout << "無向連通圖G建立完成！" << endl << endl;

   cout << "請輸入周遊連通圖的起始點：";

   VerTexType c;

   cin >> c;

   int i;

   for (i = 0; i < G.vexnum; ++i) {

       if (c == G.vertices[i].data)

           break;

   }

   cout << endl;

   while (i >= G.vexnum) {

       cout << "該點不存在，請重新輸入！" << endl;

       cout << "請輸入周遊連通圖的起始點：";

       cin >> c;

       for (i = 0; i < G.vexnum; ++i) {

           if (c == G.vertices[i].data)

               break;

       }

   }

 cout << "深度優先搜尋周遊圖結果：" << endl;

   DFS(G, i);

   cout << endl;

   cout << "廣度優先搜尋周遊連通圖結果：" << endl;

   BFS(G, i);

  cout << endl;

   return 0;

}//main