拓扑排序邻接矩阵c语言算法

拓扑排序是一种针对有向无环图(DAG)的排序算法，用于确定图中节点之间的依赖关系。下面是一个基于邻接矩阵的C语言实现拓扑排序的算法：

1. 首先，我们需要定义一个栈数据结构来保存拓扑排序的结果。栈的大小可以根据需要进行调整。

2. 接下来，我们需要创建一个邻接矩阵来表示有向图，其中矩阵的大小为图中节点的数量。

3. 我们可以使用深度优先搜索(DFS)来实现拓扑排序。具体步骤如下：

a. 遍历图中的每个节点，对于未被访问的节点，递归调用深度优先搜索函数。

b. 在深度优先搜索函数中，首先将当前节点标记为已访问，并递归访问当前节点的邻居节点。

c. 当前节点的所有邻居节点都被访问过后，将当前节点入栈。

4. 最后，输出栈中的元素，即为拓扑排序的结果。

这是一个基本的拓扑排序邻接矩阵的C语言算法。通过使用邻接矩阵来表示图的结构，通过深度优先搜索来进行拓扑排序。希望这能帮助到你。

相关问题

求图的关键路径邻接矩阵C语言

求图的关键路径是一个常见的图算法问题，可以使用拓扑排序和关键路径算法来解决。下面是一个使用邻接矩阵表示图的C语言代码示例：

#include <stdio.h>
#include <stdbool.h>

#define MaxVertexNum 100

