#ifndef ALGRAPH_H
#define ALGRAPH_H

//领接表的存储结构
template <typename E>
struct ArcNode
{
    E weight;
    int adjvex;
    ArcNode<E> *nextarc;
};

//顶点结点
template <typename V, typename E>
struct VexNode
{
    V data;
    ArcNode<E> *firstarc;
};

//邻接表
template <typename V, typename E = int, int M = 16>
struct ALGraph
{
    VexNode<V,E> vexs[M];
    int vexnum;
    int arcnum;
    bool visited[M];
};


//邻接表基本操作

// InitGraph(&G)
template <typename V, typename E, int M>
void InitGraph(ALGraph<V,E,M> &G)
{
    G.vexnum = 0;
    G.arcnum = 0;
}

// DestoryGraph(&G)
template <typename V, typename E, int M>
void DestoryGraph(ALGraph<V,E,M> &G)
{
    //释放所有弧结点
    for (int v = 0; v < G.vexnum; v++){
        auto p =G.vexs[v].firstarc;
        while (p) {
            // auto s = p -> nextarc;
            // delete p;
            // p = s;

            auto s = p;
            p = p ->nextarc;
            delete s;
        }
    }

    //顶点数、弧的数量置零
    G.vexnum = 0;
    G.arcnum = 0;
}

// AddVertex(&G, vdata)
template <typename V, typename E, int M>
int AddVertex(ALGraph<V,E,M> &G, V vdata)
{
    if (G.vexnum == M) throw "Graph full";

    int v = G.vexnum;
    G.vexs[v].data = vdata;
    G.vexs[v].firstarc = nullptr;
    G.vexnum++; // 顶点个数加 1

    return v; // 返回新的顶点的编号
}

//AddEdge(&G,s,t,e)
template <typename V, typename E, int M>
void AddEdge(ALGraph<V,E,M> &G, int s, int t, E e)
{
    if (s < 0 || s >= G.vexnum) 
        throw "Invalid s";
    if (t < 0 || t >= G.vexnum) 
        throw "Invalid t";

    auto p = new ArcNode<E>;
    p -> adjvex = t;
    p -> weight = e;
    p -> nextarc = G.vexs[s].firstarc;
    G.vexs[s].firstarc = p;
    G.arcnum++;
}

#include <queue> // C++ 中的队列
 
// 从顶点 v 出发广度优先遍历图 G
template <typename V, typename E, int M, typename F>
void BFS(ALGraph<V,E,M> &G, int v, F visit)
{
    visit(G.vexs[v].data);
    G.visited[v] = true;

    std::queue<int> q; // 定义一个队列，初始化为空
    q.push(v); // 访问过的顶点入队列

    while (!q.empty()) {
        int v = q.front();
        q.pop(); // 出队列

        // 遍历并访问 v 的未访问的邻接点
        for (auto p = G.vexs[v].firstarc; p; p = p->nextarc) {
            int w = p->adjvex; // 邻接点的编号 w
            if (!G.visited[w]) {
                // 访问顶点 w
                visit(G.vexs[w].data);
                G.visited[w] = true;
                // w 入队列
                q.push(w);
            }
        }
    }
}

//广度优先遍历图 G
template <typename V, typename E, int M, typename F>
void BFSTraverse(ALGraph<V,E,M> &G, F visit)
{
    for (int v= 0; v < G.vexnum; v++)
        G.visited[v] = false;

    for (int v = 0; v < G.vexnum; v++)
        if (!G.visited[v])
        BFS(G, v, visit);
}


#endif