图

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

typedef char VertexType; // 顶点类型
typedef int EdgeType; // 边上的权值
#define MAXVEX 100 // 最大顶点数
#define INF 65535 // 如果两个顶点之间不可达，用无穷表示距离
#define DIRECTED true // 是否为有向图

typedef struct {
    VertexType vexs[MAXVEX]; // 顶点表
    EdgeType arc[MAXVEX][MAXVEX]; // 邻接矩阵，可看做边表
    int vexNum, edgeNum; // 图中当前的顶点数和边数
} MGraph;

// 创建邻接矩阵
int Graph_Create (MGraph &G) {
    int vi, vj, weight;
    // 输入顶点数和边数
    printf("请输入顶点数：");
    scanf("%d", &G.vexNum);
    printf("请输入边数：");
    scanf("%d", &G.edgeNum);

    for (int i = 0; i < G.vexNum; i++) { // 为每个顶点初始化信息
        printf("请输入第 %d 个的顶点名称: ", i + 1);
        scanf(" %c", &G.vexs[i]);
    }
    for (int i = 0; i < G.vexNum; i++) { // 初始化顶点之间的权值 默认为无穷
        for (int j = 0; j < G.vexNum; j++) {
            G.arc[i][j] = INF;
        }
    }

    printf("下标为 -1 -1 则退出创建边\n");
    for(int i = 0; i < G.edgeNum; i++){ // 根据边的条数，为每一条边赋值
        printf("请输入要创建边的下标 v1 v2 ");
        scanf("%d %d", &vi, &vj);
        if (vi == -1 && vj == -1) break;
        printf("请输入边为[%d][%d]的权值 weight = ", vi, vj);
        scanf("%d", &weight);
        G.arc[vi][vj] = weight;
        // 在无向网中满足图对称性，即Vi-Vj 和Vj-Vi的距离相等，实际就是一条路径
        if (!DIRECTED) {
            G.arc[vj][vi] = weight;
        }
    }
}

// 打印图
void Graph_Show (MGraph G) {
    // 打印顶点
    for (int i = 0; i < G.vexNum; i++)
        printf("%c", G.vexs[i]);
    printf("\n");
    // 打印邻接矩阵
    for(int i = 0; i < G.vexNum; i++){
        for(int j = 0; j < G.vexNum; j++){
            if(G.arc[i][j] == INF) printf("%6s", "∞");
            else printf("%6d", G.arc[i][j]);
        }
        printf("\n");
    }
}

int main () {
    MGraph G;
    Graph_Create(G);
    Graph_Show(G);
    return 0;
}

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

#define MaxVertexNum 26
// 是否为有向图
#define DIRECTED true
typedef char VertexType;
typedef int ArcWeight;

// 边表结点
typedef struct ArcNode {
    int adjvex; // 该边指向的顶点下标
    ArcWeight weight; // 权值
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

// 顶点表结点
typedef struct VNode{
    VertexType data; // 顶点信息
    ArcNode *first; // 指向该顶点的第一条边的指针
} VNode, AdjList[MaxVertexNum];

// 邻接表的图结构
typedef struct {
    AdjList adjList; // 邻接表
    int vexnum, arcnum; // 图的顶点数和边数
} ALGraph;

// 队列-广度

// 循环队列算法，辅助完成二叉树层次遍历
#define MaxSize 50   // 定义队列中元素的最大个数
typedef struct {
  int data[MaxSize]; // 存放队列元素
  int front, rear;   // 队头和队尾指针 
} SqQueue;

// 初始化队列（带头结点）
void Queue_Init(SqQueue &Q) {
  Q.rear = Q.front = 0;
}

// 判断队列是否为空
bool Queue_Empty(SqQueue Q) {
  return Q.front == Q.rear;
}

// 入队
bool Queue_En(SqQueue &Q, int e) {
  if ((Q.rear + 1) % MaxSize == Q.front) return false; // 队满则报错
  Q.data[Q.rear] = e;
  Q.rear = (Q.rear + 1) % MaxSize; // 队尾指针加 1 取模
  return true;
}

// 出队
bool Queue_De(SqQueue &Q, int &e) {
  if (Queue_Empty(Q)) return false; // 队空则报错
  e = Q.data[Q.front];
  Q.front = (Q.front + 1) % MaxSize;
  return true;
}

void ALGraph_Create (ALGraph &G) {
    // 对顶点表结点进行初始化
    for (int i = 0; i < MaxVertexNum; i++) {
        G.adjList[i].first = NULL;
    }
    printf("输入顶点 边个数（空格间隔）：");
    scanf("%d %d", &G.vexnum, &G.arcnum);
    // 建立顶点表
    for (int i = 0; i < G.vexnum; i++) {
        printf("请输入第%d个顶点的值：", i + 1);
        scanf(" %c", &G.adjList[i].data);
        G.adjList[i].first = NULL;
    }
    // 建立边表
    int vi, vj;
    ArcWeight weight;
    printf("下标为 -1 -1 则退出创建边\n");
    for (int i = 0; i < G.arcnum; i++) {
        // 代表两个顶点 vi 指向 vj 的边，注意vi vj是从0开始的
        printf("请输入要创建边的两个顶点 vi vj ");
        scanf("%d %d", &vi, &vj);
        if (vi == -1 && vj == -1) break;
        printf("请输入边为[%d->%d]的权值 weight = ", vi, vj);
        scanf("%d", &weight);
        ArcNode *arcNode;
        arcNode = (ArcNode *)malloc(sizeof(ArcNode));
        // 通过头插法插入新边，
        arcNode->next = G.adjList[vi].first;
        arcNode->adjvex = vj; // 该边指向的顶点位置
        arcNode->weight = weight;
        G.adjList[vi].first = arcNode;
        // 如果是无向图，则还需要创建相反方向的边
        if (!DIRECTED) {
            ArcNode *arcNode2;
            arcNode2 = (ArcNode *)malloc(sizeof(ArcNode));
            // 相反方向，放入vj里 头插
            arcNode2->next = G.adjList[vj].first;
            arcNode2->adjvex = vi;
            arcNode2->weight = weight;
            G.adjList[vj].first = arcNode2;
        }
    }
}

// 访问标记数组
bool BFSVisited[MaxVertexNum];
// 对图G进行广度优先遍历
// 注意：对邻接表进行广度优先遍历的结果并不唯一
void BFS (ALGraph G, int v) { // 从顶点V出发，广度优先遍历图G
    for (int i = 0; i < G.vexnum; i++)
        BFSVisited[i] = false;
    SqQueue Q;
    Queue_Init(Q); // 初始化辅助队列Q
    Queue_En(Q, v); // 将顶点 v 的下标入队
    // 访问初始顶点 V
    printf("\n对顶点【%d】进行广度优先遍历：", v);
    BFSVisited[v] = true; // 对 v 进行已访问标记
    ArcNode *p;
    while (Queue_Empty(Q) == false) { // 当队列非空时
        Queue_De(Q, v); // 将队头元素出队并送到 v 中
        p = G.adjList[v].first; // 指针 p 指向顶点 v 的边表
        while (p != NULL) {
            // 遍历该顶点的出边表
            if (BFSVisited[p->adjvex] == false) {
                printf("%d、", p->adjvex); // 访问顶点
                BFSVisited[p->adjvex] = true;
                Queue_En(Q, p->adjvex); // 将顶点下标入队
            }
            p = p->next;
        }
    }
}

// 对整个图进行遍历
void BFS_Traverse (ALGraph G) {
    for (int i = 0; i < G.vexnum; i++)
        BFS(G, i);
}

// 访问标记数组
bool DFSVisited[MaxVertexNum];
// 深度优先遍历
// 注意：对邻接表进行深度优先遍历的结果并不唯一
void DFS (ALGraph G, int v) {
    ArcNode *p;
    p = G.adjList[v].first;
    printf("%d、", v);
    DFSVisited[v] = true;
    while (p) {
        int j = p->adjvex;
        if (DFSVisited[j] == false) {
            DFS(G, j);
        }
        p = p->next;
    }
}
// 对整个图进行遍历
void DFS_Traverse (ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        // 从顶点V出发，深度优先遍历图G
        for (int j = 0; j < G.vexnum; j++)
            DFSVisited[j] = false;

        printf("\n对顶点【%d】进行深度优先遍历：", i);
        DFS(G, i);
    }
}