typedef struct {
    int numV; // 顶点数
    int numE; // 边数
    char nameV[MaxVertexNum]; // 顶点的名字
    int dis[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
} MG, *MGraph;

// 拓扑排序
bool TopologicalSort(MGraph G, int indegree[], int ve[]) {
    int count = 0; // 计数，记录已经输出的顶点数
    int queue[MaxVertexNum]; // 用于存储入度为0的顶点
    int front = 0, rear = 0; // 队列的头尾指针

    // 初始化入度数组和队列
    for (int i = 0; i < G->numV; i++) {
        indegree[i] = 0;
    }
    for (int i = 0; i < G->numV; i++) {
        for (int j = 0; j < G->numV; j++) {
            if (G->dis[i][j] != 0) {
                indegree[j]++;
            }
        }
    }
    for (int i = 0; i < G->numV; i++) {
        if (indegree[i] == 0) {
            queue[rear++] = i;        }
    }

    // 拓扑排序
    while (front != rear) {
        int v = queue[front++]; // 取出一个入度为0的顶点
        count++; // 计数
        for (int w = 0; w < G->numV; w++) {
            if (G->dis[v][w] != 0) {
                if (--indegree[w] == 0) {
                    queue[rear++] = w; // 入度为0的顶点入队列
                }
                if (ve[v] + G->dis[v][w] > ve[w]) {
                    ve[w] = ve[v] + G->dis[v][w]; // 更新最早开始时间
                }
            }
        }
    }

    if (count < G->numV) {
        return false; // 有回路，拓扑排序失败
    } else {
        return true; // 拓扑排序成功
    }
}

// 关键路径算法
void CriticalPath(MGraph G) {
    int indegree[MaxVertexNum]; // 入度数组
    int ve[MaxVertexNum]; // 最早开始时间
    int vl[MaxVertexNum]; // 最晚开始时间
    int e[MaxVertexNum][MaxVertexNum]; // 事件最早发生时间
    int l[MaxVertexNum][MaxVertexNum]; // 事件最晚发生时间

    // 初始化最早开始时间和最晚开始时间
    for (int i = 0; i < G->numV; i++) {
        ve[i] = 0;
        vl[i] = ve[G->numV - 1];
    }

    // 求最早开始时间
    TopologicalSort(G, indegree, ve);

    // 求最晚开始时间
    for (int i = G->numV - 1; i >= 0; i--) {
        int v = G->numV - 1;
        for (int w = 0; w < G->numV; w++) {
            if (G->dis[v][w] != 0) {
                if (vl[w] - G->dis[v][w] < vl[v]) {
                    vl[v] = vl[w] - G->dis[v][w]; // 更新最晚开始时间
                }
            }
        }
    }

    // 求事件最早发生时间和最晚发生时间
    for (int i = 0; i < G->numV; i++) {
        for (int j = 0; j < G->numV; j++) {
            e[i][j] = ve[i];
            l[i][j] = vl[j] - G->dis[i][j];
        }
    }

    // 输出关键路径
    printf("Critical Path:\n");
    for (int i = 0; i < G->numV; i++) {
        for (int j = 0; j < G->numV; j++) {
            if (G->dis[i][j] != 0 && e[i][j] == l[i][j]) {
                printf("%c -> %c\n", G->nameV[i], G->nameV[j]);
            }
        }
    }
}

int main() {
    MG G;
    G.numV = 6;
    G.numE = 9;
    strcpy(G.nameV, "ABCDEF");
    memset(G.dis, 0, sizeof(G.dis));
    G.dis[0][1] = 3;
    G.dis[0][2] = 2;
    G.dis[1][3] = 2;
    G.dis[1][4] = 3;
    G.dis[2][3] = 1;
    G.dis[2][5] = 3;
    G.dis[3][4] = 4;
    G.dis[3][5] = 2;
    G.dis[4][5] = 1;

    CriticalPath(&G);

    return 0;
}

这段代码实现了求图的关键路径，其中使用了邻接矩阵存储图的结构。首先进行拓扑排序，然后根据拓扑排序的结果计算最早开始时间和最晚开始时间，最后输出关键路径。

使用邻接矩阵用c语言实现AOE网的拓扑算法，输出拓扑序列。

好的，我可以帮你解决这个问题。

首先，让我们来了解一下AOE网和拓扑排序算法。

AOE网（Activity On Edge Network）是一种用于描述工程项目中各项活动以及它们之间的依赖关系的网络模型。在AOE网中，节点表示活动，边表示活动之间的依赖关系，权值表示活动所需的时间。

拓扑排序算法可以用来确定AOE网中各个活动的执行顺序。它的基本思想是将AOE网中的节点按照拓扑序列的顺序进行排列，使得所有的依赖关系都被满足。具体实现方法有Kahn算法和DFS算法。

我们这里使用邻接矩阵来表示AOE网，其中矩阵中的元素表示边的权值。接下来是实现拓扑排序的C语言代码：

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

#define MAX_VERTEX_NUM 100

// 邻接矩阵表示法
typedef struct {
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
    int indegrees[MAX_VERTEX_NUM];             // 每个节点的入度
    int vertex_num;                             // 顶点数
} AOE_graph;

// 创建AOE网
void create_AOE_graph(AOE_graph *g) {
    int i, j, k, n, m, w;

    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &g->vertex_num, &m);

    // 初始化邻接矩阵和入度数组
    for (i = 0; i < g->vertex_num; i++) {
        for (j = 0; j < g->vertex_num; j++) {
            g->arcs[i][j] = 0;
        }
        g->indegrees[i] = 0;
    }

    // 输入边信息
    printf("请输入每条边的起点、终点和权值：\n");
    for (k = 0; k < m; k++) {
        scanf("%d%d%d", &i, &j, &w);
        g->arcs[i][j] = w;
        g->indegrees[j]++;
    }
}

// 拓扑排序
void topological_sort(AOE_graph *g) {
    int i, j, count;
    int queue[MAX_VERTEX_NUM];  // 存储入度为0的节点
    int front = 0, rear = 0;    // 队列的头和尾
    int v, w;

    // 将入度为0的节点加入队列
    for (i = 0; i < g->vertex_num; i++) {
        if (g->indegrees[i] == 0) {
            queue[rear++] = i;
        }
    }

    // 遍历队列中的节点
    while (front != rear) {
        v = queue[front++];
        printf("%d ", v);  // 输出拓扑序列
        count++;

        // 更新与v相邻的节点的入度
        for (w = 0; w < g->vertex_num; w++) {
            if (g->arcs[v][w] != 0) {
                g->indegrees[w]--;
                if (g->indegrees[w] == 0) {
                    queue[rear++] = w;
                }
            }
        }
    }

    if (count != g->vertex_num) {
        printf("该AOE网存在环路！\n");
    }
}

int main() {
    AOE_graph g;

    create_AOE_graph(&g);
    printf("AOE网的拓扑序列为：");
    topological_sort(&g);

    return 0;
}

以上就是使用邻接矩阵实现AOE网的拓扑排序的C语言代码。在运行程序时，首先需要输入顶点数和边数，然后输入每条边的起点、终点和权值。程序会输出拓扑序列。如果AOE网中存在环路，则会输出“该AOE网存在环路！”的提示信息。