#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define MAXV 10
#define true 1
#define false 0
// 邻接矩阵存储结构；
typedef char VertexType;
typedef int  EdgeType;
typedef struct {
    VertexType *vertices;       // 节点表，存储节点的数据；
    EdgeType **edge;        // 邻接矩阵；
    int vexnum, arcnum;
} MGraph;
void InitMgraph(MGraph *G) {
    G->vertices = (VertexType *)malloc(MAXV * sizeof(VertexType));
    G->edge = (EdgeType **)malloc(MAXV * sizeof(EdgeType *));
    for (int i = 0; i < MAXV; i ++)
        G->edge[i] = (EdgeType *)malloc(MAXV * sizeof(EdgeType));
    for (int i = 0; i < MAXV; i ++)
        for (int j = 0; j < MAXV; j ++) 
            G->edge[i][j] = 0;
    G->vexnum = G->arcnum = 0;
}
void DestroyMGaph(MGraph *G) {
    free(G->vertices);
    G->vertices = NULL;
    for (int i = 0; i < MAXV; i ++)
        free(G->edge[i]);
    free(G->edge);
    G->edge = NULL;
    G->vexnum = G->arcnum = 0;
}
void ShowMGraph(MGraph G) {
    printf("  ");
    for (int i = 0; i < G.vexnum; i ++) printf("%c ", G.vertices[i]);       putchar(10);
    for (int i = 0; i < G.vexnum; i ++) {
        printf("%c ", G.vertices[i]);
        for (int j = 0; j < G.vexnum; j ++)
            printf("%d ", G.edge[i][j]);
        putchar(10);
    }
}
void InsertMVertex(MGraph *G, VertexType T) {
    if (G->vexnum == MAXV) return;
    G->vertices[G->vexnum ++] = T;
}
int  GetVertexPos(MGraph *G, VertexType T) {
    for (int i = 0; i < G->vexnum; i ++)
        if (T == G->vertices[i]) return i;
    return -1;
}
void InsertMEdge(MGraph *G, VertexType T1, VertexType T2) {
    int p1 = GetVertexPos(G, T1);
    int p2 = GetVertexPos(G, T2);
    if (p1 == -1 || p2 == -1) return;   // 若节点表中不存在对应节点，则不进行边的插入；
    G->edge[p1][p2] = G->edge[p2][p1] = 1;    // 若为无向图，则需要对邻接矩阵对称的赋值；
    G->arcnum ++;
}
void RemoveMEdge(MGraph *G, VertexType T1, VertexType T2) {
    int p1 = GetVertexPos(G, T1);
    int p2 = GetVertexPos(G, T2);
    if (p1 == -1 || p2 == -1) return;
    G->edge[p1][p2] = G->edge[p2][p1] = 0;
    G->arcnum --;
}
void RemoveMVertex(MGraph *G, VertexType T) {
    int p = GetVertexPos(G, T), n = G->vexnum, k = 0;
    if (p == -1) return;
    // 统计节点边的个数，修改arcnum；
    for (int j = 0; j < n; j ++)
        if (G->edge[p][j]) k ++;
    // 节点表的处理；
    for (int i = p; i < n - 1; i ++)
        G->vertices[i] = G->vertices[i + 1];
    // 邻接矩阵的处理
    for (int i = p; i < n - 1; i ++)
        for (int j = 0; j < n; j ++)
            G->edge[i][j] = G->edge[i + 1][j];
    for (int j = p; j < n - 1; j ++)
        for (int i = 0; i < n - 1; i ++)
            G->edge[i][j] = G->edge[i][j + 1];
    G->vexnum --, G->arcnum -= k;
}
// 返回第一个指向的节点位于节点表的下标；此时传入的参数是节点数据；
/*
int GetFirstNeighbor(MGraph *G, VertexType T) {
    int p = GetVertexPos(G, T);
    if (p == -1) return -1;
    for (int j = 0; j < G->vexnum; j ++)
        if (G->edge[p][j]) return j;
    return -1;
}
*/
/*
int GetNextNeighbor(MGraph *G, VertexType T1, VertexType T2) {
    int p1 = GetVertexPos(G, T1);
    int p2 = GetVertexPos(G, T2);
    if (p1 == -1 || p2 == -1) return -1;
    for (int j = p2 + 1; j < G->vexnum; j ++)
        if (G->edge[p1][j]) return j;
    return -1;
}
*/
/*
void MGraphDFS(MGraph *G, int p, int visit []) {
    // 访问数据；邻接节点未被访问且存在，继续向下dfs，否则回溯，上层节点递归下一个邻接节点；
    printf("%c --> ", G->vertices[p]);
    visit[p] = true;
    int q = GetFirstNeighbor(G, G->vertices[p]);        // 其实这里有层时间的无效浪费，即传入节点数据作为参数，在GetNeighbor函数中又要获得下标，其目的是为了将GetNeighbor函数不止是服务于dfs，而是通用的函数，此时节点下标未知 只知道两节点数据；
    while (q != -1) {
        if (!visit[q])  MGraphDFS(G, q, visit);
        q = GetNextNeighbor(G, G->vertices[p], G->vertices[q]);
    }
}
*/
// 更加便利的dfs方式，不考虑获取first与next邻接节点函数的通用性 这需要不断的转换节点数据与下标的关系，特别是根据节点数据获取下标这一时间开销
// 此时的优化就是dfs只处理下标，对于节点数据到下标的转换只在predfs中处理；
void MGraphDFS(MGraph *G, int p, int visit []) {
    printf("%c --> ", G->vertices[p]);
    visit[p] = true;
    // 对于不存在边的邻接节点 以及 已访问的节点 不会访问
    for (int i = 0; i < G->vexnum; i ++)
        if (!visit[i] && G->edge[p][i]) MGraphDFS(G, i, visit);
}
// 邻接矩阵的深度优先遍历；先是dfs的预备工作，参数是节点数据，然后是具体的dfs递归，参数是节点下标；
void MGraphPreDFS(MGraph *G, VertexType T) {
    // 申请visit数组并且初始化；从T节点开始向下递归遍历访问；
    int *visit = (int *)malloc(G->vexnum * sizeof(int));
    memset(visit, 0, G->vexnum * sizeof(int));
    int p = GetVertexPos(G, T);
    MGraphDFS(G, p, visit);
    printf("nul");
}
// WD T8 (有向图；对出度大于入度的节点进行输出并返回个数)
int printVertices(MGraph G) {
    // 对邻接矩阵进行一次遍历 获得 每个节点的度数，时间复杂度O(n^2)，空间复杂度O(n);
    int n = G.vexnum, cnt = 0;
    int *ID = (int *)malloc(n * sizeof(int)), *OD = (int *)malloc(n * sizeof(int));
    memset(ID, 0, n * sizeof(int));     memset(OD, 0, n * sizeof(int));
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            if (G.edge[i][j]) OD[i] ++, ID[j] ++;
    for (int i = 0; i < n; i ++)
        if (OD[i] > ID[i]) {
            printf("%c ", G.vertices[i]);
            cnt ++;
        }
    return cnt;
}