void ALGraph_Show (ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        printf("%c", G.adjList[i].data);
        ArcNode *p = G.adjList[i].first;
        while (p) {
            printf("->%d", p->adjvex);
            p = p->next;
        }
        printf("\n");
    }
}

int main () {
    printf("注意，当前创建图为有向图\n");
    ALGraph G;
    ALGraph_Create(G);
    ALGraph_Show(G);
    BFS_Traverse(G);
    DFS_Traverse(G);
    return 0;
}

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

#define MaxVertexNum 26
// 是否为有向图
#define DIRECTED true
typedef char VertexType;
typedef int ArcWeight;

// 边表结点
typedef struct ArcNode {
    int adjvex; // 该边指向的顶点下标
    ArcWeight weight; // 权值
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

// 顶点表结点
typedef struct VNode{
    VertexType data; // 顶点信息
    ArcNode *first; // 指向该顶点的第一条边的指针
} VNode, AdjList[MaxVertexNum];

// 邻接表的图结构
typedef struct {
    AdjList adjList; // 邻接表
    int vexnum, arcnum; // 图的顶点数和边数
} ALGraph;

// 队列-广度

// 循环队列算法，辅助完成二叉树层次遍历
#define MaxSize 50   // 定义队列中元素的最大个数
typedef struct {
  int data[MaxSize]; // 存放队列元素
  int front, rear;   // 队头和队尾指针 
} SqQueue;

// 初始化队列（带头结点）
void Queue_Init(SqQueue &Q) {
  Q.rear = Q.front = 0;
}

// 判断队列是否为空
bool Queue_Empty(SqQueue Q) {
  return Q.front == Q.rear;
}

// 入队
bool Queue_En(SqQueue &Q, int e) {
  if ((Q.rear + 1) % MaxSize == Q.front) return false; // 队满则报错
  Q.data[Q.rear] = e;
  Q.rear = (Q.rear + 1) % MaxSize; // 队尾指针加 1 取模
  return true;
}

// 出队
bool Queue_De(SqQueue &Q, int &e) {
  if (Queue_Empty(Q)) return false; // 队空则报错
  e = Q.data[Q.front];
  Q.front = (Q.front + 1) % MaxSize;
  return true;
}

void ALGraph_Create (ALGraph &G) {
    // 对顶点表结点进行初始化
    for (int i = 0; i < MaxVertexNum; i++) {
        G.adjList[i].first = NULL;
    }
    printf("输入顶点 边个数（空格间隔）：");
    scanf("%d %d", &G.vexnum, &G.arcnum);
    // 建立顶点表
    for (int i = 0; i < G.vexnum; i++) {
        printf("请输入第%d个顶点的值：", i + 1);
        scanf(" %c", &G.adjList[i].data);
        G.adjList[i].first = NULL;
    }
    // 建立边表
    int vi, vj;
    ArcWeight weight;
    printf("下标为 -1 -1 则退出创建边\n");
    for (int i = 0; i < G.arcnum; i++) {
        // 代表两个顶点 vi 指向 vj 的边，注意vi vj是从0开始的
        printf("请输入要创建边的两个顶点 vi vj ");
        scanf("%d %d", &vi, &vj);
        if (vi == -1 && vj == -1) break;
        printf("请输入边为[%d->%d]的权值 weight = ", vi, vj);
        scanf("%d", &weight);
        ArcNode *arcNode;
        arcNode = (ArcNode *)malloc(sizeof(ArcNode));
        // 通过头插法插入新边，
        arcNode->next = G.adjList[vi].first;
        arcNode->adjvex = vj; // 该边指向的顶点位置
        arcNode->weight = weight;
        G.adjList[vi].first = arcNode;
        // 如果是无向图，则还需要创建相反方向的边
        if (!DIRECTED) {
            ArcNode *arcNode2;
            arcNode2 = (ArcNode *)malloc(sizeof(ArcNode));
            // 相反方向，放入vj里 头插
            arcNode2->next = G.adjList[vj].first;
            arcNode2->adjvex = vi;
            arcNode2->weight = weight;
            G.adjList[vj].first = arcNode2;
        }
    }
}

// 访问标记数组
bool BFSVisited[MaxVertexNum];
// 对图G进行广度优先遍历
// 注意：对邻接表进行广度优先遍历的结果并不唯一
void BFS (ALGraph G, int v) { // 从顶点V出发，广度优先遍历图G
    for (int i = 0; i < G.vexnum; i++)
        BFSVisited[i] = false;
    SqQueue Q;
    Queue_Init(Q); // 初始化辅助队列Q
    Queue_En(Q, v); // 将顶点 v 的下标入队
    // 访问初始顶点 V
    printf("\n对顶点【%d】进行广度优先遍历：", v);
    BFSVisited[v] = true; // 对 v 进行已访问标记
    ArcNode *p;
    while (Queue_Empty(Q) == false) { // 当队列非空时
        Queue_De(Q, v); // 将队头元素出队并送到 v 中
        p = G.adjList[v].first; // 指针 p 指向顶点 v 的边表
        while (p != NULL) {
            // 遍历该顶点的出边表
            if (BFSVisited[p->adjvex] == false) {
                printf("%d、", p->adjvex); // 访问顶点
                BFSVisited[p->adjvex] = true;
                Queue_En(Q, p->adjvex); // 将顶点下标入队
            }
            p = p->next;
        }
    }
}

// 对整个图进行遍历
void BFS_Traverse (ALGraph G) {
    for (int i = 0; i < G.vexnum; i++)
        BFS(G, i);
}

// 访问标记数组
bool DFSVisited[MaxVertexNum];
// 深度优先遍历
// 注意：对邻接表进行深度优先遍历的结果并不唯一
void DFS (ALGraph G, int v) {
    ArcNode *p;
    p = G.adjList[v].first;
    printf("%d、", v);
    DFSVisited[v] = true;
    while (p) {
        int j = p->adjvex;
        if (DFSVisited[j] == false) {
            DFS(G, j);
        }
        p = p->next;
    }
}
// 对整个图进行遍历
void DFS_Traverse (ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        // 从顶点V出发，深度优先遍历图G
        for (int j = 0; j < G.vexnum; j++)
            DFSVisited[j] = false;

        printf("\n对顶点【%d】进行深度优先遍历：", i);
        DFS(G, i);
    }
}

void ALGraph_Show (ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        printf("%c", G.adjList[i].data);
        ArcNode *p = G.adjList[i].first;
        while (p) {
            printf("->%d", p->adjvex);
            p = p->next;
        }
        printf("\n");
    }
}

int main () {
    printf("注意，当前创建图为有向图\n");
    ALGraph G;
    ALGraph_Create(G);
    ALGraph_Show(G);
    BFS_Traverse(G);
    DFS_Traverse(G);
    return 0;
}

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

#define MaxVertexNum 26
// 是否为有向图
#define DIRECTED true
typedef char VertexType;
typedef int ArcWeight;

