int **edges; int *edgeColSize; int *visited; bool vaild; void dfs(int n) { //对课程标进行遍历标记 visited[n]=1; for(int i=0;i<edgeColSize[n];++i) { if(visited[edges[n][i]]==0) { dfs(edges[n][i]); if(!vaild) return; } else if(visited[edges[n][i]]==1) { vaild=false; return; } } //遍历完中止 visited[n]=2; } bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize){ //初始化用edge[][]接受需要的数组 vaild=true; edges=(int **)malloc(sizeof(int *)*numCourses); edgeColSize=(int *)malloc(sizeof(int)*numCourses); //滞空 for(int i=0;i<numCourses;++i) edges[i]=(int *)malloc(0); memset(edgeColSize,0,sizeof(int)*numCourses); //对先修课程跟主课程进行设计 for(int i=0;i<prerequisites;++i) { //将辅修跟主修标记 int a=prerequisites[i][0]; int b=prerequisites[i][1]; edgeColSize[a]++;//更新入度 edges[a]=(int *)realloc(edges[a],sizeof(int)*edgeColSize[a]); //除非是大于0的合理要求否则不申请 edges[a][edgeColSize[a]-1]=b; } //dfs进行统计 for(int i=0;i<numCourses;++i) if(!vaild) dfs(i); //释放空间 for(int i=0;i<numCourses;++i) free(edges[i]); free(edges); free(edgeColSize); free(visited); return vaild; }

这段代码是关于判断课程安排是否合理的，其中 canFinish 函数用于判断在给定的课程数量和先决条件下是否能够完成所有课程。具体实现是使用 DFS 对每个课程进行遍历，如果出现环则说明课程安排不合理。其中，edges 数组用于存储每个课程的依赖关系，visited 数组用于标记每个课程的遍历状态，vaild 变量用于标记课程安排是否合理。该代码的时间复杂度为 O(n+m)，其中 n 为课程数量，m 为先决条件数量。

相关问题

优化这段代码 #include <stdio.h> #include <stdlib.h> #include <conio.h> #define MAX 20 typedef int VexType; typedef VexType Mgraph[MAX][MAX]; /* Mgraph是二维数组类型标识符 */ /* 函数原形声明 */ void creat_mg(Mgraph G); void out_mg(Mgraph G); Mgraph G1; /* G1是邻接矩阵的二维数组名 */ int n,e,v0; /* 主函数 */ int main() { creat_mg(G1); out_mg(G1); return 0; }/* main */ /* 建立邻接矩阵 */ void creat_mg(Mgraph G) { int i, j, k; printf("\n n,e=?"); scanf("%d%d", &n, &e); /* 输入顶点数n，边数e */ for(i=1; i<=n;i++) for(j=1;j<=n;j++) G[i][j]=0; /* 如果是网，G[i][j]=0改为G[i][j]=32767（无穷）*/ for(k=1;k<=e;k++) /* 组织边数的循环 */ { printf("\n vi,vj=?"); scanf("%d%d", &i, &j); /* 输入一条边的两个顶点编号i,j */ G[i][j]=1; G[j][i]=1; /* 无向图的邻接矩阵是对称矩阵 */ /* 如果是网，还要输入边的权值w，再让G[i][j]=w */ } } /* creat_mg */ /* 邻接矩阵简单输出，为了检查输入是否正确 */ void out_mg(Mgraph G) { int i,j,k; char ch; for(i=1; i<=n;i++) /* 矩阵原样输出 */ { printf("\n "); for(j=1;j<=n;j++) printf("%5d",G[i][j]); } /* 输出所存在的边 */ for(i=1; i<=n;i++) for(j=1;j<=n;j++) if(G[i][j]==1) printf("\n 存在边< %d,%d >", i, j); printf("\n\n 打回车键，继续。"); ch=getch(); } /* out_mg */

以下是对代码的优化建议：

1. 将输入顶点数和边数的代码抽象成一个函数，以提高代码的可重用性和可维护性。

2. 将邻接矩阵的初始化和边的输入合并在一起，以减少循环次数，提高代码效率。

3. 对于无向图的邻接矩阵，只需要输入每条边的一个方向即可，另一个方向可以直接赋值，避免重复输入。

下面是代码的优化版本：

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

#define MAX 20

typedef int VexType;
typedef VexType Mgraph[MAX][MAX];

void input_vertices_and_edges(int *n, int *e);
void create_mg(Mgraph G, int n, int e);
void output_mg(Mgraph G, int n);

int main()
{
    Mgraph G1;
    int n, e;

    input_vertices_and_edges(&n, &e);
    create_mg(G1, n, e);
    output_mg(G1, n);

    return 0;
}

/* 输入顶点数n和边数e */
void input_vertices_and_edges(int *n, int *e)
{
    printf("\n  n,e=?");
    scanf("%d%d", n, e);
}

/* 建立邻接矩阵 */
void create_mg(Mgraph G, int n, int e)
{
    int i, j, k, vi, vj;

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            G[i][j] = 0;
        }
    }

    for (k = 1; k <= e; k++)
    {
        printf("\n  vi,vj=?");
        scanf("%d%d", &vi, &vj);

        G[vi][vj] = 1;
        G[vj][vi] = 1;
    }
}

