图

1. 邻接矩阵存储

#define MAX_VERTEX_NUM 10   // 图中允许的最大顶点数

typedef int VertexType;     // 顶点的数据类型
typedef int ArcType;        // 弧（边）的数据类型

typedef struct MGraph {
    VertexType vex[MAX_VERTEX_NUM];     // 存储顶点的数组
    ArcType arcMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];      // 邻接矩阵，存储弧（边）之间的关系
    int vexNum;     // 图中的顶点数
    int arcNum;     // 图中的弧（边）数
    int kind;       // 图的类型（有向图DG、有向网DN、无向图UDG、无向网UDN）
} MGraph;

2. 邻接表存储

// 定义图中最大顶点数目
#define MAX_VERTEX_NUM 10

// 顶点的数据类型，这里定义为整数类型
typedef int VertexType;

// 弧（边）节点的结构体
typedef struct ArcNode {
    int adjVex;            // 该弧所指向的顶点在顶点数组中的下标
    struct ArcNode *nextArc; // 指向下一条弧的指针
} ArcNode;

// 顶点节点的结构体
typedef struct VNode {
    VertexType data;      // 顶点的数据
    ArcNode *firstArc;    // 指向该顶点第一条弧（边）的指针
} VNode, AdjList[MAX_VERTEX_NUM]; // 用于存储邻接表的数组类型，数组大小为MAX_VERTEX_NUM

// 邻接表图的结构体
typedef struct {
    AdjList vertices;     // 邻接表数组，存储图的所有顶点及其相关的弧（边）
    int vexNum;           // 图中的顶点数
    int arcNum;           // 图中的弧（边）数
    int kind;             // 图的类型
} ALGraph;

3. 使用邻接表存储方式建立无向图G

void createALGraph(ALGraph &G, VertexType vList[], int vListLength, VertexType arcList[][2], int arcListLength){    
    G.vexNum = vListLength;          // 设置图的顶点数为传入的顶点列表长度
    G.arcNum = 2 * arcListLength;    // 因为是无向图，每条边需要记录两次，所以边数是弧列表长度的两倍
    G.kind = 0;                      // 将图的类型设置为无向图

    // 初始化顶点列表
    for(int index = 1; index <= vListLength; index++){  // 从1开始遍历顶点列表（注意：C语言中通常从0开始）
        VertexType vertex = vList[index];               // 获取当前顶点
        G.vertices[vertex].data = vertex;               // 将顶点数据存储到图的顶点数组中
        G.vertices[vertex].firstArc = NULL;             // 初始化顶点的第一条弧（边）为空
    }

    // 构建边表
    for(int i = 0; i < arcListLength; i++){
        VertexType src = arcList[i][0];     // 获取边的起点
        VertexType dest = arcList[i][1];    // 获取边的终点

        // 为 src -> dest 创建新的弧节点
        ArcNode *pArcNode = (ArcNode *) malloc (sizeof(ArcNode));  // 分配内存给新的弧节点
        pArcNode->adjVex = dest;  // 设置弧节点的目标顶点为dest
        pArcNode->nextArc = G.vertices[src].firstArc;  // 将当前弧节点的nextArc指向src顶点的第一条弧
        G.vertices[src].firstArc = pArcNode;  // 将src顶点的firstArc指向新的弧节点

        // 为 dest -> src 创建新的弧节点（因为是无向图，需要反向添加）
        pArcNode = (ArcNode *) malloc (sizeof(ArcNode));  // 为新弧节点分配内存
        pArcNode->adjVex = src;  // 设置弧节点的目标顶点为src
        pArcNode->nextArc = G.vertices[dest].firstArc;  // 将当前弧节点的nextArc指向dest顶点的第一条弧
        G.vertices[dest].firstArc = pArcNode;  // 将dest顶点的firstArc指向新的弧节点
    }
}

4. 将邻接表表示的有向网转换成邻接数组表示

void convertAdjList2Matrix(ALGraph G, MGraph *mG) {
    // 初始化邻接矩阵的基本信息
    mG->vexNum = G.vexNum;  // 顶点数量
    mG->arcNum = G.arcNum;  // 边的数量
    mG->kind = G.kind;      // 图的种类

    // 初始化邻接矩阵，将所有权重初始化为无穷大（表示没有边）
    for(int i = 0; i < mG->vexNum; i++){
        for(int j = 0; j < mG->vexNum; j++){
            mG->arcMatrix[i][j] = INFINITY;  // 初始化为INFINITY表示无边
        }
    }

    // 将邻接表转换为邻接矩阵
    for(int i = 0; i < G.vexNum; i++){
        VertexType src = G.vertices[i].data;  // 获取当前顶点的编号
        mG->vex[i] = src;  // 将顶点编号存入邻接矩阵的顶点数组中

        ArcNode *pArcNode = G.vertices[i].firstArc;  // 获取顶点的第一条边
        while(pArcNode != NULL){
            int dest = pArcNode->adjVex;  // 获取边的目标顶点编号
            int weight = pArcNode->weight;  // 获取边的权重
            mG->arcMatrix[src][dest] = weight;  // 在邻接矩阵中设置对应的权重
            pArcNode = pArcNode->nextArc;  // 继续处理下一条边
        }
    }
}