// 边表结点
typedef struct ArcNode {
    int adjvex; // 该边指向的顶点下标
    ArcWeight weight; // 权值
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

// 顶点表结点
typedef struct VNode{
    VertexType data; // 顶点信息
    ArcNode *first; // 指向该顶点的第一条边的指针
} VNode, AdjList[MaxVertexNum];

// 邻接表的图结构
typedef struct {
    AdjList adjList; // 邻接表
    int vexnum, arcnum; // 图的顶点数和边数
} ALGraph;

// 队列-广度

// 循环队列算法，辅助完成二叉树层次遍历
#define MaxSize 50   // 定义队列中元素的最大个数
typedef struct {
  int data[MaxSize]; // 存放队列元素
  int front, rear;   // 队头和队尾指针 
} SqQueue;

// 初始化队列（带头结点）
void Queue_Init(SqQueue &Q) {
  Q.rear = Q.front = 0;
}

// 判断队列是否为空
bool Queue_Empty(SqQueue Q) {
  return Q.front == Q.rear;
}

// 入队
bool Queue_En(SqQueue &Q, int e) {
  if ((Q.rear + 1) % MaxSize == Q.front) return false; // 队满则报错
  Q.data[Q.rear] = e;
  Q.rear = (Q.rear + 1) % MaxSize; // 队尾指针加 1 取模
  return true;
}

// 出队
bool Queue_De(SqQueue &Q, int &e) {
  if (Queue_Empty(Q)) return false; // 队空则报错
  e = Q.data[Q.front];
  Q.front = (Q.front + 1) % MaxSize;
  return true;
}

void ALGraph_Create (ALGraph &G) {
    // 对顶点表结点进行初始化
    for (int i = 0; i < MaxVertexNum; i++) {
        G.adjList[i].first = NULL;
    }
    printf("输入顶点 边个数（空格间隔）：");
    scanf("%d %d", &G.vexnum, &G.arcnum);
    // 建立顶点表
    for (int i = 0; i < G.vexnum; i++) {
        printf("请输入第%d个顶点的值：", i + 1);
        scanf(" %c", &G.adjList[i].data);
        G.adjList[i].first = NULL;
    }
    // 建立边表
    int vi, vj;
    ArcWeight weight;
    printf("下标为 -1 -1 则退出创建边\n");
    for (int i = 0; i < G.arcnum; i++) {
        // 代表两个顶点 vi 指向 vj 的边，注意vi vj是从0开始的
        printf("请输入要创建边的两个顶点 vi vj ");
        scanf("%d %d", &vi, &vj);
        if (vi == -1 && vj == -1) break;
        printf("请输入边为[%d->%d]的权值 weight = ", vi, vj);
        scanf("%d", &weight);
        ArcNode *arcNode;
        arcNode = (ArcNode *)malloc(sizeof(ArcNode));
        // 通过头插法插入新边，
        arcNode->next = G.adjList[vi].first;
        arcNode->adjvex = vj; // 该边指向的顶点位置
        arcNode->weight = weight;
        G.adjList[vi].first = arcNode;
        // 如果是无向图，则还需要创建相反方向的边
        if (!DIRECTED) {
            ArcNode *arcNode2;
            arcNode2 = (ArcNode *)malloc(sizeof(ArcNode));
            // 相反方向，放入vj里 头插
            arcNode2->next = G.adjList[vj].first;
            arcNode2->adjvex = vi;
            arcNode2->weight = weight;
            G.adjList[vj].first = arcNode2;
        }
    }
}

// 访问标记数组
bool BFSVisited[MaxVertexNum];
// 对图G进行广度优先遍历
// 注意：对邻接表进行广度优先遍历的结果并不唯一
void BFS (ALGraph G, int v) { // 从顶点V出发，广度优先遍历图G
    for (int i = 0; i < G.vexnum; i++)
        BFSVisited[i] = false;
    SqQueue Q;
    Queue_Init(Q); // 初始化辅助队列Q
    Queue_En(Q, v); // 将顶点 v 的下标入队
    // 访问初始顶点 V
    printf("\n对顶点【%d】进行广度优先遍历：", v);
    BFSVisited[v] = true; // 对 v 进行已访问标记
    ArcNode *p;
    while (Queue_Empty(Q) == false) { // 当队列非空时
        Queue_De(Q, v); // 将队头元素出队并送到 v 中
        p = G.adjList[v].first; // 指针 p 指向顶点 v 的边表
        while (p != NULL) {
            // 遍历该顶点的出边表
            if (BFSVisited[p->adjvex] == false) {
                printf("%d、", p->adjvex); // 访问顶点
                BFSVisited[p->adjvex] = true;
                Queue_En(Q, p->adjvex); // 将顶点下标入队
            }
            p = p->next;
        }
    }
}

// 对整个图进行遍历
void BFS_Traverse (ALGraph G) {
    for (int i = 0; i < G.vexnum; i++)
        BFS(G, i);
}

// 访问标记数组
bool DFSVisited[MaxVertexNum];
// 深度优先遍历
// 注意：对邻接表进行深度优先遍历的结果并不唯一
void DFS (ALGraph G, int v) {
    ArcNode *p;
    p = G.adjList[v].first;
    printf("%d、", v);
    DFSVisited[v] = true;
    while (p) {
        int j = p->adjvex;
        if (DFSVisited[j] == false) {
            DFS(G, j);
        }
        p = p->next;
    }
}
// 对整个图进行遍历
void DFS_Traverse (ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        // 从顶点V出发，深度优先遍历图G
        for (int j = 0; j < G.vexnum; j++)
            DFSVisited[j] = false;

        printf("\n对顶点【%d】进行深度优先遍历：", i);
        DFS(G, i);
    }
}

void ALGraph_Show (ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        printf("%c", G.adjList[i].data);
        ArcNode *p = G.adjList[i].first;
        while (p) {
            printf("->%d", p->adjvex);
            p = p->next;
        }
        printf("\n");
    }
}

int main () {
    printf("注意，当前创建图为有向图\n");
    ALGraph G;
    ALGraph_Create(G);
    ALGraph_Show(G);
    BFS_Traverse(G);
    DFS_Traverse(G);
    return 0;
}

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

typedef char VertexType; // 顶点类型
typedef int EdgeType; // 边上的权值
#define MAXVEX 100 // 最大顶点数
#define INF 65535 // 如果两个顶点之间不可达，用无穷表示距离
#define DIRECTED true // 是否为有向图

typedef struct {
    VertexType vexs[MAXVEX]; // 顶点表
    EdgeType arc[MAXVEX][MAXVEX]; // 邻接矩阵，可看做边表
    int vexNum, edgeNum; // 图中当前的顶点数和边数
} MGraph;

// 创建邻接矩阵
int Graph_Create (MGraph &G) {
    int vi, vj, weight;
    // 输入顶点数和边数
    printf("请输入顶点数：");
    scanf("%d", &G.vexNum);
    printf("请输入边数：");
    scanf("%d", &G.edgeNum);

    for (int i = 0; i < G.vexNum; i++) { // 为每个顶点初始化信息
        printf("请输入第 %d 个的顶点名称: ", i + 1);
        scanf(" %c", &G.vexs[i]);
    }
    for (int i = 0; i < G.vexNum; i++) { // 初始化顶点之间的权值 默认为无穷
        for (int j = 0; j < G.vexNum; j++) {
            G.arc[i][j] = INF;
        }
    }

    printf("下标为 -1 -1 则退出创建边\n");
    for(int i = 0; i < G.edgeNum; i++){ // 根据边的条数，为每一条边赋值
        printf("请输入要创建边的下标 v1 v2 ");
        scanf("%d %d", &vi, &vj);
        if (vi == -1 && vj == -1) break;
        printf("请输入边为[%d][%d]的权值 weight = ", vi, vj);
        scanf("%d", &weight);
        G.arc[vi][vj] = weight;
        // 在无向网中满足图对称性，即Vi-Vj 和Vj-Vi的距离相等，实际就是一条路径
        if (!DIRECTED) {
            G.arc[vj][vi] = weight;
        }
    }
}

