请用c语言实现并写出以下代码: 实现拓扑排序的Kahn算法、DFS算法

以下是用C语言实现拓扑排序的Kahn算法和DFS算法的示例代码：

1. 拓扑排序的Kahn算法：

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

#define MAX_SIZE 100

struct Node {
    int data;
    struct Node* next;
};

struct Graph {
    int numVertices;
    struct Node** adjLists;
    int* indegree;
};

struct Node* createNode(int data) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(struct Node*));
    graph->indegree = malloc(vertices * sizeof(int));

    int i;
    for (i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->indegree[i] = 0;
    }

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    graph->indegree[dest]++;
}

void topologicalSort(struct Graph* graph) {
    int* result = malloc(graph->numVertices * sizeof(int));
    int front = 0, rear = 0;

    int* indegree = graph->indegree;

    int i;
    for (i = 0; i < graph->numVertices; i++) {
        if (indegree[i] == 0) {
            result[rear++] = i;
        }
    }

    while (front != rear) {
        int currentVertex = result[front++];
        struct Node* temp = graph->adjLists[currentVertex];

        while (temp) {
            int adjVertex = temp->data;
            indegree[adjVertex]--;

            if (indegree[adjVertex] == 0) {
                result[rear++] = adjVertex;
            }

            temp = temp->next;
        }
    }

    if (rear != graph->numVertices) {
        printf("Graph contains a cycle!\n");
        return;
    }

    printf("Topological Sort:");
    for (i = 0; i < graph->numVertices; i++) {
        printf(" %d", result[i]);
    }
    printf("\n");
}

int main() {
    int vertices, edges;
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);
    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    struct Graph* graph = createGraph(vertices);

    int i, src, dest;
    for (i = 0; i < edges; i++) {
        printf("Enter edge %d (source destination): ", i+1);
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    topologicalSort(graph);

    return 0;
}

2. 拓扑排序的DFS算法：

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

#define MAX_SIZE 100

struct Node {
    int data;
    struct Node* next;
};

struct Graph {
    int numVertices;
    struct Node** adjLists;
    int* visited;
};

struct Node* createNode(int data) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(struct Node*));
    graph->visited = malloc(vertices * sizeof(int));

    int i;
    for (i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

void DFS(struct Graph* graph, int vertex, int* result, int* index) {
    struct Node* adjList = graph->adjLists[vertex];
    graph->visited[vertex] = 1;

    while (adjList) {
        int connectedVertex = adjList->data;
        if (!graph->visited[connectedVertex]) {
            DFS(graph, connectedVertex, result, index);
        }
        adjList = adjList->next;
    }

    result[(*index)++] = vertex;
}

void topologicalSort(struct Graph* graph) {
    int* result = malloc(graph->numVertices * sizeof(int));
    int index = 0;

    int i;
    for (i = 0; i < graph->numVertices; i++) {
        if (!graph->visited[i]) {
            DFS(graph, i, result, &index);
        }
    }

    printf("Topological Sort:");
    for (i = graph->numVertices - 1; i >= 0; i--) {
        printf(" %d", result[i]);
    }
    printf("\n");
}

int main() {
    int vertices, edges;
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);
    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    struct Graph* graph = createGraph(vertices);

    int i, src, dest;
    for (i = 0; i < edges; i++) {
        printf("Enter edge %d (source destination): ", i+1);
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    topologicalSort(graph);

    return 0;
}

这些代码可以帮助您实现拓扑排序的Kahn算法和DFS算法。您可以根据需要进行修改和调整。