// 邻接表存储结构 (以无向图为例，此时需要对称加边与删边)；
typedef struct ArcNode {
    int adjvex;     // 弧所指向的节点位于邻接表中的下标 (所指向的顶点的位置)；
    struct ArcNode *nextarc;
} ArcNode;      // 称作 弧节点 或者 边表节点；
typedef struct VNode {
    VertexType data;
    ArcNode *firstarc;
} VNode;
typedef struct {
    VNode *adjList;   // 邻接表；
    int vexnum, arcnum;
} ALGraph;
void InitALGraph(ALGraph *G) {
    G->adjList = (VNode *)malloc(MAXV * sizeof(VNode));
    for (int i = 0; i < MAXV; i ++) G->adjList[i].firstarc = NULL;
    G->vexnum = G->arcnum = 0;
}
void DestroyALGraph(ALGraph *G) {
    free(G->adjList);
    G->adjList = NULL;
    G->vexnum = G->arcnum = 0;
}
void ShowALGraph(ALGraph *G) {
    ArcNode *p;
    for (int i = 0; i < G->vexnum; i ++) {
        printf("%d %c:>", i, G->adjList[i].data);
        p = G->adjList[i].firstarc;
        while (p != NULL) {
            printf("%c->", G->adjList[p->adjvex].data);
            p = p->nextarc;
        }
        printf("nul\n");
    }
}
int  GetVertexPos2(ALGraph *G, VertexType T) {
    for (int i = 0; i < G->vexnum; i ++)
        if (G->adjList[i].data == T) return i;
    return -1;
}
void InsertALVertex(ALGraph *G, VertexType T) {
    if (G->vexnum == MAXV) return;
    // 邻接表的节点下标从0开始；
    G->adjList[G->vexnum ++].data = T;
}
void InsertALEdge(ALGraph *G, VertexType T1, VertexType T2) {
    // 不仅是在T1的邻接表中添加节点T2的指向，同时需要在T2邻接表中加入T1指向；
    int p1 = GetVertexPos2(G, T1);
    int p2 = GetVertexPos2(G, T2);
    // 假如是节点不存在，此时无需插入边；
    if (p1 == -1 || p2 == -1) return;
    // 头插法，假设是简单图，不存在重边；
    ArcNode *s = (ArcNode *)malloc(sizeof(ArcNode));
    s->adjvex = p2, s->nextarc = G->adjList[p1].firstarc;
    G->adjList[p1].firstarc = s;

    ArcNode *t = (ArcNode *)malloc(sizeof(ArcNode));
    t->adjvex = p1, t->nextarc = G->adjList[p2].firstarc;
    G->adjList[p2].firstarc = t;
    // 更新边数的信息；
    G->arcnum ++;
}
void RemoveALEdge(ALGraph *G, VertexType T1, VertexType T2) {
    int p1 = GetVertexPos2(G, T1);
    int p2 = GetVertexPos2(G, T2);
    if (p1 == -1 || p2 == -1) return;
    ArcNode *pre = NULL, *p = G->adjList[p1].firstarc;
    while (p != NULL) {
        if (p->adjvex == p2) {
            if (pre == NULL) G->adjList[p1].firstarc = p->nextarc;
            else pre->nextarc = p->nextarc;
            free(p);    break;      // 简单图中最多只存在一条指向同一节点的边；
        }
        pre = p, p = p->nextarc;
    }
    // 若没找到p2，说明不存在此边，直接返回无需删除；若找到了，说明必定存在一条对称的边；
    if (p == NULL) return;
    pre = NULL, p = G->adjList[p2].firstarc;
    while (p != NULL) {
        if (p->adjvex == p1) {
            if (pre == NULL) G->adjList[p2].firstarc = p->nextarc;
            else pre->nextarc = p->nextarc;
            free(p);
        }
        pre = p, p = p->nextarc;
    }
}
// Hard繁琐程度的节点删除操作；
void RemoveALVertex(ALGraph *G, VertexType T) {
    // T顶点对应邻接表中ArcNode节点内存空间的释放；
    int v = GetVertexPos2(G, T), k = 0;
    ArcNode *p = G->adjList[v].firstarc, *pre = NULL;
    while (p != NULL) {
        k ++;
        G->adjList[v].firstarc = p->nextarc;
        free(p);
        p = G->adjList[v].firstarc;
    }
    // 此时将最后一个节点插入至该空闲位置，对于邻接矩阵的节点删除，为了保证节点编号的顺序性，此时是寻找后面的元素依次覆盖；
    G->adjList[v] = G->adjList[-- G->vexnum];       // 直接最后节点对v处进行覆盖 同时 更新vexnum信息；
    // 待节点删除之后，需删除边表中指向被删除节点adjvex的ArcNode节点；
    // 更新指向最后一个节点的边节点的adjvex信息，即由于最后一个节点位于邻接表的下标已经发生改变，因此需要更新边表信息，需寻找adjvex为当前的G->vexnum的节点；
    for (int i = 0; i < G->vexnum; i ++) {
        p = G->adjList[i].firstarc;
        while (p != NULL) {
            // 先删除v指向的ArcNode节点，再更新指向最后一个节点的adjvex，防止矛盾；
            if (p->adjvex == v) {
                if (pre == NULL) G->adjList[i].firstarc = p->nextarc;
                else pre->nextarc = p->nextarc;
                free(p);
            }
            if (p->adjvex == G->vexnum) p->adjvex = v;
            pre = p, p = p->nextarc;
        }
    }
    G->arcnum -= k;
}
void ALGraphDFS(ALGraph *G, int v, int visit []) {
    printf("%c --> ", G->adjList[v].data);
    visit[v] = true;
    for (ArcNode *p = G->adjList[v].firstarc; p != NULL; p = p->nextarc)
        if (!visit[p->adjvex]) ALGraphDFS(G, p->adjvex, visit);
}
void ALGraphPreDFS(ALGraph *G, VertexType T) {
    int *visit = (int *)malloc(G->vexnum * sizeof(int));
    memset(visit, 0, G->vexnum * sizeof(int));
    int p = GetVertexPos2(G, T);
    ALGraphDFS(G, p, visit);
    printf("nul");
}
// 广度优先搜索；建立一个队列 访问初始节点 加入初始节点至队列 队列弹出 访问邻接节点的数据 然后将全部邻接节点依次加入队列 直到队列为空；队列的数据类型为顶点节点位于顶点表中的下标；
void ALGraphBFS(ALGraph *G, VertexType T) {     // 无需准备工作；while循环来遍历队列；
    int v = GetVertexPos2(G, T);
    int *visit = (int *)malloc(G->vexnum * sizeof(int));
    memset(visit, 0, G->vexnum * sizeof(int));
    int *q = (int *)malloc(G->vexnum * sizeof(int));
    int tt = -1, hh = -1;     // tt == hh表示队列为空；q[++ tt]加入下一个元素 tt表示当前所指的队尾元素，q[++ hh]弹出队头元素，可以从初始时赋值的-1理解，指向同一个元素事表示该元素为空；

    printf("%c --> ", T);
    visit[v] = true;
    q[++ tt] = v;
    while (tt != hh) {
        v = q[++ hh];
        // 邻接矩阵的访问方式 以及 邻接表的访问方式；
        for (ArcNode *p = G->adjList[v].firstarc; p != NULL; p = p->nextarc) {
            int j = p->adjvex;
            if (!visit[j]) {
                printf("%c --> ", G->adjList[j].data);
                visit[j] = true;
                q[++ tt] = j;
            }
        }
    }
}