// 找到未在最小生成树中且边权值最小的顶点
int Find_Min_V(MGraph G, int cost[], bool visited[]) {
    int minCost = INF; // 最小边权值初始设为无穷大
    int minVertex = -1; // 初始化最小边权值对应的顶点索引

    for (int v = 0; v < G.vexNum; v++) {
        if ((visited[v] == false) && cost[v] < minCost) {
            minCost = cost[v]; // 更新最小边权值
            minVertex = v; // 记录对应顶点索引
        }
    }
    return minVertex; // 返回最小边权值对应的顶点索引
}

// v 为开始顶点
void Prim (MGraph G, int v) {
    int parent[MAXVEX]; // 记录每个顶点在最小生成树中的父节点
    int cost[MAXVEX]; // 记录每个顶点与当前最小生成树的最小边权值
    bool visited[MAXVEX]; // 记录顶点是否已经在最小生成树中

    // 初始化权值
    for (int i = 0; i < G.vexNum; i++) {
        parent[i] = -1;
        cost[i] = INF;
        visited[i] = false;
    }

    cost[v] = 0; // 指定的开始顶点作为初始顶点
    parent[v] = -1; // 初始顶点没有父结点

    // 主循环，构建最小生成树
    // 最小生成树有 vexNum - 1 条边，当 i 达到 vexNum - 1 时，算法就已经完成了构建最小生成树的过程
    for (int i = 0; i < G.vexNum - 1; i++) {
        // 找到最小边权值的顶点，第一次循环找到的是开始顶点
        int minV = Find_Min_V(G, cost, visited);
        // 非联通的
        if (minV == -1) continue;
        visited[minV] = true;
        // 更新其他顶点到最小生成树的边权值和父结点
        for (int j = 0; j < G.vexNum; j++) {
            if (
                G.arc[minV][j]
                && (visited[j] == false)
                && G.arc[minV][j] < cost[j]
            ) {
                parent[j] = minV; // 顶点 j 的父节点是顶点 u
                cost[j] = G.arc[minV][j]; // 更新顶点 j 到最小生成树的边权值
            }
        }
    }
    // 输出构建的最小生成树的顶点
    printf("Vertices in the MST:\n");
    for (int i = 0; i < G.vexNum; i++)
    {
        printf("v=%d p=%d c=%d\n", i, parent[i], cost[i]);
    }
}

// 打印图
void Graph_Show (MGraph G) {
    // 打印顶点
    for (int i = 0; i < G.vexNum; i++)
        printf("%c", G.vexs[i]);
    printf("\n");
    // 打印邻接矩阵
    for(int i = 0; i < G.vexNum; i++){
        for(int j = 0; j < G.vexNum; j++){
            if(G.arc[i][j] == INF) printf("%6s", "∞");
            else printf("%6d", G.arc[i][j]);
        }
        printf("\n");
    }
}

int main () {
    MGraph G;
    // Graph_Create(G);
    G.vexNum = 6;
    G.edgeNum = 10;
    G.vexs[0] = 'a';
    G.vexs[1] = 'b';
    G.vexs[2] = 'c';
    G.vexs[3] = 'd';
    G.vexs[4] = 'e';
    G.vexs[5] = 'f';
    for (int i = 0; i < G.vexNum; i++) { // 初始化顶点之间的权值 默认为无穷
        for (int j = 0; j < G.vexNum; j++) {
            G.arc[i][j] = INF;
        }
    }
    // 设置边
    G.arc[0][1] = G.arc[1][0] = 6;
    G.arc[0][3] = G.arc[3][0] = 5;
    G.arc[0][2] = G.arc[2][0] = 1;
    G.arc[1][2] = G.arc[2][1] = 5;
    G.arc[2][3] = G.arc[3][2] = 5;
    G.arc[1][4] = G.arc[4][1] = 3;
    G.arc[2][4] = G.arc[4][2] = 6;
    G.arc[2][5] = G.arc[5][2] = 4;
    G.arc[3][5] = G.arc[5][3] = 2;
    G.arc[4][5] = G.arc[5][4] = 6;
    Graph_Show(G);
    Prim(G, 0);
    return 0;
}

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

typedef char VertexType; // 顶点类型
typedef int EdgeType; // 边上的权值
#define MAXVEX 100 // 最大顶点数
#define INF 65535 // 如果两个顶点之间不可达，用无穷表示距离
#define DIRECTED true // 是否为有向图

// Kruskal 辅助边
typedef struct {
    int source;
    int target;
    int weight;
} Edge;

typedef struct {
    VertexType vexs[MAXVEX]; // 顶点表
    EdgeType arc[MAXVEX][MAXVEX]; // 邻接矩阵，可看做边表
    int vexNum, edgeNum; // 图中当前的顶点数和边数
} MGraph;

// 创建邻接矩阵
int Graph_Create (MGraph &G) {
    int vi, vj, weight;
    // 输入顶点数和边数
    printf("请输入顶点数：");
    scanf("%d", &G.vexNum);
    printf("请输入边数：");
    scanf("%d", &G.edgeNum);

    for (int i = 0; i < G.vexNum; i++) { // 为每个顶点初始化信息
        printf("请输入第 %d 个的顶点名称: ", i + 1);
        scanf(" %c", &G.vexs[i]);
    }
    for (int i = 0; i < G.vexNum; i++) { // 初始化顶点之间的权值 默认为无穷
        for (int j = 0; j < G.vexNum; j++) {
            G.arc[i][j] = INF;
        }
    }

    printf("下标为 -1 -1 则退出创建边\n");
    for(int i = 0; i < G.edgeNum; i++){ // 根据边的条数，为每一条边赋值
        printf("请输入要创建边的下标 v1 v2 ");
        scanf("%d %d", &vi, &vj);
        if (vi == -1 && vj == -1) break;
        printf("请输入边为[%d][%d]的权值 weight = ", vi, vj);
        scanf("%d", &weight);
        G.arc[vi][vj] = weight;
        // 在无向网中满足图对称性，即Vi-Vj 和Vj-Vi的距离相等，实际就是一条路径
        if (!DIRECTED) {
            G.arc[vj][vi] = weight;
        }
    }
}

// 比较函数，用于排序边
int compareEdges (const void *a, const void *b) {
    return ((Edge *)a)->weight - ((Edge *)b)->weight;
}

// Kruskal 克鲁斯卡尔算法
void Kruskal (MGraph G, Edge edges[]) {
    // 每个顶点配置一个标记值（并查集思想）
    int *sets = (int *)malloc(G.vexNum * sizeof(int));
    // 初始状态下，每个顶点的标记都不相同
    for (int i = 0; i < G.vexNum; i++) {
        sets[i] = i;
    }
    // 根据权值，对所有边进行升序排序
    qsort(edges, G.edgeNum, sizeof(edges[0]), compareEdges);

    // 遍历所有边
    int num = 0; // 记录加入的边数
    // 由于已经按升序进行排序，只需对边进行遍历每个都是最小权值边
    for (int i = 0; i < G.edgeNum; i++) {
        // 找到当前边的两个顶点在 sets 数组中的位置下标
        int source = edges[i].source;
        int target = edges[i].target;
        int weight = edges[i].weight;
        // 如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路
        if (sets[source] != sets[target]) {
            printf("s=%d, t=%d, w=%d\n", source, target, weight);
            num++;
            // 将新加入的生成树的顶点标记全改为一样的
            for (int j = 0; j < G.vexNum; j++) {
                // 找到集合的 target 标记
                if (sets[j] == sets[target]) {
                    // 使 targe 标记 = source 的标记（相反也行）
                    sets[j] = sets[source];
                }
            }
            // 如果选中的边数量=顶点数-1，证明最小生成树已形成，退出循环
            if (num == G.vexNum - 1) {
                break;
            }
        }
    }
}

