网站需求清单,全国被执行人名单查询,辽宁建设执业信息网官网,上海模板网站制作多少钱目录 有向无环图拓扑排序求拓扑排序步骤代码实现 例题 有向无环图
如果一个有向图的任意顶点都无法通过一些有向边回到自身#xff0c;那么称这个有向图为有向无环图#xff08;DirectedAcyclic Graph#xff0c;DAG#xff09;。
拓扑排序
拓扑排序是将有向无环图G的所… 目录 有向无环图拓扑排序求拓扑排序步骤代码实现 例题 有向无环图
如果一个有向图的任意顶点都无法通过一些有向边回到自身那么称这个有向图为有向无环图DirectedAcyclic GraphDAG。
拓扑排序
拓扑排序是将有向无环图G的所有顶点排成一个线性序列使得对图G中的任意两个顶点u、v如果存在边u-v那么在序列中u一定在v前面。这个序列又被称为拓扑序列。
求拓扑排序步骤
定义一个队列Q并把所有入度为0的结点加入队列(算法笔记p251队列)。取队首结点输出。然后删去所有从它出发的边并令这些边到达的顶点的入度减1如果某个顶点的入度减为0则将其加入队列。反复进行②操作直到队列为空。如果队列为空时入过队的结点数目恰好为N说明拓扑排序成功图G为有向无环图否则拓扑排序失败图G中有环。
代码实现
可使用邻接表实现拓扑排序。显然由于需要记录结点的入度因此需要额外建立一个数组inDegree[MAXV]并在程序一开始读入图时就记录好每个结点的入度。接下来就只需要按上面所说的步骤进行实现即可拓扑排序的代码如下
C实现
#include vector
#include queue#define MAXV 10000using namespace std;vectorint G[MAXV]; // 邻接表
int n, inDegree[MAXV]; // 顶点数、入度// 拓扑排序
bool topologicalSort() {int num 0;queueint q;for (int i 0; i n; i)if (inDegree[i] 0)q.push(i); //将所有入度为0的顶点入队while (!q.empty()) {int u q.front(); // 取队首顶点u// printf(%d, u); // 此处可输出顶点u,作为拓扑序列中的顶点q.pop();for (int i 0; i G[u].size(); i) {int v G[u][i]; // u的后继结点vinDegree[v]--; // 顶点v的入度减1if (inDegree[v] 0) // 顶点v的入度减为0则入队q.push(v);}G[u].clear(); // 清空顶点u的所有出边(如无必要可不写)num; // 加入拓扑序列的顶点数加1}if (num n) return true; // 加入拓扑排序的顶点数为n,说明拓扑排序成功else return false; // 加入拓扑排序的顶点数小于n,说明拓扑排序失败
}拓扑排序的很重要的应用就是判断一个给定的图是否是有向无环图。正如上面的代码如果 topologicalSort0函数返回true则说明拓扑排序成功给定的图是有向无环图否则说明拓扑排序失败给定的图中有环。最后指出如果要求有多个入度为0的顶点选择编号最小的顶点那么把queue改成priority_queue堆实现并保持队首元素是优先队列中最小的元素即可(算法笔记p335堆)。
C语言实现
#include stdio.h
#include stdbool.h#define MaxSize 1000// 图的邻接表实现数据结构定义
typedef int VertexType;
typedef int EdgeType;// 边表结点
typedef struct ArcNode {int adjVertex; // 该弧所指向的顶点的位置EdgeType info; // 弧的权值struct ArcNode *next; // 指向下一条弧的指针
} ArcNode;
// 顶点表结点
typedef struct VertexNode {VertexType data; // 顶点信息struct ArcNode *first; // 指向第一条依附该顶点的弧的指针
} AdjList;
// 图的链式存储(邻接表实现)
typedef struct ALGraph {AdjList vertices[MaxSize]; // 邻接表int verNum, arcNum; // 顶点数和弧数
} ALGraph;// 循环队列实现的数据结构定义
typedef int ElemType;typedef struct Queue {ElemType data[MaxSize];int front, rear;
} Queue;void init(Queue *q) {q-rear 0;q-front 0;
}bool empty(Queue *q) {return q-front q-rear;
}bool full(Queue *q) {return (q-rear 1) % MaxSize q-front;
}bool push(Queue *q, ElemType value) {if (full(q))return false;q-data[q-rear] value;q-rear (q-rear 1) % MaxSize;return true;
}bool pop(Queue *q, ElemType *p) {if (empty(q))return false;*p q-data[q-front];q-front (q-front 1) % MaxSize;return true;
}// 入度
int inDegree[MaxSize];// 计算图中各个顶点的入度
void countInDegree(ALGraph *G) {// 初始化for (int i 0; i G-verNum; i)inDegree[i] 0;// 计算入度for (int i 0; i G-verNum; i) {ArcNode *node G-vertices[i].first;while (node) {inDegree[node-adjVertex];node node-next;}}
}// 拓扑排序
bool topologicalSort(ALGraph *G) {int num 0; // 记录加入拓扑排序的顶点数Queue q; // 拓扑队列init(q); // 初始化队列countInDegree(G); // 计算图的入度for (int i 0; i G-verNum; i)if (inDegree[i] 0)push(q, i); //将所有入度为0的顶点入队while (!empty(q)) {int u;pop(q, u); // 取队首顶点u并出队// printf(%d, u); // 此处可输出顶点u,作为拓扑序列中的顶点ArcNode *i G-vertices[u].first;while (i) {int v G-vertices[i-adjVertex].data;inDegree[v]--; // 顶点v的入度减1if (inDegree[v] 0) // 顶点v的入度减为0则入队push(q, v);i i-next;}G-vertices[u].first NULL; // 清空顶点u的所有出边(如无必要可不写)num; // 加入拓扑序列的顶点数加1}if (num G-verNum) return true; // 加入拓扑排序的顶点数为n,说明拓扑排序成功else return false; // 加入拓扑排序的顶点数小于n,说明拓扑排序失败
}例题
2012年中国科学技术大学研究生复试机试题任务调度
