資料結構 — 圖 之 廣度優先周遊

【描述】：  圖的bfs

【輸入】：

8

1 2 -1

0 3 4 -1

0 5 6 -1

1 7 -1

1 7 -1

2 7 -1

2 7 -1

3 4 5 6 -1

【輸出】：

0 1 2 3 4 5 6 7

/*
 *圖的廣度優先周遊
 *1.鍊式隊列（連結清單的頭節點中存資料、節點的尾插法、頭節點的删除）
 *2.bfs 

8 
1 2 -1 
0 3 4 -1 
0 5 6 -1 
1 7 -1 
1 7 -1 
2 7 -1 
2 7 -1 
3 4 5 6 -1 
 */

#include<iostream>
#include<memory.h>
using namespace std;

/* 宏定義 */
#define MAX_NUM 50
#define ElementType int

/* 定義動态鍊式隊列節點 */
typedef struct QueueNode{
    ElementType data;
    struct QueueNode *next;
}QueueNode,*QueuePointer;

/* 鄰接表表節點 */
typedef struct TableNode{
    ElementType vertex;
    struct TableNode *next;
}TableNode,*TablePointer;

/* 頭節點數組 */
TablePointer graph[MAX_NUM];

/* 定義visited數組 */
bool visited[MAX_NUM];

/* 頂點數 */
int vertices;

/*
 * 動态鍊式隊列
 * 1.addq -> 入隊
 * 2.deleteq -> 出隊
 */
/*在鍊式隊列的隊尾插入元素*/
void addq(QueuePointer &front, QueuePointer &rear, ElementType item){
    QueuePointer temp = new QueueNode;
    temp->data = item;
    temp->next = NULL;

    //插入
    if(front){
        rear->next = temp;
    }else{
        front = temp;
    }
    rear = temp;
}

/*從鍊式隊列的頭部出隊*/
ElementType deleteq(QueuePointer &front){
    QueuePointer temp = front;
    ElementType item;

    //出隊
    item = temp->data;
    front = temp->next;
    delete temp;
    return item;
}

/*
 * 鄰接表存儲的圖
 * 1.建立圖
 * 2.bfs
 */
/*建立*/
void CreateGraph(){  
    ElementType ch;  
    TablePointer pnew,qnode;  
    pnew = qnode = NULL;  
  
    for(int i = 0; i < vertices; i++){  
        cin>>ch;  
        if(ch == -1) continue; /*當ch 為-1是結束該vertex的建立*/  
        //連結清單的頭節點  
        pnew = new TableNode;  
        pnew->vertex = ch;  
        pnew->next = NULL;  
        //将頭節點存入 頭節點數組  
        graph[i] = pnew;  
        //尾插法建立連結清單  
        cin>>ch;  
        while(ch != -1){  
            //申請記憶體、處理資料域、處理指針域  
            qnode = new TableNode;  
            qnode->vertex = ch;  
            qnode->next =NULL;  
            //插入  
            pnew->next = qnode;  
            //更新尾指針  
            pnew = qnode;  
            cin>>ch;  
        }  
    }  
}

/*bfs*/
void bfs(ElementType v){
    TablePointer w;
    QueuePointer front, rear;
    front = rear = NULL;

    //将第一個節點輸入、标記、進隊
    cout<<v<<endl;
    visited[v] = true;
    addq(front, rear, v);

    //通路隊列中的節點、通路與其相鄰的節點、已經被visited的節點将不再通路
    while(front){
        v = deleteq(front);
    //掃vertex v 的連結清單
        for(w = graph[v]; w; w=w->next){
            if(!visited[w->vertex]){
                cout<<w->vertex<<" ";
        visited[w->vertex] = true;
                addq(front, rear, w->vertex);
            }
    }
    }
    cout<<endl;
}

int main(){  
  
    memset(visited,false,sizeof(visited));  
  
    cout<<"輸入頂點數"<<endl;  
    cin>>vertices;  
  
    CreateGraph();  
    cout<<"廣度優先周遊"<<endl;  
    bfs(0);  

    return 0;  
}