// 打印图
void Graph_Show (MGraph G) {
    // 打印顶点
    for (int i = 0; i < G.vexNum; i++)
        printf("%c", G.vexs[i]);
    printf("\n");
    // 打印邻接矩阵
    for(int i = 0; i < G.vexNum; i++){
        for(int j = 0; j < G.vexNum; j++){
            if(G.arc[i][j] == INF) printf("%6s", "∞");
            else printf("%6d", G.arc[i][j]);
        }
        printf("\n");
    }
}

int main () {
    MGraph G;
    // Graph_Create(G);
    G.vexNum = 6;
    G.vexs[0] = 'a';
    G.vexs[1] = 'b';
    G.vexs[2] = 'c';
    G.vexs[3] = 'd';
    G.vexs[4] = 'e';
    G.vexs[5] = 'f';
    for (int i = 0; i < G.vexNum; i++) { // 初始化顶点之间的权值 默认为无穷
        for (int j = 0; j < G.vexNum; j++) {
            G.arc[i][j] = INF;
        }
    }
    G.edgeNum = 10;
    // 设置边
    G.arc[0][1] = G.arc[1][0] = 6;
    G.arc[0][3] = G.arc[3][0] = 5;
    G.arc[0][2] = G.arc[2][0] = 1;
    G.arc[1][2] = G.arc[2][1] = 5;
    G.arc[2][3] = G.arc[3][2] = 5;
    G.arc[1][4] = G.arc[4][1] = 3;
    G.arc[2][4] = G.arc[4][2] = 6;
    G.arc[2][5] = G.arc[5][2] = 4;
    G.arc[3][5] = G.arc[5][3] = 2;
    G.arc[4][5] = G.arc[5][4] = 6;
    Edge *edges = (Edge *)malloc(G.edgeNum * sizeof(Edge));
    int edgeIndex = 0;
    // 构建边数组，只使用矩阵的上三角
    for (int i = 0; i < G.vexNum; i++) {
        for (int j = i + 1; j < G.vexNum; j++) {
            if (G.arc[i][j] != INF) {
                edges[edgeIndex].source = i;
                edges[edgeIndex].target = j;
                edges[edgeIndex].weight = G.arc[i][j];
                edgeIndex++;
            }
        }
    }
    Graph_Show(G);
    Kruskal(G, edges);
    return 0;
}

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

typedef char VertexType; // 顶点类型
typedef int EdgeType; // 边上的权值
#define MAXVEX 100 // 最大顶点数
#define INF 65535 // 如果两个顶点之间不可达，用无穷表示距离
#define DIRECTED true // 是否为有向图

typedef struct {
    VertexType vexs[MAXVEX]; // 顶点表
    EdgeType arc[MAXVEX][MAXVEX]; // 邻接矩阵，可看做边表
    int vexNum, edgeNum; // 图中当前的顶点数和边数
} MGraph;

// 创建邻接矩阵
int Graph_Create (MGraph &G) {
    int vi, vj, weight;
    // 输入顶点数和边数
    printf("请输入顶点数：");
    scanf("%d", &G.vexNum);
    printf("请输入边数：");
    scanf("%d", &G.edgeNum);

    for (int i = 0; i < G.vexNum; i++) { // 为每个顶点初始化信息
        printf("请输入第 %d 个的顶点名称: ", i + 1);
        scanf(" %c", &G.vexs[i]);
    }
    for (int i = 0; i < G.vexNum; i++) { // 初始化顶点之间的权值 默认为无穷
        for (int j = 0; j < G.vexNum; j++) {
            G.arc[i][j] = INF;
        }
    }

    printf("下标为 -1 -1 则退出创建边\n");
    for(int i = 0; i < G.edgeNum; i++){ // 根据边的条数，为每一条边赋值
        printf("请输入要创建边的下标 v1 v2 ");
        scanf("%d %d", &vi, &vj);
        if (vi == -1 && vj == -1) break;
        printf("请输入边为[%d][%d]的权值 weight = ", vi, vj);
        scanf("%d", &weight);
        G.arc[vi][vj] = weight;
        // 在无向网中满足图对称性，即Vi-Vj 和Vj-Vi的距离相等，实际就是一条路径
        if (!DIRECTED) {
            G.arc[vj][vi] = weight;
        }
    }
}

// 找到距离值最小的顶点，从尚未包括在最短路径树中的顶点集合中选取
int minDistance (MGraph G, int dist[], bool visited[]) {
    int min = INF, minIndex;
    // 遍历所有顶点，找到距离最小的顶点
    for (int v = 0; v < G.vexNum; v++)
        if (visited[v] == false && dist[v] <= min)
            min = dist[v], minIndex = v;

    return minIndex;
}

// 打印构造的距离数组
void printPath (int parent[], int i) {
    // 递归打印路径
    if (parent[i] == -1)
        return;
    printPath(parent, parent[i]);
    printf(" -> %d", i);
}