/* 邻接矩阵简单输出 */
void output_mg(Mgraph G, int n)
{
    int i, j;
    char ch;

    for (i = 1; i <= n; i++)
    {
        printf("\n ");
        for (j = 1; j <= n; j++)
        {
            printf("%5d", G[i][j]);
        }
    }

    for (i = 1; i <= n; i++)
    {
        for (j = i + 1; j <= n; j++)
        {
            if (G[i][j] == 1)
            {
                printf("\n 存在边< %d,%d >", i, j);
            }
        }
    }

    printf("\n\n   打回车键，继续。");
    ch = getch();
}

typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* Number of vertices */ int Ne; /* Number of edges */ AdjList List; /* adjacency matrix */ }; typedef PtrToGNode Graph; void Unweighted( Graph G, Queue Q, int dist[], int path[], Vertex S ) { Vertex V, W; NodePtr ptr; dist[S] = 0; Enqueue(S, Q); while ( !IsEmpty(Q) ) { V = Dequeue( Q ); for ( ptr=G->List[V].FirstEdge; ptr; ptr=ptr->Next) { W = ptr->AdjV; if ( dist[W] == INFINITY ) { ; path[W] = V; ; } } } }

这段代码定义了一个无权图（图中所有边的权值均为1），并实现了基于BFS的无权图最短路径算法。具体来说，代码中定义了一个`Graph`结构体，包含图的顶点数、边数和邻接表等信息。邻接表`AdjList`是一个数组，每个元素是一个链表，表示从该顶点发出的所有边。

函数`Unweighted`用于计算从源点`S`到图中所有其他顶点的最短路径。该函数的参数包括一个队列`Q`，用于BFS遍历图；一个一维数组`dist[]`，记录源点`S`到每个顶点的最短距离；一个一维数组`path[]`，记录从源点`S`到每个顶点的最短路径上的前驱顶点；以及源点`S`的编号。

在函数的开头，将源点`S`的距离设置为0，并将其入队。然后进入循环，只要队列不为空，就从队列中取出一个顶点`V`，遍历其所有邻接顶点，并更新其距离和路径信息。具体来说，对于`V`的每个邻接点`W`，如果`W`的距离尚未被计算，则将其距离设置为`V`到`W`的距离加1，将其前驱顶点设置为`V`，并将`W`入队，表示需要继续遍历从`W`出发的邻接点。

值得注意的是，代码中使用了一个宏定义`INFINITY`表示距离无穷大，用于判断某个顶点的距离是否已经被计算过。另外，代码中使用了一个链表结构体`Node`表示邻接表中的一条边，包括该边的邻接顶点`AdjV`和下一条边的指针`Next`。