//c语言实现
#define MAX_VERTEX 30 
typedef enum{DG,DN,UDG,UDN}GraphKind; //有向图、有向网、无向图、无向网
typedef struct {
    VertexType vexs[MAX_VERTEX]; //顶点表
    int arcs[MAX_VERTEX][MAX_VERTEX]; //邻接矩阵
    int vexnum,arcnum;//顶点数、边数
    GraphKind kind; //图的种类    
}MGraph;

typedef struct ArcNode{
    int adjvex; //顶点序号
    struct ArcNode * nextarc;//指向下一个邻接点
    int weight; //权值
} ArcNode; //边结点类型
typedef struct VertexNode{
    VertexType data;
    ArcNode * firstarc; //指向第一个邻接点
}VertexNode, AdjList[MAX_VERTEX]; //邻接表结点类型
typedef struct {
    AdjList vertices; //邻接表
    int vexnum,arcnum; //顶点数、边数
    GraphKind kind; //图的种类
}ALGraph; 

//十字链表的边节点
typedef struct ArcNode{
    int tail;  //弧尾(起点)
    int head;   //弧头(终点)
    struct ArcNode * tnext;//同一弧尾的下一个节点(起点相同的下一条边)
    struct ArcNode * hnext;//同一弧头的下一个节点(终点相同的下一条边)
} ArcNode;

//十字链表的顶点节点
typedef struct VertexNode{
    char data;
    ArcNode *firstIn; //以该顶点为终点的第一条边
    ArcNode * firstOut; //以该顶点为起点的第一条边
} VertexNode;

typedef struct CrossList{
    VertexNode *adjlist; //十字链表的顶点数组
    int vexnum,arcnum; //图的顶点数和边数
} CrossList;

// 邻接多重表的边结点
typedef struct EdgeNode {
    int iVex;              // 顶点i的索引
    int jVex;              // 顶点j的索引
    struct EdgeNode *iNext; // 下一条依附于iVex的边
    struct EdgeNode *jNext; // 下一条依附于jVex的边
} EdgeNode;

// 邻接多重表的顶点结点
typedef struct VertexNode {
    char data;             // 顶点数据
    EdgeNode *firstEdge;   // 第一条依附于该顶点的边
} MVertexNode;

// 邻接多重表表示的图
typedef struct {
    MVertexNode *vertices;  // 顶点数组
    int vertexNum;         // 顶点数
} AMLGraph;

void DFS (ALGraph G,int v,bool visited,status(*visit)(ALGraph,int)){
    visited[v]=true; //访问顶点v
    visit(G,v); //访问顶点v
    for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
        if(!visited[w]) //如果w未被访问
            DFS(G,w,visited,visit); //递归访问w
}
void TraverseGraph(ALGraph G,status(*visit)(ALGraph,int)){
    bool visited[MAXVEX]; //访问标志数组
    for(int i=0;i<G.vexnum;i++)
        visited[i]=false; //初始化所有顶点为未访问
    for(int v=0;v<G.vexnum;v++)
        if(!visited[v]) //如果顶点v未被访问
            DFS(G,v,visited,visit); //递归访问v
}

void DFSTraverse(ALGraph G,status(*visit)(ALGraph,int)){
    bool visited[MAX_VERTEX];
    for(int v=0; v<G.vexnum; v++){
        visited[v]=false; //初始化所有顶点为未访问
    }
    LinkQueue Q; //创建一个队列
    InitQueue(Q); //初始化队列
    for(int v=0;v<G.vexnum;v++){
        if(!visited[v]){ //如果顶点v未被访问
            visited[v]=true; //访问顶点v
            visit(G,v); //访问顶点v
            EnQueue(Q,v); //入队列
            while(!QueueEmpty(Q)){ //队列不为空
                DeQueue(Q,v); //出队列
                for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){
                    if(!visited[w]){ //如果w未被访问
                        visited[w]=true; //访问顶点w
                        visit(G,w); //访问顶点w
                        EnQueue(Q,w); //入队列
                    }
                }
            }
        }
    }
}

typedef