// 实现Dijkstra算法的函数
// 计算从源顶点到其他顶点的最短路径并输出
void Dijkstra (MGraph G, int src) {
    // 保存从源到每个顶点的最短路径
    int dist[G.vexNum];
    // 标记顶点是否在最短路径树中
    bool visited[G.vexNum];
    // 存储每个顶点在最短路径中的前一个顶点
    int parent[G.vexNum];
    // 初始化距离、最短路径树集合和前驱顶点
    for (int i = 0; i < G.vexNum; i++) {
        dist[i] = INF; // 初始化距离为无限大
        visited[i] = false; // 尚未包括在最短路径树中
        parent[i] = -1; // 初始前驱为 -1
    }

    dist[src] = 0; // 源顶点到自身的距离为0

    // 查找原顶点到其他顶点的最短路径
    for (int i = 0; i < G.vexNum - 1; i++) {
        // 找到距离最小的顶点，第一次循环找到的是开始顶点
        int u = minDistance(G, dist, visited);
        visited[u] = true;
        // 其他没更新到的顶点 dist 任然为 INF
        // 所以在 i 的下次循环中 找到的顶点是相邻顶点
        // 更新从找到的最小顶点到其相邻顶点的距离和前驱顶点
        for (int v = 0; v < G.vexNum; v++) {
            if (
                !visited[v]
                && G.arc[u][v]
                && dist[u] != INF
                // 判断是否找到了一条比当前路径更短的路径
                && dist[u] + G.arc[u][v] < dist[v]
            ) {
                dist[v] = dist[u] + G.arc[u][v];
                parent[v] = u; // 更新前驱结点
            }
        }
    }
    // 输出每个顶点的最短路径及路径本身
    printf("Vertex   Distance    Path
");
    for (int i = 0; i < G.vexNum; i++) {
        printf("%d   %d          %d", i, dist[i], src);
        printPath(parent, i);  // 打印路径
        printf("
");
    }
}

// 打印图
void Graph_Show (MGraph G) {
    // 打印顶点
    for (int i = 0; i < G.vexNum; i++)
        printf("%c", G.vexs[i]);
    printf("\n");
    // 打印邻接矩阵
    for(int i = 0; i < G.vexNum; i++){
        for(int j = 0; j < G.vexNum; j++){
            if(G.arc[i][j] == INF) printf("%6s", "∞");
            else printf("%6d", G.arc[i][j]);
        }
        printf("\n");
    }
}

int main () {
    MGraph G;
    // Graph_Create(G);
    G.vexNum = 6;
    G.edgeNum = 10;
    G.vexs[0] = 'a';
    G.vexs[1] = 'b';
    G.vexs[2] = 'c';
    G.vexs[3] = 'd';
    G.vexs[4] = 'e';
    G.vexs[5] = 'f';
    for (int i = 0; i < G.vexNum; i++) { // 初始化顶点之间的权值 默认为无穷
        for (int j = 0; j < G.vexNum; j++) {
            G.arc[i][j] = INF;
        }
    }
    // 设置边
    G.arc[0][1] = G.arc[1][0] = 6;
    G.arc[0][3] = G.arc[3][0] = 5;
    G.arc[0][2] = G.arc[2][0] = 1;
    G.arc[1][2] = G.arc[2][1] = 5;
    G.arc[2][3] = G.arc[3][2] = 5;
    G.arc[1][4] = G.arc[4][1] = 3;
    G.arc[2][4] = G.arc[4][2] = 6;
    G.arc[2][5] = G.arc[5][2] = 4;
    G.arc[3][5] = G.arc[5][3] = 2;
    G.arc[4][5] = G.arc[5][4] = 6;
    Graph_Show(G);
    Dijkstra(G, 0);
    return 0;
}

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

typedef char VertexType; // 顶点类型
typedef int EdgeType; // 边上的权值
#define MAXVEX 100 // 最大顶点数
#define INF 65535 // 如果两个顶点之间不可达，用无穷表示距离
#define DIRECTED true // 是否为有向图

#define V 3 // 定义图中结点的个数

typedef struct {
    VertexType vexs[MAXVEX]; // 顶点表
    EdgeType arc[MAXVEX][MAXVEX]; // 邻接矩阵，可看做边表
    int vexNum, edgeNum; // 图中当前的顶点数和边数
} MGraph;

// 创建邻接矩阵
int Graph_Create (MGraph &G) {
    int vi, vj, weight;
    // 输入顶点数和边数
    printf("请输入顶点数：");
    scanf("%d", &G.vexNum);
    printf("请输入边数：");
    scanf("%d", &G.edgeNum);

    for (int i = 0; i < G.vexNum; i++) { // 为每个顶点初始化信息
        printf("请输入第 %d 个的顶点名称: ", i + 1);
        scanf(" %c", &G.vexs[i]);
    }
    for (int i = 0; i < G.vexNum; i++) { // 初始化顶点之间的权值 默认为无穷
        for (int j = 0; j < G.vexNum; j++) {
            G.arc[i][j] = INF;
        }
    }

    printf("下标为 -1 -1 则退出创建边\n");
    for(int i = 0; i < G.edgeNum; i++){ // 根据边的条数，为每一条边赋值
        printf("请输入要创建边的下标 v1 v2 ");
        scanf("%d %d", &vi, &vj);
        if (vi == -1 && vj == -1) break;
        printf("请输入边为[%d][%d]的权值 weight = ", vi, vj);
        scanf("%d", &weight);
        G.arc[vi][vj] = weight;
        // 在无向网中满足图对称性，即Vi-Vj 和Vj-Vi的距离相等，实际就是一条路径
        if (!DIRECTED) {
            G.arc[vj][vi] = weight;
        }
    }
}

// 输出最短路径的函数
void printPath (int path[V][V], int start, int end) {
    // 如果路径前驱为-1，表示没有路径
    if (path[start][end] == -1) {
        printf("%d", start); // 直接输出起始结点
        return;
    }
    printPath(path, start, path[start][end]); // 递归输出路径
    printf(" -> %d", end); // 输出当前路径
}

// Flyod-Warshall 算法函数
void Floyd (MGraph G) {
    int dist[V][V]; // 最短路径的距离矩阵
    int path[V][V]; // 最短路径的前驱结点

    // 初始化 dist 和 path 矩阵
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = G.arc[i][j];
            if (i != j && G.arc[i][j] != INF) {
                path[i][j] = i; // 初始化路径前驱结点
            } else {
                path[i][j] = -1; // 无路径时设置为 -1
            }
        }
    }

    // 逐个结点尝试作为中间节点，更新最短路径
    for (int k = 0; k <  V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                // dist[i][k] + dist[k][j] 表示通过中间节点 k 从节点 i 到节点 j 的路径长度，即通过节点 k 的路径长度。
                // dist[i][j] 是节点 i 到节点 j 的当前已知的最短路径长度。
                // i != j 自己到自己的路径为无穷(或0)所以不需要更新
                // 如果通过中间节点 k 的路径更短，则更新最短路径
                if (i != j && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[k][j]; // 更新路径前驱信息
                }
            }
        }
    }

    // 输出最终的最短路径矩阵
    printf("最短路径矩阵：\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF) {
                printf("INF ");
            } else {
                printf("%d  ", dist[i][j]);
            }
        }
        printf("\n");
    }

    // 输出没对节点之前的最短路径信息
    printf("\n最短路径信息：\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (path[i][j] == -1) {
                printf("No Path from %d to %d", i, j); // 没有路径时的提示
            } else {
                printf("Path from %d to %d: ", i, j);
                printPath(path, i, j); // 调用输出路径的函数
            }
            printf("\n");
        }
    }
}

// 打印图
void Graph_Show (MGraph G) {
    // 打印顶点
    for (int i = 0; i < G.vexNum; i++)
        printf("%c", G.vexs[i]);
    printf("\n");
    // 打印邻接矩阵
    for(int i = 0; i < G.vexNum; i++){
        for(int j = 0; j < G.vexNum; j++){
            if(G.arc[i][j] == INF) printf("%6s", "∞");
            else printf("%6d", G.arc[i][j]);
        }
        printf("\n");
    }
}

int main () {
    // 注意 为了方便申请数组内存，在全局定义了顶点数常量
    MGraph G;
    // Graph_Create(G);
    G.vexNum = V;
    G.vexs[0] = '0';
    G.vexs[1] = '1';
    G.vexs[2] = '2';
    for (int i = 0; i < G.vexNum; i++) { // 初始化顶点之间的权值 默认为无穷
        for (int j = 0; j < G.vexNum; j++) {
            G.arc[i][j] = INF;
        }
    }
    G.edgeNum = 5;
    // 设置边
    G.arc[0][1] = 6;
    G.arc[0][2] = 13;
    G.arc[1][0] = 10;
    G.arc[1][2] = 4;
    G.arc[2][0] = 5;
    Graph_Show(G);
    Floyd(G);
    return 0;
}

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

#define MaxVertexNum 26
// 是否为有向图
#define DIRECTED true
typedef char VertexType;
typedef int ArcWeight;

// 边表结点
typedef struct ArcNode {
    int adjvex; // 该边指向的顶点下标
    ArcWeight weight; // 权值
    struct ArcNode *next; // 指向下一条边的指针
} ArcNode;

// 顶点表结点
typedef struct VNode{
    VertexType data; // 顶点信息
    ArcNode *first; // 指向该顶点的第一条边的指针
} VNode, AdjList[MaxVertexNum];

// 邻接表的图结构
typedef struct {
    AdjList adjList; // 邻接表
    int vexnum, arcnum; // 图的顶点数和边数
} ALGraph;

// =========拓扑排序辅助栈
typedef struct {
    int data[MaxVertexNum];
    int top;
} Stack;

// 初始化栈
void Stack_Init(Stack &stack) {
    stack.top = -1;
}

// 栈是否空
int Stack_IsEmpty(Stack stack) {
    return stack.top == -1;
}

// 是否满栈
int Stack_IsFull(Stack stack) {
    return stack.top == MaxVertexNum - 1;
}

// 入栈
void Stack_Push(Stack &stack, int value) {
    if (!Stack_IsFull(stack)) {
        stack.top++;
        stack.data[stack.top] = value;
    } else {
        printf("栈满，不能Push操作\n");
    }
}

