c语言数据结构--------拓扑排序和逆拓扑排序(Kahn算法和DFS算法实现)

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>//使用卡恩算法(Kahn)和深度优先算法(DFS)实现//拓扑排序和逆拓扑排序//拓扑排序和逆拓扑排序顶点顺序相反//图，邻接矩阵存储
#define MaxVertexNum 100  //最大顶点数typedef struct {int vex[MaxVertexNum]; //顶点表int edge[MaxVertexNum][MaxVertexNum]; //边表int vernum, arcnum; //记录当前图的顶点数量和边数
} MGraph;int vexIndex(MGraph G, int x);void visit(int i);//初始化图
MGraph InitMgraph() {MGraph graph;memset(graph.edge, 0, sizeof(graph.edge));graph.arcnum = 0;graph.vernum = 0;return graph;
}//带头节点
//链队列节点
typedef struct Linknode {int data;struct Linknode *next;
} Linknode;//链队列
typedef struct {//队头指针Linknode *front;//队尾指针Linknode *rear;
} LinkQueue;//初始化队列
void InitQueue(LinkQueue *Q) {//创建头结点Linknode *temp = (Linknode *) malloc(sizeof(Linknode));Q->front = temp;Q->rear = temp;
}//入队
void EnQueue(LinkQueue *Q, int data) {//创造节点Linknode *temp = (Linknode *) malloc(sizeof(Linknode));//赋值temp->data = data;temp->next = NULL;//连接插入节点Q->rear->next = temp;//队尾指针更换Q->rear = temp;
}//出队
bool DeQueue(LinkQueue *Q, int *e) {//队列为空if (Q->rear == Q->front) {return false;}//要出队的节点Linknode *temp = Q->front->next;*e = temp->data;//队头指针更换Q->front->next = temp->next;free(temp);//最后一个节点出队if (temp == Q->rear) {//队尾指针更换Q->rear = Q->front;}return true;
}/
//借助队列实现拓扑排序
//卡恩算法
bool TopologicalSort(MGraph G) {//初始化队列LinkQueue *linkQueue = (Linknode *) malloc(sizeof(linkQueue));InitQueue(linkQueue);//当前顶点的入度int indegree[G.vernum];//记录拓扑排序int print[G.vernum];memset(indegree, 0, sizeof(indegree));//初始化入度数组for (int i = 0; i < G.vernum; ++i) {for (int j = 0; j < G.vernum; j++) {if (G.edge[j][i] == 1) {indegree[i]++;}}}//初始化print数组memset(print, -1, sizeof(print));//度为0的顶点索引入队列for (int i = 0; i < G.vernum; i++) {if (indegree[i] == 0) {EnQueue(linkQueue, i);indegree[i] = -1;}}//记录顶点个数int count = 0;int *e = malloc(sizeof(int));while (linkQueue->rear != linkQueue->front) {DeQueue(linkQueue, e);print[count] = G.vex[*e];count++;for (int i = 0; i < G.vernum; ++i) {if (G.edge[*e][i] == 1) {indegree[i]--;}if (indegree[i] == 0) {EnQueue(linkQueue, i);indegree[i] = -1;}}}if (count < G.vernum)return false;else {for (int i = 0; i < G.vernum; i++) {printf("%d  ", print[i]);}return true;}}int time;
int finalTime[100];
int visited[100];//DFS算法实现拓扑排序
//v为入度为0的顶点
void DFSTopologicalSort(MGraph G, int i) {//对i做已访问标记visited[vexIndex(G, i)] = 1;//找到i的所有邻接点for (int j = 0; j < G.vernum; j++) {if (visited[j] == 0 && G.edge[vexIndex(G, i)][j] == 1) {DFSTopologicalSort(G, G.vex[j]);}}(time)++;finalTime[vexIndex(G, i)] = time;}//使用后visited会被重新赋值，需重置
//建议用一个变量临时保存原有图
void DFSTraverseTopologicalSort(MGraph G, int i) {time = 0;for (int j = 0; j < G.vernum; j++) {visited[j] = 0;}DFSTopologicalSort(G, i);for (int j = 0; j < G.vernum; j++) {if (visited[j] == 0) {DFSTopologicalSort(G, G.vex[j]);}}for (int j = 0; j < G.vernum; j++) {printf("%d  ", finalTime[j]);}
}//有向图深度优先搜索
void niDFSTopologicalSort(MGraph G, int i) {//对i做已访问标记visited[vexIndex(G, i)] = 1;//找到i的所有邻接点for (int j = 0; j < G.vernum; j++) {if (visited[j] == 0 && G.edge[vexIndex(G, i)][j] == 1) {niDFSTopologicalSort(G, G.vex[j]);}}printf("%d  ", i);
}//使用后visited会被重新赋值，需重置
//建议用一个变量临时保存原有图
//连通图和非连通图的深度优先搜索(改进)
void niDFSTraverseTopologicalSort(MGraph G, int i) {for (int j = 0; j < G.vernum; j++) {visited[j] = 0;}niDFSTopologicalSort(G, i);for (int j = 0; j < G.vernum; j++) {if (visited[j] == 0) {niDFSTopologicalSort(G, G.vex[j]);}}
}int main(void) {//有向图//初始化图MGraph graph = InitMgraph();//图添加元素//顶点集添加1,2,3,4,5for (int i = 0; i < 5; i++) {graph.vex[i] = i + 1;graph.vernum++;}//边集加边<1,2>,<1,4>,<2,3>,<2,4>,<3,5>,<4,3>,<4,5>graph.edge[0][1] = 1;graph.edge[0][3] = 1;graph.edge[1][2] = 1;graph.edge[1][3] = 1;graph.edge[2][4] = 1;graph.edge[3][2] = 1;graph.edge[3][4] = 1;graph.arcnum = 7;printf("拓扑排序序列:\n");TopologicalSort(graph);printf("\n");printf("tineFinal数组:\n");DFSTraverseTopologicalSort(graph, 1);printf("\n");printf("逆拓扑排序序列:\n");niDFSTraverseTopologicalSort(graph, 5);
}//返回x在顶点表的索引
int vexIndex(MGraph G, int x) {int index = -1;for (int i = 0; i < G.vernum; i++) {if (G.vex[i] == x) {index = i;break;}}return index;
}

测试用例