文章
100
粉丝
0
获赞
0
访问
3.8k
(1)统计入度:遍历邻接矩阵,计算每个顶点的入度(即指向该顶点的边数)。
入队:将所有入度为 0 的顶点存入栈或队列(这些是没有任何前导工程的任务)。
循环处理:从栈/队列中取出一个顶点。
输出该顶点(或存入结果数组)。
遍历该顶点的所有邻接点,将它们的入度减 1。
如果某个邻接点的入度减为 0,则将其入队。
判断回路:如果输出的顶点数小于图中的总顶点数 n,说明图中存在环(即工程逻辑冲突,A依赖B,B又依赖A)。
(2)
#include <stdio.h>
#include <stdbool.h>
#define MAXV 100 // 假设最大顶点数
typedef struct {
int numVertices, numEdges;
char verticesList[MAXV];
int Edge[MAXV][MAXV];
} MGraph;
// 拓扑排序函数
bool TopologicalSort(MGraph G) {
int indegree[MAXV] = {0}; // 存储每个顶点的入度
int stack[MAXV]; // 辅助栈
int top = -1;
int count = 0; // 记录已输出的顶点数
// 1. 计算所有顶点的入度
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
if (G.Edge[i][j] != 0) {
&n...
登录后发布评论
暂无评论,来抢沙发