// 出栈
int Stack_Pop(Stack &stack) {
    if (!Stack_IsEmpty(stack)) {
        int value = stack.data[stack.top];
        stack.top--;
        return value;
    } else {
        printf("栈为空，不能Pop操作\n");
        return -1; // Indicating an error value
    }
}

// 添加边到图
void ALGraph_AddEdge(ALGraph &graph, int source, int target, ArcWeight weight) {
    ArcNode* newNode = (ArcNode*)malloc(sizeof(ArcNode));
    // 通过头插法插入新边
    newNode->adjvex = target; // 该边指向的顶点位置
    newNode->weight = weight;
    newNode->next = graph.adjList[source].first;
    graph.adjList[source].first = newNode;

    // 如果是无向图，则还需要创建相反方向的边
    if (!DIRECTED) {
        ArcNode* reverseNode = (ArcNode*)malloc(sizeof(ArcNode));
        reverseNode->adjvex = source;
        reverseNode->weight = weight;
        // 相反方向，放入vj里 头插
        reverseNode->next = graph.adjList[target].first;
        graph.adjList[target].first = reverseNode;
    }
}

void ALGraph_Create (ALGraph &G) {
    // 对顶点表结点进行初始化
    for (int i = 0; i < MaxVertexNum; i++) {
        G.adjList[i].first = NULL;
    }
    printf("输入顶点 边个数（空格间隔）：");
    scanf("%d %d", &G.vexnum, &G.arcnum);
    // 建立顶点表
    for (int i = 0; i < G.vexnum; i++) {
        printf("请输入第%d个顶点的值：", i + 1);
        scanf(" %c", &G.adjList[i].data);
        G.adjList[i].first = NULL;
    }
    // 建立边表
    int vi, vj;
    ArcWeight weight;
    printf("下标为 -1 -1 则退出创建边\n");
    for (int i = 0; i < G.arcnum; i++) {
        // 代表两个顶点 vi 指向 vj 的边，注意vi vj是从0开始的
        printf("请输入要创建边的两个顶点 vi vj ");
        scanf("%d %d", &vi, &vj);
        if (vi == -1 && vj == -1) break;
        printf("请输入边为[%d->%d]的权值 weight = ", vi, vj);
        scanf("%d", &weight);
        ALGraph_AddEdge(G, vi, vj, weight);
    }
}

// 拓扑排序
bool TopologicalSort (ALGraph G) {
    int indegree[MaxVertexNum] = {0}; // 存放每个顶点的入度
    Stack S; // 初始化栈，存储入度为0的顶点
    Stack_Init(S);

    // 计算每个顶点的入度
    for (int i = 0; i < G.vexnum; i++) {
        ArcNode *p = G.adjList[i].first;
        while (p) {
            indegree[p->adjvex]++;
            p = p->next;
        }
    }

    // 将入度为 0 的顶点入栈
    for (int i = 0; i < G.vexnum; i++) {
        if (indegree[i] == 0) {
            Stack_Push(S, i);
        }
    }

    int count = 0; // 记录已经输出的顶点数
    while(!Stack_IsEmpty(S)) {
        int v = Stack_Pop(S); // 弹出栈顶入度为 0 的顶点
        printf("%c", G.adjList[v].data); // 输出顶点
        count++;
        ArcNode *p = G.adjList[v].first;
        while (p) {
            indegree[p->adjvex]--;
            if (indegree[p->adjvex] == 0) {
                Stack_Push(S, p->adjvex);
            }
            p = p->next;
        }

    }
    if (count != G.vexnum) {
        printf("\n图存在回路！\n");
        return false;
    }
    return true;
}

void ALGraph_Show (ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        printf("%c", G.adjList[i].data);
        ArcNode *p = G.adjList[i].first;
        while (p) {
            printf("->%c", G.adjList[p->adjvex].data);
            p = p->next;
        }
        printf("\n");
    }
}

int main () {
    printf("注意，当前创建图为有向图\n");
    ALGraph G;
    // ALGraph_Create(G);
    G.vexnum = 5;
    G.arcnum = 7;
    G.adjList[0].data = 'a';
    G.adjList[1].data = 'b';
    G.adjList[2].data = 'c';
    G.adjList[3].data = 'd';
    G.adjList[4].data = 'e';
    G.adjList[0].first = NULL;
    G.adjList[1].first = NULL;
    G.adjList[2].first = NULL;
    G.adjList[3].first = NULL;
    G.adjList[4].first = NULL;

    // 建立边表
    ALGraph_AddEdge(G, 0, 1, 0); // a->b
    ALGraph_AddEdge(G, 0, 3, 0); // a->d
    ALGraph_AddEdge(G, 1, 3, 0); // b->d
    ALGraph_AddEdge(G, 1, 2, 0); // b->c
    ALGraph_AddEdge(G, 3, 4, 0); // d->e
    ALGraph_AddEdge(G, 3, 2, 0); // d->c
    ALGraph_AddEdge(G, 2, 4, 0); // c->e

    ALGraph_Show(G);
    TopologicalSort(G);
    return 0;
}

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

typedef char VertexType; // 顶点类型
typedef int EdgeType; // 边上的权值
#define MAXVEX 100 // 最大顶点数
#define INF 65535 // 如果两个顶点之间不可达，用无穷表示距离
#define DIRECTED true // 是否为有向图

typedef struct {
  VertexType vexs[MAXVEX]; // 顶点表
  EdgeType arc[MAXVEX][MAXVEX]; // 邻接矩阵，可看做边表
  int vexNum, edgeNum; // 图中当前的顶点数和边数
} MGraph;

// 栈相关
// 定义栈中元素的最大个数为顶点个数
#define STACK_MAX_SIZE MAXVEX

typedef struct {
  int data[STACK_MAX_SIZE];
  int top;
} SqStack;

// 初始化栈
void Stack_Init(SqStack &S) {
  S.top = -1; // 初始化栈顶指针为-1，表示栈为空
}

// 判断栈是否为空
bool Stack_Empty(SqStack S) {
  return S.top == -1;
}

// 判断栈是否已满
bool Stack_Full(SqStack S) {
  return S.top == STACK_MAX_SIZE - 1;
}

// 新元素入栈
bool Stack_Push(SqStack &S, int x) {
  if (Stack_Full(S)) {
    printf("栈已满，无法入栈");
    return false;
  } else {
    S.data[++S.top] = x; // 将元素入栈，并更新栈顶指针
    return true;
  }
}

// 栈顶元素出栈，x为出栈的栈顶元素
bool Stack_Pop(SqStack &S, int &x) {
  if (Stack_Empty(S)) {
    printf("栈为空，无法出栈");
    return false;
  } else {
    x = S.data[S.top--]; // 将栈顶元素出栈，并更新栈顶指针
    return true;
  }
}

// 创建邻接矩阵
int Graph_Create (MGraph &G) {
  int vi, vj, weight;
  // 输入顶点数和边数
  printf("请输入顶点数：");
  scanf("%d", &G.vexNum);
  printf("请输入边数：");
  scanf("%d", &G.edgeNum);

  for (int i = 0; i < G.vexNum; i++) { // 为每个顶点初始化信息
    printf("请输入第 %d 个的顶点名称: ", i + 1);
    scanf(" %c", &G.vexs[i]);
  }
  for (int i = 0; i < G.vexNum; i++) { // 初始化顶点之间的权值 默认为无穷
    for (int j = 0; j < G.vexNum; j++) {
      G.arc[i][j] = INF;
    }
  }

  printf("下标为 -1 -1 则退出创建边\n");
  for(int i = 0; i < G.edgeNum; i++){ // 根据边的条数，为每一条边赋值
    printf("请输入要创建边的下标 v1 v2 ");
    scanf("%d %d", &vi, &vj);
    if (vi == -1 && vj == -1) break;
    printf("请输入边为[%d][%d]的权值 weight = ", vi, vj);
    scanf("%d", &weight);
    G.arc[vi][vj] = weight;
    // 在无向网中满足图对称性，即Vi-Vj 和Vj-Vi的距离相等，实际就是一条路径
    if (!DIRECTED) {
      G.arc[vj][vi] = weight;
    }
  }
  return 0;
}