5. 对有向图G进行DFS遍历

int visit[MAX_VERTEX_NUM] = {0}; // 标记数组，初始化为0，表示未访问

// 深度优先搜索（DFS）核心函数
void DFS(ALGraph G, int vertex){
    visit[vertex] = 1;           // 标记当前顶点为已访问
    printf("%d ", vertex);       // 打印当前顶点

    ArcNode *pArcNode = G.vertices[vertex].firstArc;  // 获取当前顶点的第一条边
    while(pArcNode != NULL){
        VertexType adjVex = pArcNode->adjVex;  // 获取邻接顶点
        if(visit[adjVex] == 0){                // 如果邻接顶点未被访问，递归访问
            DFS(G, adjVex);
        }
        pArcNode = pArcNode->nextArc;  // 移动到下一条边
    }
}

// 图的深度优先遍历函数
void DFSTraverse(ALGraph G){
    for(int i = 0; i < G.vexNum; i++){
        if(visit[i] == 0){         // 如果顶点未被访问，从该顶点开始DFS
            DFS(G, i);
        }
    }
}

6. 判断以邻接表方式存储的有向图G是否存在src到dest的路径

int isExistPath(ALGraph G, VertexType src, VertexType dest) {
    // 标记当前节点src已访问
    visit[src] = 1;

    // 如果当前节点src就是目标节点dest，直接返回1，表示找到路径
    if (src == dest) {
        return 1;
    }

    // 获取从当前节点src出发的所有边（邻接节点）
    ArcNode *pArcNode = G.vertices[src].firstArc;

    // 遍历所有邻接节点
    while (pArcNode != NULL) {
        VertexType adjVex = pArcNode->adjVex; // 获取当前邻接节点的编号

        // 如果该邻接节点尚未访问过
        if (visit[adjVex] == 0) {
            // 递归调用isExistPath判断是否存在从邻接节点adjVex到dest的路径
            if (isExistPath(G, adjVex, dest)) {
                return 1; // 如果找到路径，立即返回1
            }
        }

        // 移动到下一个邻接节点
        pArcNode = pArcNode->nextArc;
    }

    // 如果所有邻接节点都无法到达目标节点dest，返回0
    return 0;
}

7. 判断以邻接表为存储结构的有向图G是否存在环

int getRing(ALGraph G, VertexType v) {
    if (visit[v] == 1) {
        return 1; // 如果再次访问到这个顶点，说明存在环
    }

    visit[v] = 1; // 标记当前顶点为访问中
    ArcNode *pArcNode = G.vertices[v].firstArc; // 获取当前顶点的邻接表头节点

    while (pArcNode != NULL) {
        VertexType adjVex = pArcNode->adjVex;
        if (visit[adjVex] == 0) { // 仅对未访问的顶点进行递归调用
            if (getRing(G, adjVex)) {
                return 1; // 如果递归调用返回1，说明存在环
            }
        } else if (visit[adjVex] == 1) {
            return 1; // 如果访问到一个正在访问中的顶点，说明存在环
        }
        pArcNode = pArcNode->nextArc; // 继续检查下一个邻接节点
    }

    visit[v] = 2; // 当前顶点访问结束，标记为完全访问状态
    return 0; // 如果没有找到环，返回0
}

int isExistRing(ALGraph G) {
    for (int i = 0; i < G.vexNum; i++) {
        if (visit[i] == 0) { // 仅当顶点状态为0时才调用getRing
            if (getRing(G, i)) {
                return 1; // 如果检测到环，立即返回1
            }
        }
    }
    return 0; // 没有检测到环
}

8. 求出以邻接表存储的有向图中所有从顶点src到顶点dest的简单路径

void getPaths(ALGraph G, VertexType src, VertexType dest) {
    // 标记当前顶点为已访问
    visit[src] = 1;

    // 将当前顶点加入路径
    path[pathLength++] = src;

    // 如果当前顶点是目标顶点，打印路径
    if(src == dest) {
        printPath(path, pathLength);
    } else {
        // 遍历当前顶点的所有邻接顶点
        ArcNode *pArcNode = G.vertices[src].firstArc;
        while(pArcNode != NULL){
            VertexType adjVex = pArcNode->adjVex;
            // 如果邻接顶点未被访问，递归查找路径
            if(visit[adjVex] == 0){
                getPaths(G, adjVex, dest);
            }
            pArcNode = pArcNode->nextArc;
        }
    }

    // 递归返回前，取消当前顶点的访问状态
    visit[src] = 0;
    // 移除路径中的当前顶点
    pathLength--;
}

9. 设计算法求解以邻接表存储的有向图G中所有从顶点src到顶点dest长度为distance的路径