int main() {
    /* begin 邻接矩阵图的初始化；
    MGraph G;
    InitMgraph(&G);
    InsertMVertex(&G, 'A');
    InsertMVertex(&G, 'B');
    InsertMVertex(&G, 'C');
    InsertMVertex(&G, 'D');
    InsertMVertex(&G, 'E');
    InsertMVertex(&G, 'F');
    InsertMVertex(&G, 'G');
    InsertMVertex(&G, 'H');
    InsertMEdge(&G, 'A', 'B');
    InsertMEdge(&G, 'A', 'C');
    InsertMEdge(&G, 'B', 'D');
    InsertMEdge(&G, 'B', 'E');
    InsertMEdge(&G, 'C', 'F');
    InsertMEdge(&G, 'C', 'G');
    InsertMEdge(&G, 'D', 'H');
    InsertMEdge(&G, 'E', 'H');
    InsertMEdge(&G, 'G', 'F');

    ShowMGraph(G);
    MGraphPreDFS(&G, 'A');
    end */
    ALGraph G;
    InitALGraph(&G);
    InsertALVertex(&G, 'A');
    InsertALVertex(&G, 'B');
    InsertALVertex(&G, 'C');
    InsertALVertex(&G, 'D');
    InsertALVertex(&G, 'E');
    InsertALVertex(&G, 'F');
    InsertALVertex(&G, 'G');
    InsertALVertex(&G, 'H');
    InsertALEdge(&G, 'A', 'B');
    InsertALEdge(&G, 'A', 'C');
    InsertALEdge(&G, 'B', 'D');
    InsertALEdge(&G, 'B', 'E');
    InsertALEdge(&G, 'C', 'F');
    InsertALEdge(&G, 'C', 'G');
    InsertALEdge(&G, 'D', 'H');
    InsertALEdge(&G, 'E', 'H');
    InsertALEdge(&G, 'G', 'F');

    ShowALGraph(&G);
    ALGraphBFS(&G, 'A');
    return 0;
}