// 打印图
void Graph_Show (MGraph G) {
  printf("顶点：");
  // 打印顶点
  for (int i = 0; i < G.vexNum; i++)
      printf("%c ", G.vexs[i]);
  printf("\n邻接矩阵：\n");
  // 打印邻接矩阵
  for(int i = 0; i < G.vexNum; i++){
    for(int j = 0; j < G.vexNum; j++){
      if(G.arc[i][j] == INF) printf("%6s", "∞");
      else printf("%6d", G.arc[i][j]);
    }
    printf("\n");
  }
}

// 求关键路径
bool Critical_Path (MGraph G) {
  // 1.先求拓扑排序
  SqStack S;
  Stack_Init(S);
  // 拓扑排序序列，存储的为顶点下标
  int topOrder[MAXVEX];
  // 当前拓扑排序中有多少个元素
  int topOrderLen = 0;

  // 每个顶点的入度数量
  int inDegree[MAXVEX];
  // 初始入度为 0
  for (int i = 0; i < MAXVEX; i++) inDegree[i] = 0;

  // 计算每个顶点的初始入度
  for (int i = 0; i < G.vexNum; i++) {
    for (int j = 0; j < G.vexNum; j++) {
      if (G.arc[i][j] != INF) {
        // 行为出度，列为入度
        // 这里使用 j 代表列
        inDegree[j] = inDegree[j] + 1;
      }
    }
  }

  // 将所有入度为0的顶点下标加入栈中
  for (int i = 0; i < G.vexNum; i++) {
    if (inDegree[i] == 0) {
      Stack_Push(S, i);
    }
  }

  // 开始拓扑排序 栈不为空则进入循环
  while (!Stack_Empty(S)) {
    // 弹出栈顶
    int u;
    Stack_Pop(S, u);

    // 将当前出栈的顶点下标加入拓扑排序序列中
    topOrder[topOrderLen] = u;
    topOrderLen++;

    // 遍历当前顶点的邻接顶点
    for (int i = 0; i < G.vexNum; i++) {
      if (G.arc[u][i] != INF) {
        // 减少邻接顶点的入度
        inDegree[i]--;

        // 如果邻接顶点的入度为0了，则将其下标加入栈
        // 注意：加入栈的始终为下标，不是顶点名称
        if (inDegree[i] == 0) {
          Stack_Push(S, i);
        }
      }
    }
  }

  printf("\n拓扑排序顶点下标序列：");
  for (int i = 0; i < topOrderLen; i++) {
    printf("%d ", topOrder[i]);
  }
  // 如果拓扑排序后的序列长度不等于顶点数，说明拓扑排序失败，则不进行关键路径求解
  if (topOrderLen != G.vexNum) return false;

  // 求关键路径

  // 2.求所有时间的最早发生时间 ve
  int ve[MAXVEX];
  int veMax = 0;
  // 初始 ve 为 0
  for (int i = 0; i < G.vexNum; i++) ve[i] = 0;

  for (int i = 0; i < topOrderLen; i++) {
    // 根据拓扑序列，依次计算顶点最早开始时间
    int u = topOrder[i];
    // 对于每个顶点，依次遍历其所有的出边（邻接顶点）
    for (int j = 0; j < G.vexNum; j++) {
      // 其他顶点到达 u 的权值
      int weight = G.arc[j][u];
      // 检查是否通过顶点 j 到达顶点 u 的路径能够获得更早的开始时间
      if (
        weight != INF
        &&
        (ve[j] + weight) > ve[u]
      ) {
        // 更新最早开始时间
        ve[u] = ve[j] + weight;
        // 记录最大值，给第 3 步求所有事件的最迟发生时间使用
        if (ve[u] > veMax) veMax = ve[u];
      }
    }
  }

  // 3.求所有事件的最迟发生时间 vl
  // 按逆拓扑排序序列，依次求各个顶点的 vl
  int vl[MAXVEX];
  // 初始化最迟发生时间
  for (int i = 0; i < G.vexNum; i++) {
    vl[i] = veMax;
  }
  for (int i = topOrderLen - 1; i >= 0; i--) {
    int u = topOrder[i];
    for (int j = 0; j < G.vexNum; j++) {
      // u 到其它顶点的权值
      int weight = G.arc[u][j];
      if (
        weight != INF
        &&
        vl[j] - weight < vl[u]
      ) {
        vl[u] = vl[j] - weight;
      }
    }
  }

  int e[MAXVEX * 2]; // 因为是记录边，所以最大值为顶点 * 2
  int l[MAXVEX * 2];
  int d[MAXVEX * 2];
  int edgeLen = 0;
  printf("\n关键路径：");
  for (int i = 0; i < G.vexNum; i++) {
    for (int j = 0; j < G.vexNum; j++) {
      int weight = G.arc[i][j];
      // 边存在
      if (weight != INF) {
        // 4.求所有活动的最早发生时间(e)
        // 边活动最早发生时间等于其起点顶点的 ve
        e[edgeLen] = ve[i];

        // 5.求所有活动的最迟发生时间(l)
        // 边活动的最迟发生时间等于 其指向 顶点的 vl - 边权值
        l[edgeLen] = vl[j] - weight;

        // 6.求所有活动的时间余量(d)
        d[edgeLen] = l[edgeLen] - e[edgeLen];

        // 7.余量 d 为 0 的即关键边
        if (d[edgeLen] == 0) {
          printf("%d -> %d，", i, j);
        }
        edgeLen++;
      }
    }
  }

  printf("\n所有事件的最早发生时间(ve)：");
  for (int i = 0; i < G.vexNum; i++) {
    printf("%d ", ve[i]);
  }

  printf("\n所有事件的最迟发生时间(vl)：");
  for (int i = 0; i < G.vexNum; i++) {
    printf("%d ", vl[i]);
  }

  printf("\n所有活动的最早发生时间(e)：");
  for (int i = 0; i < edgeLen; i++) {
    printf("%d ", e[i]);
  }

  printf("\n所有活动的最迟发生时间(l)：");
  for (int i = 0; i < edgeLen; i++) {
    printf("%d ", l[i]);
  }

  printf("\n求所有活动的时间余量  (d)：");
  for (int i = 0; i < edgeLen; i++) {
    printf("%d ", d[i]);
  }

  // 关键路径即为 活动时间余量 d 为 0 的边
  return true;
}

int main () {
  MGraph G;
  // Graph_Create(G);
  G.vexs[0] = '1';
  G.vexs[1] = '2';
  G.vexs[2] = '3';
  G.vexs[3] = '4';
  G.vexs[4] = '5';
  G.vexs[5] = '6';
  G.vexNum = 6;

  // 初始化所有边为 无穷
  for (int i = 0; i < G.vexNum; i++) {
      for (int j = 0; j < G.vexNum; j++) {
      G.arc[i][j] = INF;
      }
  }
  G.arc[0][1] = 3;
  G.arc[0][2] = 2;
  G.arc[1][3] = 2;
  G.arc[1][4] = 3;
  G.arc[2][3] = 4;
  G.arc[2][5] = 3;
  G.arc[3][5] = 2;
  G.arc[4][5] = 1;
  G.edgeNum = 8;
  Graph_Show(G);

  // 求关键路径
  Critical_Path(G);
  return 0;
}