#include "stdio.h"
#include <stdlib.h>
#include <string.h>
using namespace std;

//邻接矩阵
struct graph{
    int vertexs; //顶点个数
    int edges;   //边的条数

    char* ver; //描述顶点的一维数组
    int** edg; //描述边的二维数组
};
//图的初始化
void InitGraph(graph *g, bool alloc = false);

//图的设置
void SetGraph(graph *g);

//通过顶点数剧找下标
int ver2idx(graph *g, char ver);

//打印图
void showGraph(graph *g);

//深度优先遍历
void DFS(graph *g);

//广度优先遍历
void BFS(graph *g);


int main()
{
    graph graphics;
    InitGraph(&graphics);
    SetGraph(&graphics);
    BFS(&graphics);


    getchar();
    return 0;
}

void InitGraph(graph *g, bool alloc){
    if (alloc){
        g = new graph;
    }
    g->edges = g->vertexs = 0;
    g->ver = NULL;
    g->edg = NULL;
}

void SetGraph(graph *g){
    printf("请输入顶点的个数:");
    scanf("%d", &g->vertexs);
    g->ver = new char[g->vertexs]; //开辟空间
    for (int i = 0; i < g->vertexs; i++){
        //printf("请输入第%d个顶点:", i + 1);
        g->ver[i] = 'A' + i;
    }
    
    //开内存
    g->edg = (int**)malloc(4 * (g->vertexs));
    for (int i = 0; i < g->vertexs; i++){
        g->edg[i] = new int[g->vertexs];
        memset(g->edg[i], 0, sizeof(int)*(g->vertexs)); //置空

    }
    printf("请输入有多少条边：");
    scanf("%d", &(g->edges));

    char buff[20];
    for (int i = 0; i < g->edges; i++){
        printf("请输入第%d条边:(A,B)\n",i+1);
        scanf("%s", buff);

        int row = ver2idx(g, buff[0]);
        int low = ver2idx(g, buff[2]);
        //            printf("%d%d", row, low);
        g->edg[row][low] = 1;

        showGraph(g);
    }

    

}

int ver2idx(graph *g, char ver){
    for (int i = 0; i < g->vertexs; i++){
        if (g->ver[i] == ver)
            return i;
    }
    return -1;
}

void showGraph(graph *g){
    for (int i = 0; i < g->vertexs; i++)
    {
        printf("%c ", g->ver[i]);
    }
    printf("\n");

    for (int i = 0; i < g->vertexs; i++)
    {
        for (int j = 0; j < g->vertexs; j++)
        {
            printf("%d ", g->edg[i][j]);
        }
        printf("\n");
    }
}

void DFS(graph *g){



}


void BFS(graph *g){
    char c;
    scanf("%*c"); //清空缓存区
    printf("请输入顶点：");
    scanf("%c", &c);
    printf("起始顶点为%c! \n", c);

    int begInd = ver2idx(g, c);
    //标记所有顶点都没有找过
    bool *isFind = new bool[g->vertexs];
    memset(isFind, 0, g->vertexs);

    //标记起始顶点找过，并打印
    printf("%c", g->ver[begInd]);
    int count = 1;
    int i;
    while (1)
    {
        //从当前节点开始找相邻节点
        for (i = 0; i < g->vertexs; i++)
        {
            if (g->edg[begInd][i] == 1)
            {
                if (isFind[i] == false)
                {
                    printf("%c", g->ver[i]);
                    isFind[i] = true;
                    begInd = i; //下一个从找到的开始
                    count++;
                    break;
                }
            }
        }
        if (i == g->vertexs)  //回溯
        {
            begInd = (begInd + 1) % (g->vertexs);
        }
        //没有下一个顶点了，回到起始顶点，换下一个相邻顶点
        if (count > g->vertexs) break;
    }
    printf("\n");
}