MGraph* create_Mgraph() /* 以邻接矩阵作为图的存储结构建立图 / { char inchar[6], enchar[6], vex, fvex, lvex; int weight; MGraph G; ArcType* arc; G = (MGraph*)malloc(sizeof(MGraph)); G = Init_MGraph(); printf("图的初始化已经完成!!\n\n"); while (1) { printf("请输入图的顶点，?表示结束：\n"); scanf("%s", inchar); vex = inchar[0]; if (vex == '?') break; else AddVertex(G, vex); } arc = (ArcType*)malloc(sizeof(ArcType)); if (G->kind == DG || G->kind == AG) { printf("\n请以(顶点,顶点)的形式输入图的边(或弧)，第一个顶点是?表示结束：\n"); while (1) { scanf("%s", inchar); /* 输入第一个顶点，?结束 / fvex = inchar[0]; if (fvex == '?') break; else { scanf("%s", enchar); lvex = enchar[0]; / 输入第二个顶点 / arc->vex1 = fvex; arc->vex2 = lvex; arc->ArcVal = 1; AddArc(G, arc); printf("请继续输入下一条边(或弧)!!\n"); } } } else { printf("\n请以(顶点,顶点,权值)的形式输入图的边(或弧)，第一个顶点是?表示结束：\n"); while (1) { scanf("%s", inchar); fvex = inchar[0]; / 输入第一个顶点，?结束 / if (fvex == '?') break; else { scanf("%s", enchar); / 输入第二个顶点 / getchar(); / 取消回车键 / scanf("%d", &weight); / 输入权值 */ lvex = enchar[0]; arc->vex1 = fvex; arc->vex2 = lvex; arc->ArcVal = weight; AddArc(G, arc); printf("请继续输入下一条边(或弧)!!\n"); } } } return(G); }的时间复杂度

这段代码主要是用来创建图的邻接矩阵表示的存储结构，并且读入图的顶点和边（或弧）。其中，图的初始化是常数时间复杂度，而后面的 while 循环是 O(E) 的时间复杂度，其中 E 表示边（或弧）的数量。因此，该函数的时间复杂度为 O(E)。需要注意的是，这里的 E 是输入的边（或弧）的数量，而不是图的实际边（或弧）的数量，因为输入的边（或弧）可能会包含重复的边（或弧）。

相关问题

typedef enum GraphKind{DG,DN,UDG,UDN}; //{有向图,有向网,无向图,无向网} typedef char VertexType; typedef struct{ int adj; //顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；对带权图，则为权值 int *info; //该弧相关信息的指针 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{ //图的结构 VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs; //邻接矩阵(二维数组) int vexnum,arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }MGraph;根据这个结构体写拓扑排序和关键路径函数

好的，下面是拓扑排序和关键路径函数的代码实现：

拓扑排序函数：

void TopologicalSort(MGraph G, int *etv, int *etl){
    int i, j, k, top = 0;
    int stack[MAX_VERTEX_NUM], indegree[MAX_VERTEX_NUM];

    for(i = 0; i < G.vexnum; i++){      //初始化入度数组
        indegree[i] = 0;
    }

    for(i = 0; i < G.vexnum; i++){      //统计每个顶点的入度
        for(j = 0; j < G.vexnum; j++){
            if(G.arcs[j][i].adj != 0){
                indegree[i]++;
            }
        }
    }

    for(i = 0; i < G.vexnum; i++){      //入度为0的顶点入栈
        if(indegree[i] == 0){
            stack[++top] = i;
        }
    }

    for(i = 0; i < G.vexnum; i++){      //初始化事件最早发生时间
        etv[i] = 0;
    }

    while(top != 0){                    //拓扑排序
        j = stack[top--];
        for(k = 0; k < G.vexnum; k++){
            if(G.arcs[j][k].adj != 0){
                if(--indegree[k] == 0){
                    stack[++top] = k;
                }
                if(etv[j] + G.arcs[j][k].adj > etv[k]){
                    etv[k] = etv[j] + G.arcs[j][k].adj;
                }
            }
        }
    }

    for(i = 0; i < G.vexnum; i++){      //初始化事件最晚发生时间
        etl[i] = etv[G.vexnum - 1];
    }

    while(top != 0){                    //求事件最晚发生时间
        j = stack[top--];
        for(k = 0; k < G.vexnum; k++){
            if(G.arcs[j][k].adj != 0){
                if(etl[k] - G.arcs[j][k].adj < etl[j]){
                    etl[j] = etl[k] - G.arcs[j][k].adj;
                }
            }
        }
    }
}

关键路径函数：

