拓扑排序
（1）在有向图中选一个没有前驱的顶点且输出之；
（2）在图中删除该顶点和所有以它为尾的弧。
重复上述两个步骤，直至全部顶点均已输出，或者当前图中不存在无前驱节点的顶点为止，后一种情况则说明有向图中存在环
最后得到的有向图的拓扑序列为：
算法实现
//算法7.12
Status TopologicalSort(ALGraph G){
int i, k, count, indegree[MAX_VERTEX_NUM];
SqStack S;
ArcNode *p;
FindInDegree(G, indegree); // 对各顶点求入度indegree[0..vernum-1]
InitStack(&S); // 初始化栈
for (i = 0; i < G.vexnum; ++i) // 建零入度顶点栈S
if (!indegree[i])
Push(&S, i); // 入度为0者进栈
count = 0; // 对输出顶点计数
while (!StackEmpty(S)){
// 栈不空
Pop(&S, &i);
printf("%s ", G.vertices[i].data); // 输出i号顶点并计数
++count;
for (p = G.vertices[i].firstarc; p; p = p->nextarc){
// 对i号顶点的每个邻接点的入度减1
k = p->adjvex;
if (!(--indegree[k])) // 若入度减为0,则入栈
Push(&S, k);
}
}
if (count < G.vexnum){
printf("此有向图有回路\n");
return ERROR;
}
else{
printf("为一个拓扑序列。\n");
return OK;
}
}
完整代码
#include<bits/stdc++.h>
using namespace std;
typedef int Status;
typedef int Boolean;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAX_NAME 5
typedef int InfoType;
typedef char VertexType[MAX_NAME];
/* ---------------------------------- 图的邻接表存储表示 ----------------------------------*/
#define MAX_VERTEX_NUM 20
typedef enum {
DG, DN, AG, AN }GraphKind; //{有向图,有向网,无向图,无向网}
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct{
VertexType data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum, arcnum;
int kind;
}ALGraph;
/* --------------------------- 需要用的图的邻接表存储的基本操作 --------------------------*/
int LocateVex(ALGraph &G, VertexType u){
int i;
for (i = 0; i < G.vexnum; ++i)
if (strcmp(u, G.vertices[i].data) == 0)
return i;
return -1;
}
Status CreateGraph(ALGraph &G){
int i, j, k;
int w; /* 权值 */
VertexType va, vb;
ArcNode *p;
printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
scanf("%d", &G.kind);
printf("请输入图的顶点数和边数(空格隔开): ");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请输入%d个顶点的值(<%d个字符):\n", G.vexnum, MAX_NAME);
for (i = 0; i < G.vexnum; ++i)
{
scanf("%s", G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
if (G.kind == 1 || G.kind == 3)
printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
else
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for (k = 0; k < G.arcnum; ++k)
{
if (G.kind == 1 || G.kind == 3) // 网
scanf("%d%s%s", &w, va, vb);
else // 图
scanf("%s%s", va, vb);
i = LocateVex(G, va); // 弧尾
j = LocateVex(G, vb); // 弧头
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
if (G.kind == 1 || G.kind == 3) {
// 网
p->info = (int *)malloc(sizeof(int));
*(p->info) = w;
}
else
p->info = NULL; // 图
p->nextarc = G.vertices[i].firstarc; // 插在表头
G.vertices[i].firstarc = p;
if (G.kind >= 2){
// 无向图或网,产生第二个表结点
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
if (G.kind == 3){
// 无向网
p->info = (int*)malloc(sizeof(int));
*(p->info) = w;
}
else
p->info = NULL; // 无向图
p->nextarc = G.vertices[j].firstarc; // 插在表头
G.vertices[j].firstarc = p;
}
}
return OK;
}
Boolean visited[MAX_VERTEX_NUM];
void(*VisitFunc)(char* v);
void Display(ALGraph G){
// 输出图的邻接表G
int i;
ArcNode *p;
switch (G.kind)
{
case DG: printf("有向图\n");
break;
case DN: printf("有向网\n");
break;
case AG: printf("无向图\n");
break;
case AN: printf("无向网\n");
}
printf("%d个顶点：\n", G.vexnum);
for (i = 0; i < G.vexnum; ++i)
printf("%s ", G.vertices[i].data);
printf("\n%d条弧(边):\n", G.arcnum);
for (i = 0; i < G.vexnum; i++){
p = G.vertices[i].firstarc;
while (p){
if (G.kind <= 1) {
// 有向
printf("%s→%s ", G.vertices[i].data, G.vertices[p->adjvex].data);
if (G.kind == DN) // 网
printf(":%d ", *(p->info));
}
else{
// 无向(避免输出两次)
if (i < p->adjvex) {
printf("%s－%s ", G.vertices[i].data, G.vertices[p->adjvex].data);
if (G.kind == AN) /* 网 */
printf(":%d ", *(p->info));
}
}
p = p->nextarc;
}
printf("\n");
}
}
void FindInDegree(ALGraph G, int indegree[])
{
//求顶点的入度
int i;
ArcNode *p;
for (i = 0; i < G.vexnum; i++)
indegree[i] = 0; //初始化
for (i = 0; i < G.vexnum; i++)
{
p = G.vertices[i].firstarc;
while (p)
{
indegree[p->adjvex]++;
p = p->nextarc;
}
}
}
typedef int SElemType; // 栈类型
/* ------------------------------------ 栈的顺序存储表示 ----------------------------------*/
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
Status InitStack(SqStack *S)
{
/* 构造一个空栈S */
(*S).base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top = (*S).base;
(*S).stacksize = STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{
/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if (S.top == S.base)
return TRUE;
else
return FALSE;
}
Status Push(SqStack *S, SElemType e)
{
/* 插入元素e为新的栈顶元素 */
if ((*S).top - (*S).base >= (*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base = (SElemType *)realloc((*S).base, ((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));
if (!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top = (*S).base + (*S).stacksize;
(*S).stacksize += STACKINCREMENT;
}
*((*S).top)++ = e;
return OK;
}
Status Pop(SqStack *S, SElemType *e)
{
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if ((*S).top == (*S).base)
return ERROR;
*e = *--(*S).top;
return OK;
}
//算法7.12
Status TopologicalSort(ALGraph G){
int i, k, count, indegree[MAX_VERTEX_NUM];
SqStack S;
ArcNode *p;
FindInDegree(G, indegree); // 对各顶点求入度indegree[0..vernum-1]
InitStack(&S); // 初始化栈
for (i = 0; i < G.vexnum; ++i) // 建零入度顶点栈S
if (!indegree[i])
Push(&S, i); // 入度为0者进栈
count = 0; // 对输出顶点计数
while (!StackEmpty(S)){
// 栈不空
Pop(&S, &i);
printf("%s ", G.vertices[i].data); // 输出i号顶点并计数
++count;
for (p = G.vertices[i].firstarc; p; p = p->nextarc){
// 对i号顶点的每个邻接点的入度减1
k = p->adjvex;
if (!(--indegree[k])) // 若入度减为0,则入栈
Push(&S, k);
}
}
if (count < G.vexnum){
printf("此有向图有回路\n");
return ERROR;
}
else{
printf("为一个拓扑序列。\n");
return OK;
}
}
int main(){
ALGraph f;
printf("请选择有向图\n");
CreateGraph(f);
Display(f);
TopologicalSort(f);
}
测试样例
请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): 0
请输入图的顶点数和边数(空格隔开): 6 8
请输入6个顶点的值(<5个字符):
v1 v2 v3 v4 v5 v6
请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):
v1 v2
v1 v3
v1 v4
v3 v2
v3 v5
v4 v5
v6 v4
v6 v5
运行结果
有向图
6个顶点：
v1 v2 v3 v4 v5 v6
8条弧(边):
v1→v4 v1→v3 v1→v2
v3→v5 v3→v2
v4→v5
v6→v5 v6→v4
v6 v1 v3 v2 v4 v5 为一个拓扑序列。
京公网安备 11010502036488号