#include <stdio.h>
#include <stdlib.h>

#define MaxVertexNum 100
typedef char VertexType;
typedef int ElemType;
typedef int EdgeType;
typedef struct QNode{
    ElemType data;
    struct QNode* next;
}QNode, *QNodePtr;
typedef struct {
    QNode *front, *rear;
}Queue, *QueuePtr;

typedef struct {
    VertexType Vex[MaxVertexNum];
    EdgeType Edge[MaxVertexNum][MaxVertexNum];
    int vexnum, arnum;
}MGraph;

bool visited[MaxVertexNum] = {false};
int number;


void InitQueue(QueuePtr *q); //初始化
void InsertQueue(QueuePtr *q, ElemType c); //入队
void DeleteQueue(QueuePtr *q, ElemType *c);//出队
bool IsEmpty(QueuePtr *q); //判空

void InitGraph(MGraph* m, int number);
void DFS(MGraph* m, int start);
void BFS(MGraph* m);
void visit(int);

int main()
{
    int start;
    MGraph m;
    printf("Please the vertex number: ");
    scanf("%d", &number);
    InitGraph(&m, number);
    printf("Please input a starting vertex:");
    scanf("%d", &start);
    //DFS(&m, start);
    BFS(&m);
    printf("\n");
    return 0;
}

void InitGraph(MGraph *m, int number) {
    printf("please input the whole graph, 1(yes), 0(no)\n");
    int isExist;
    for (int i = 0; i < number; i++) {
        for (int j = 0; j < number; j++) {
            scanf("%d", &isExist);
            m->Edge[i][j] = isExist;
        }
    }
}

void DFS(MGraph *m, int start) {
    visit(start);
    visited[start] = true;
    for (int i = 0; i < number; i++) {
        if (!visited[i] && m->Edge[start][i]) {
            DFS(m, i);
        }
    }
}
void BFS(MGraph* m) {
    int vertex;
    QueuePtr *q = (QueuePtr *)malloc(sizeof(QueuePtr));
    InitQueue(q);
    for (int i = 0; i < number; i++) {
        if (!visited[i]) {
            visit(i);
            visited[i] = true;
            InsertQueue(q, i);
            while (!IsEmpty(q)) {
                DeleteQueue(q, &vertex);
                for (int j = 0; j < number;j++) {
                    if (!visited[j] && m->Edge[vertex][j]) {
                        visit(j);
                        visited[j] = true;
                        InsertQueue(q, j);
                    }
                }
            }
        }
    }
}
void visit(int vertex) {
    printf("%d ", vertex);
}
void InitQueue(QueuePtr *q) {
    (*q) = (QueuePtr)malloc(sizeof(Queue));
    (*q)->front = (*q)->rear = (QNodePtr)malloc(sizeof(QNode)); //头结点
    (*q)->front->next = NULL;
}
void InsertQueue(QueuePtr *q, ElemType c) {
    QNodePtr qNode = (QNodePtr)malloc(sizeof(QNode));
    qNode->data = c;
    qNode->next = NULL;
    (*q)->rear->next = qNode;
    (*q)->rear = qNode;
}
void DeleteQueue(QueuePtr *q, ElemType *c) {
    if ((*q)->front == (*q)->rear) {
        printf("The Queue is empty\n");
        return;
    }
    QNodePtr headNode = (*q)->front;
    QNodePtr firstNode = headNode->next;
    *c = firstNode->data;
    headNode->next = firstNode->next;
    if ((*q)->rear == firstNode) {
        (*q)->rear = (*q)->front;
    }
    free(firstNode);
}
bool IsEmpty(QueuePtr *q) {
    if ((*q)->front == (*q)->rear) {
        return true;
    } else {
                return false;
        }
}