void CriticalPath(MGraph G){
    int i, j, k, etv[MAX_VERTEX_NUM], etl[MAX_VERTEX_NUM], ltv[MAX_VERTEX_NUM], lte[MAX_VERTEX_NUM];
    TopologicalSort(G, etv, etl);

    printf("etv: ");
    for(i = 0; i < G.vexnum; i++){
        printf("%d ", etv[i]);
    }
    printf("\n");

    printf("etl: ");
    for(i = 0; i < G.vexnum; i++){
        printf("%d ", etl[i]);
    }
    printf("\n");

    for(i = 0; i < G.vexnum; i++){      //求ltv和lte
        ltv[i] = etl[G.vexnum - 1];
    }

    for(i = G.vexnum - 2; i >= 0; i--){
        j = etv[i];
        for(k = 0; k < G.vexnum; k++){
            if(G.arcs[i][k].adj != 0){
                if(ltv[k] - G.arcs[i][k].adj < j){
                    j = ltv[k] - G.arcs[i][k].adj;
                }
            }
        }
        ltv[i] = j;
    }

    printf("ltv: ");
    for(i = 0; i < G.vexnum; i++){
        printf("%d ", ltv[i]);
    }
    printf("\n");

    for(i = 0; i < G.vexnum; i++){
        lte[i] = etv[i];
    }

    for(i = 0; i < G.vexnum; i++){      //求关键路径
        for(j = 0; j < G.vexnum; j++){
            if(G.arcs[i][j].adj != 0){
                if(lte[i] + G.arcs[i][j].adj == ltv[j]){
                    printf("<%c, %c> length: %d, ", G.vexs[i], G.vexs[j], G.arcs[i][j].adj);
                }
            }
        }
    }
}

以上是根据您提供的结构体实现的拓扑排序和关键路径函数，希望可以帮助您。如果您有任何问题，可以随时问我。

C语言邻接矩阵有向带权图并实现输出、计算各个顶点的入度功能

好的，以下是C语言实现邻接矩阵有向带权图的代码，包括输出、计算各个顶点的入度功能：

#include <stdio.h>

#define MAX_VERTEX_NUM 100 // 最大顶点数量
#define INFINITY 65535 // 无穷大值

typedef struct {
    char vertex[MAX_VERTEX_NUM]; // 顶点信息
    int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vertex_num; // 顶点数量
    int arc_num; // 弧（边）数量
} MGraph;

void CreateGraph(MGraph *G) {
    int i, j;
    printf("请输入顶点数量和弧（边）数量：\n");
    scanf("%d %d", &G->vertex_num, &G->arc_num);
    printf("请输入顶点信息：\n");
    for (i = 0; i < G->vertex_num; i++) {
        scanf("%s", &G->vertex[i]);
    }
    // 初始化邻接矩阵
    for (i = 0; i < G->vertex_num; i++) {
        for (j = 0; j < G->vertex_num; j++) {
            G->arc[i][j] = INFINITY;
        }
    }
    // 输入弧（边）信息
    for (i = 0; i < G->arc_num; i++) {
        int start, end, weight;
        printf("请输入第%d条弧（边）的起点、终点和权值：\n", i + 1);
        scanf("%d %d %d", &start, &end, &weight);
        G->arc[start][end] = weight;
    }
}

void PrintGraph(MGraph G) {
    int i, j;
    printf("顶点信息：\n");
    for (i = 0; i < G.vertex_num; i++) {
        printf("%c ", G.vertex[i]);
    }
    printf("\n邻接矩阵：\n");
    for (i = 0; i < G.vertex_num; i++) {
        for (j = 0; j < G.vertex_num; j++) {
            if (G.arc[i][j] == INFINITY) {
                printf("∞ ");
            } else {
                printf("%d ", G.arc[i][j]);
            }
        }
        printf("\n");
    }
}

void CalcInDegree(MGraph G, int *indegree) {
    int i, j;
    for (i = 0; i < G.vertex_num; i++) {
        for (j = 0; j < G.vertex_num; j++) {
            if (G.arc[i][j] != INFINITY) {
                indegree[j]++;
            }
        }
    }
}

int main() {
    MGraph G;
    CreateGraph(&G);
    PrintGraph(G);
    int indegree[MAX_VERTEX_NUM] = {0};
    CalcInDegree(G, indegree);
    printf("各个顶点的入度：\n");
    int i;
    for (i = 0; i < G.vertex_num; i++) {
        printf("%c: %d\n", G.vertex[i], indegree[i]);
    }
    return 0;
}

在主函数中，先调用CreateGraph函数创建邻接矩阵有向带权图，然后调用PrintGraph函数输出图的信息，最后调用CalcInDegree函数计算各个顶点的入度并输出。