/* 
图的广度优先算法（邻接矩阵的存储结构，无权图）：
    1. 算法思想：
        1. 访问顶点

        2. visited[i]置为true

        3. 入队
        
        4.  - 出队
            - 访问所有的邻接顶点，置true，入队，重复步骤4

    2. 回顾循环队列：
        1. 基本的结构：
            - 为了便于区分 front = rear是表示当前队列是满的还是空的，使用了带有一个空位置的队列

        2. 队列满的条件：
            - (rear + 1) / maxsize == front;
        
        3. 队列空的条件：
            - frint == raer;
    
*/
# include<iostream>
# include<string>

using namespace std;

# define MAX 30

bool visited[MAX];
int queue[MAX - 1];

struct Matrix{
    char vex[MAX];
    int arc[MAX][MAX];
    int vexnum, arcnum;
};


struct Queue{
    int element[MAX];
    int front;
    int rear;
};

void initQueue(Queue * q){
    q->front = q->rear=0;
    return;
}

int enterQueue(Queue * q, int x){
    if ((q->rear + 1) % MAX == q->front)
        return false;
    q->element[q->rear] = x;
    q->rear = (q->rear + 1) % MAX;
    return true;
}

int isEmptyQueue(Queue q){
    if (q.front == q.rear)
        return false;
    else
        return true;
}

int deleteQueue(Queue * q, int * x){
    if (q->rear == q->front)
        return false;
    * x = q->element[q->front];
    q->front = (q->front + 1) % MAX;
    return true;
}

int location(Matrix * g, char data){
    for (int i = 0; i < g->vexnum; i++){
        if (g->vex[i] == data)
            return i;
    }
    return -1;
}

void createMatrix(Matrix * g){
    char data1, data2;
    cout << "请输入顶点数和边数：" << endl;
    cin >> g -> vexnum >> g -> arcnum;

    cout << "请输入各个顶点的值: ";
    for(int i = 0; i < g -> vexnum; i++)
        cin >> g -> vex[i];

    for (int k = 0; k < g -> arcnum; k++){
        cout << "请输入第" << k + 1 << "条边的值：  " << endl;
        cin >> data1 >> data2;
        int i = location(g, data1);
        int j = location(g, data2);
        if (i != -1 && j != -1){
            g -> arc[i][j] = 1;
            g -> arc[j][i] = 1;
        }else{
            cout << "输入有误，请重新输入";
        }
    }
    return;
}

int firstAdjNode(Matrix g, int x){
    for (int i = 0; i < g.vexnum; i++){
        if(g.arc[x][i] != 0){
            return i;
        }
    }
    return -1;
}

int nextAdjNode(Matrix g, int x, int w){
    for (int i = w + 1; i < g.vexnum; i++){
        if (g.arc[x][i] != 0){
            return i;
        }
    }
    return -1;
}

void breadthSearch(Matrix g, int i){
    int x;
    Queue q;
    q.front = q.rear = 0;
    cout << g.vex[i] << endl;
    visited[i] = true;
    enterQueue(&q, i);

    while (isEmptyQueue(q)){

        deleteQueue(&q, &x);

        int w = firstAdjNode(g, x);

        while (w != -1){
            if (visited[w] == false){
                cout << g.vex[w] << endl;
                visited[w] = true;
                enterQueue(&q, w);
            }

            w = nextAdjNode(g, x, w);
        }
    }
    return;
}

void tranverseGraph(Matrix g){
    
    for (int i = 0; i < MAX; i++)
        visited[i] = false;

    for(int i = 0; i < g.vexnum; i++){
        if (!visited[i])
            breadthSearch(g, i);
    }

    return;
}

int main(){
    Matrix m;

    for (int i = 0; i < MAX; i++)
        for (int j = 0; j < MAX; j++)
            m.arc[i][j] = 0;

    createMatrix(&m); 

    for (int i = 0; i < m.vexnum; i++){
        for (int j = 0; j < m.vexnum; j++)
            cout << m.arc[i][j] << " ";
        cout << endl;
    }

    cout << "---------------------------------" << endl;

    tranverseGraph(m);

    return 0;
}