void findAllPathsOfLength(ALGraph G, VertexType src, VertexType dest, int distance){
    visit[src] = 1;           // 标记当前顶点已访问
    path[pathLength++] = src; // 将当前顶点添加到路径中

    // 如果当前剩余距离为1，并且当前顶点可以到达目标顶点，打印路径
    if(src == dest && distance == 1){
        printPath(path, pathLength);
    } else {
        // 遍历当前顶点的所有邻接顶点
        ArcNode *pArcNode = G.vertices[src].firstArc;
        while(pArcNode != NULL){
            VertexType adjVex = pArcNode->adjVex;
            // 如果邻接顶点未被访问，递归查找从邻接顶点开始的路径
            if(visit[adjVex] == 0){
                findAllPathsOfLength(G, adjVex, dest, distance - 1);
            }
            pArcNode = pArcNode->nextArc;
        }
    }

    visit[src] = 0;    // 回溯，标记当前顶点未被访问
    pathLength--;      // 从路径中移除当前顶点
}

10. 设计算法对有向无环图G进行拓扑排序

int visit[MAX_VERTEX_NUM] = {0};  // 访问标记数组，初始化为0，表示所有顶点都未被访问
int stack[MAX_VERTEX_NUM] = {0};  // 栈用于存储顶点的拓扑排序结果
int stackLength = 0;              // 栈的长度，用于跟踪栈中元素的数量

// 深度优先搜索(DFS)函数，用于递归地遍历图
void DFS(ALGraph G, VertexType v) {
    visit[v] = 1;  // 将当前顶点标记为已访问

    ArcNode *pArcNode = G.vertices[v].firstArc;  // 获取与当前顶点相连的第一个边节点
    while (pArcNode != NULL) {  // 遍历所有与当前顶点相连的边
        VertexType adjVex = pArcNode->adjVex;  // 获取邻接顶点的编号
        if (visit[adjVex] == 0) {  // 如果邻接顶点尚未被访问
            DFS(G, adjVex);  // 递归地对邻接顶点执行DFS
        }
        pArcNode = pArcNode->nextArc;  // 继续遍历下一条边
    }

    stack[stackLength++] = v;  // 将当前顶点压入栈中（拓扑排序结果的一部分）
}

// 拓扑排序函数，遍历所有顶点，并对每个未访问的顶点执行DFS
void topologicalSort(ALGraph G) {
    for (int i = 1; i < G.vexNum; i++) {  // 遍历图中的每个顶点，注意这里从1开始
        if (visit[i] == 0) {  // 如果顶点尚未被访问
            DFS(G, i);  // 执行DFS，开始深度优先搜索
        }
    }
}

11. 设计算法求解以邻接表存储的有向图G中顶点src到其余顶点的最短路径，并将最短路径打印输出

// 定义边节点结构体
typedef struct ArcNode {
    int adjVex;                  // 相邻顶点（边的目标顶点）
    struct ArcNode *nextArc;     // 指向下一个边节点的指针
} ArcNode;

// 定义顶点节点结构体
typedef struct VexNode {
    int data;            // 顶点数据（可以存储顶点编号）
    ArcNode *firstArc;   // 指向第一个边节点（邻接表）
} VexNode, VexList[MAX_VERTEX_NUM];

// 定义图结构体
typedef struct ALGraph {
    VexList vexs;        // 顶点节点数组（邻接表）
    int vexNum;          // 顶点数量
    int arcNum;          // 边的数量
    int kind;            // 图的种类（此处未使用）
} ALGraph;

// 定义 BFS 队列元素结构体
typedef struct QElemType {
    int v;          // 顶点
    int index;      // 指向此顶点的前一个顶点在队列中的索引
} QElemType;

int visited[MAX_VERTEX_NUM] = {0}; // 记录访问状态的数组

// 打印路径函数
void printPath(QElemType Q[], int index){
    int path[MAX_VERTEX_NUM] = {0};  // 存储路径的数组
    int pathLength = 0;              // 路径长度

    // 逆向回溯路径
    while(index != -1){
        path[pathLength++] = Q[index].v;
        index = Q[index].index;
    }

    // 正向打印路径
    for(int i = pathLength - 1; i >= 0; i--){
        printf("%d ", path[i]);
    }
    printf("\n");
}

// 广度优先搜索（BFS）函数
void BFS(ALGraph G, int src){
    QElemType Q[MAX_VERTEX_NUM] = {0}; // 队列数组
    int QLength = 0;                   // 队列长度

    QElemType e;
    e.v = src;                         // 设置源顶点
    e.index = -1;                      // 没有前驱顶点
    Q[QLength++] = e;                  // 将源顶点加入队列
    visited[src] = 1;                  // 标记源顶点为已访问

    int i = 0; // 队头索引
    while(i < QLength){
        int v = Q[i++].v;              // 取出队列头部的顶点

        ArcNode *pArcNode = G.vexs[v].firstArc;
        while(pArcNode != NULL){       // 遍历邻接顶点
            int w = pArcNode->adjVex;
            if(visited[w] == 0){       // 如果顶点未访问
                e.v = w;
                e.index = i - 1;       // 记录前驱顶点
                Q[QLength++] = e;      // 加入队列
                visited[w] = 1;        // 标记为已访问
            }
            pArcNode = pArcNode->nextArc;
        }
    }
    // 打印所有路径
    for(int i = QLength - 1; i > 0; i--){
        printPath(Q, i);
    }    
}