TopoLogicalSort


AOV网与拓扑排序

基本概念

AOV网(Activity On Vertex Network)

​ 一项大工程可以被看作若干个子工程组成的集合,这些子工程之间存在着先后顺序关系,这些子工程被称为活动(Activity),在AOV网中,顶点(Vertex)表示活动,边(Arc)表示活动之间的先后关系,其一定是一个有向无环图(DAG).

AOV.jpg

拓扑排序(TopoLogical Sort)

​ 拓扑序列是一个有向无环图的包含所有顶点的线性序列,该序列能保证所有的子工程不会出现冲突的情况,由AOV网构造拓扑序列的过程叫做拓扑排序.

  • 每个顶点出现且只出现一次
  • 若存在Vi到Vj的路径,在此序列中Vi出现在Vj的前面

topo.jpg


算法思想

由AOV网构造拓扑序列的拓扑排序算法执行以下步骤

  1. 从图中选取一个没有前驱的顶点(即入度为0的顶点),将其删除.
  2. 删除该顶点的所有出度边.
  3. 重复执行1和2至图中不存在入度为0的顶点.
  4. 若以上步骤执行后,拓扑序列不包含所有顶点,则该图中必定存在环.

TopoOrder.jpg


代码实现

/*************************************************
 * Author           : TangRan                    
 * Blog             : tongyin.site               
 * Email            : tarngran@outlook.com       
 * Last modified    : 2021-12-29 16:46
 * Filename         : TopoLogicalSort.c
 * Description      :                            
 *************************************************/

//


#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define OK 1
#define ERR (-1)
#define MAX 100
typedef char VerTexType;
typedef int ArcType;
typedef int Status;

typedef struct {
  VerTexType vexs[MAX];//顶点表
  ArcType m[MAX][MAX];//矩阵
  int vexnum, arcnum;//顶点数和边数
}AMG;

typedef struct {
  int *base;
  int front;
  int rear;
}Q;

//辅助队列
bool empty(Q *q);
Status initQueue(Q *q);
void push(Q *q, int e);
int front(Q *q);
void pop(Q *q);

//图操作
int locateVex(const AMG *G, VerTexType vex);
Status createUDN(AMG *G);
void Print(const AMG *G);

//拓扑排序
int* Indegrees(const AMG *G);
void topologicalSort(const AMG *G);

bool empty(Q *q) {
  return q -> rear == q -> front;
}

Status initQueue(Q *q) {
  if (!q) return ERR;
  q -> base = (int*)malloc(sizeof(int) * MAX);
  q -> front = q -> rear = 0;
  return OK;
}

void push(Q *q, int e) {
  if (!q) return;
  if ((q -> rear + 1) % MAX == q -> front) return;
  q -> base[q -> rear] = e;
  q -> rear = (q ->  rear + 1) % MAX;
}

int front(Q *q) {
  if (!q || empty(q)) return ERR;
  return q -> base[q -> front];
}

void pop(Q *q) {
  if (!q || empty(q)) return;
  q -> front = (q -> front + 1) % MAX;
}

int locateVex(const AMG *G, VerTexType vex) {
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	if (G -> vexs[i] == vex) return i;
  }
  return ERR;
}

Status createUDN(AMG *G) {
  printf("输入总顶点数和总边数:>");
  scanf("%d %d", &G -> vexnum, &G -> arcnum);
  for (int i = 0 ; i < G -> vexnum ; ++i) { //构建顶点表
	while(getchar() != '\n');
	printf("依次输入顶点的信息:>");
	scanf("%c", &G -> vexs[i]);
  }
  for (int i = 0 ; i < G -> vexnum ; ++i) { //初始化矩阵
	for (int j = 0 ; j < G -> vexnum ; ++j) {
	  G -> m[i][j] = INT_MAX;
	  if (i == j) G -> m[i][j] = 0;//对角线为自身到自身
	}
  }
  for (int i = 0 ; i < G -> arcnum ; ++i) { //根据边数构建矩阵
	VerTexType v1, v2;
	ArcType weight;
	int idx1, idx2;
	printf("输入两个顶点以及边的权值:");
	while (getchar() != '\n');
	scanf("%c %c %d", &v1, &v2, &weight);
	idx1 = locateVex(G, v1);
	idx2 = locateVex(G, v2);
	G -> m[idx1][idx2] = weight;
  }
  return OK;
}

void Print(const AMG *G) {
  if (!G) return;
  printf("顶点表 : ");
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	printf("%c ", G -> vexs[i]);
  }
  printf("\n");
  printf("领接表 : \n");
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	printf("\t%c", G -> vexs[i]);
  }
  printf("\n");
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	printf("%c\t", G -> vexs[i]);
	for (int j = 0 ; j < G -> vexnum ; ++j) {
	  if (G -> m[i][j] == INT_MAX) {
		printf("∞\t");
	  } else {
		printf("%d\t", G -> m[i][j]);
	  }
	}
	printf("\n");
  }
  printf("\n");
}

int* Indegrees(const AMG *G) {
  int *indegrees = (int*)malloc(sizeof(int) * G -> vexnum);
  for (int i = 0 ; i < G -> vexnum ; ++i) indegrees[i] = 0;
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	for (int j = 0 ; j < G -> vexnum ; ++j) {
	  if (G -> m[i][j] && G -> m[i][j] != INT_MAX) {
		indegrees[j]++;
	  }
	}
  }
  return indegrees;
}

void topologicalSort(const AMG *G) {
  if (!G) return;
  Q q;
  initQueue(&q);
  int topo[G -> vexnum], idx = 0;
  memset(topo, 0, sizeof(topo));
  int *indegrees = Indegrees(G);
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	if (indegrees[i] == 0) push(&q, i);
  }
  while (!empty(&q)) {
	int e = front(&q);
	pop(&q);
	topo[idx++] = e;
	for (int i = 0 ; i < G -> vexnum ; ++i) {
	  if (G -> m[e][i] && G -> m[e][i] != INT_MAX) {
		indegrees[i]--;
		if (indegrees[i] == 0) push(&q, i);
	  }
	}
  }
  if (idx < G -> vexnum) printf("图中带环!\n");
  else printf("图中无环!\n");
}

int main() {
  AMG G;
  if (OK == createUDN(&G)) {
	printf("构建成功!\n");
	Print(&G);
	topologicalSort(&G);
  }
  return 0;
}
//cpp
std::vector<int> Indegrees(const AMG *G) {
  std::vector<int> indegrees(G -> vexnum, 0);
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	for (int j = 0 ; j < G -> vexnum ; ++j) {
	  if (G -> m[i][j] && G -> m[i][j] != INT_MAX) {
		indegrees[j]++;
	  }
	}
  }
  return indegrees;
}

void topologicalSort(const AMG *G) {
  if (!G) return;
  std::queue<int> q;
  std::vector<int> topo;
  std::vector<int> indegrees = Indegrees(G);
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	if (indegrees[i] == 0) q.push(i);
  }
  while (!q.empty()) {
	int e = q.front();
	q.pop();
	topo.push_back(e);
	for (int i = 0 ; i < G -> vexnum ; ++i) {
	  if (G -> m[e][i] && G -> m[e][i] != INT_MAX) {
		indegrees[i]--;
		if (indegrees[i] == 0) q.push(i);
	  }
	}
  }
  if (topo.size() != G -> vexnum) printf("图中带环!\n");
  else printf("图中无环!\n");
}

测试结果

test1.jpg

test2.jpg


文章作者: tang ran
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 tang ran !
  目录