下面是一個用C語言實現拓撲排序的示例代碼:
#include <stdio.h>
#include <stdbool.h>
#define MAXVERTICES 100
struct Graph {
int vertices;
int edges;
int adjacencyMatrix[MAXVERTICES][MAXVERTICES];
};
void initializeGraph(struct Graph* graph, int vertices) {
graph->vertices = vertices;
graph->edges = 0;
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
graph->adjacencyMatrix[i][j] = 0;
}
}
}
void addEdge(struct Graph* graph, int startVertex, int endVertex) {
graph->adjacencyMatrix[startVertex][endVertex] = 1;
graph->edges++;
}
void topologicalSortUtil(struct Graph* graph, int vertex, bool visited[], int stack[], int* stackIndex) {
visited[vertex] = true;
for (int i = 0; i < graph->vertices; i++) {
if (graph->adjacencyMatrix[vertex][i] == 1 && !visited[i]) {
topologicalSortUtil(graph, i, visited, stack, stackIndex);
}
}
stack[(*stackIndex)++] = vertex;
}
void topologicalSort(struct Graph* graph) {
bool visited[MAXVERTICES] = {false};
int stack[MAXVERTICES];
int stackIndex = 0;
for (int i = 0; i < graph->vertices; i++) {
if (!visited[i]) {
topologicalSortUtil(graph, i, visited, stack, &stackIndex);
}
}
printf("Topological Sort: ");
while (stackIndex > 0) {
printf("%d ", stack[--stackIndex]);
}
printf("\n");
}
int main() {
struct Graph graph;
int vertices, edges, startVertex, endVertex;
printf("Enter the number of vertices in the graph: ");
scanf("%d", &vertices);
initializeGraph(&graph, vertices);
printf("Enter the number of edges in the graph: ");
scanf("%d", &edges);
for (int i = 0; i < edges; i++) {
printf("Enter the start and end vertex of edge %d: ", i + 1);
scanf("%d %d", &startVertex, &endVertex);
addEdge(&graph, startVertex, endVertex);
}
topologicalSort(&graph);
return 0;
}
這個代碼中,首先定義了一個結構體Graph
來表示圖,其中vertices
表示頂點的個數,edges
表示邊的個數,adjacencyMatrix
表示鄰接矩陣。
然后定義了幾個函數來操作圖,包括initializeGraph
用于初始化圖,addEdge
用于添加邊,topologicalSortUtil
用于遞歸實現拓撲排序,topologicalSort
用于調用topologicalSortUtil
進行拓撲排序。
在main
函數中,首先獲取用戶輸入的頂點個數和邊的個數,然后通過addEdge
函數添加邊,最后調用topologicalSort
函數進行拓撲排序。
注意:該示例代碼中使用鄰接矩陣來表示圖,適用于邊數較少的情況。如果邊數較多,推薦使用鄰接表來表示圖。