文章
63
粉丝
1100
获赞
1549
访问
130w
拓扑排序是对有向无环图(DAG)的顶点进行排序的一种算法,使得对于图中的任意一条有向边 (u, v),顶点 u 在排序结果中都出现在顶点 v 之前。要判断一个有向图是否存在唯一的拓扑序列,可以按照以下步骤进行:
#include <stdio.h>
#include <stdlib.h>
#define MAXV 100
typedef struct //图的类型定义
{
int numVertices, numEdges; //图的顶点数和有向边数
char verticesList[MAXV]; //顶点表,MAXV为已定义常量
int Edge[MAXV][MAXV]; //邻接矩阵
} MGraph;
// 判断图是否存在唯一的拓扑序列
int uniquely(MGraph G) {
int inDegree[MAXV] = {0}; // 存储每个顶点的入度
int queue[MAXV]; // 队列用于存储入度为 0 的顶点
int front = 0, rear = 0; // 队列的头和尾指针
int count = 0; // 记录拓扑序列的长度
// 计算每个顶点的入度
for (int i = 0; i < G.numVertices; i++) {
for (int j = 0; j < G.numVertices; j++) {
if (G.Edge[j][i] =...
登录后发布评论
暂无评论,来抢沙发