赞
踩
目录
用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的网,简称AOV-网。
设G=(V,E)是一个具有n个顶点的有向图,V中顶点序列v1,v2,…,vn称为一个拓扑序列,当且仅当该顶点序列满足下列条件:
1.每个顶点出现且只出现一次
2.存在一条从顶点i到顶点j的路径,那么在序列中顶点i出现在顶点j的前面
在一个有向图中找一个拓扑序列的过程称为拓扑排序。
最后得到拓扑序列 C4 , C0 , C3 , C2 , C1 , C5 。
(1)在AOV 网中,若不存在回路.则所有活动可排成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,那么该序列为拓扑序列.
(2)拓扑序列不是唯一的.
(3)对AOV图不一定都有拓扑序列.
(1) 创建有向图,输入AOV网络;
(2)求所有顶点的入度值,将所有入度为0的顶点入栈;
(3)当栈不空时,出栈一个顶点i, 并输出i;
(4)将i的所有邻接点入度减1,如果入度减为0,则入栈。 重复以上 3、4 步, 直到栈空为止。
基于有向图的邻接表实现:
- #include <iostream>
- #include <stack>
- using namespace std;
- #define MAXV 100
-
- typedef struct ArcNode //边表节点
- {
- int adjvex; //边表节点在数组的位置
- ArcNode* Next; //指向下一个节点
- }ArcNode;
-
- typedef struct VNode //表头结点类型
- {
- char data; //顶点信息,假设为字符型
- int count; //存放顶点入度
- ArcNode* firstarc; //指向第一条边
- } VNode;
-
- typedef struct ALGraph
- {
- int vexnum; //图的顶点数
- int arcnum; //图的边数
- VNode adjlist[MAXV]; //邻接表
- }ALGraph;
-
- int Locate(char data, ALGraph G)
- {
- for (int i = 0; i < G.vexnum; i++)
- {
- if (G.adjlist[i].data == data)
- return i;
- }
- return -1;
- }
-
- void CreatALGraph(ALGraph& G) //创建有向图
- {
- cout << "请输入图的顶点个数:" << endl;
- cin >> G.vexnum;
- cout << "请输入图中边的个数:" << endl;
- cin >> G.arcnum;
-
- cout << "请输入顶点信息:" << endl;
- for (int i = 0; i < G.vexnum; i++)
- {
- cin >> G.adjlist[i].data;
- G.adjlist[i].count = 0;
- G.adjlist[i].firstarc = NULL;
- }
-
- char data1, data2;
- cout << "请输入从顶点p到顶点q的边:" << endl; //p->q
- for (int i = 0; i < G.arcnum; i++)
- {
- cin >> data1 >> data2;
- int pos1 = Locate(data1, G);
- int pos2 = Locate(data2, G);
-
- ArcNode* p = new ArcNode;
- p->adjvex = pos2;
- p->Next = G.adjlist[pos1].firstarc;
- G.adjlist[pos1].firstarc = p;
- }
-
- }
-
- void TopSort(ALGraph& G) //拓扑排序算法
- {
- ArcNode* p;
- stack<int> st= {};
- for (int i = 0; i < G.vexnum; i++) //求所有顶点的入度
- {
- p = G.adjlist[i].firstarc;
- while (p != NULL)
- {
- G.adjlist[p->adjvex].count++;
- p = p->Next;
- }
- }
-
- for (int i = 0; i < G.vexnum; i++)
- {
- if (G.adjlist[i].count == 0)
- st.push(i); //将入度为0的顶点进栈
- }
- while (!st.empty()) //栈不空循环排序
- {
- int top = st.top();
- st.pop(); //出栈一个顶点i
- cout << G.adjlist[top].data; //输出该顶点
- p = G.adjlist[top].firstarc; //找第一个邻接点
- while (p != NULL) //将顶点i的出边邻接点的入度减1
- {
- int j = p->adjvex;
- G.adjlist[j].count--;
- if (G.adjlist[j].count == 0) //将入度为0的邻接点进栈
- st.push(j);
- p = p->Next; //找下一个邻接点
- }
- }
- }
-
- int main() {
- ALGraph G{};
- cout << "创建有向图:" << endl;
- CreatALGraph(G);
- cout << "拓扑排序:" << endl;
- TopSort(G);
- return 0;
- }
输出结果如下:
拓扑排序是对又向无圈图的顶点的一种排序,它使得如果存在一条从Vi
到Vj
的路径,那么在排序中Vj
必须出现在 Vi
的后面。一种简单的求拓扑排序的算法先是找出任意一个入度为0的顶点。然后我们输出该顶点,并将它和它的边一起冲图中删除。然后,将其邻接的顶点的入度减去1。然后重复上述过程,直达图被完全删除。拓扑排序可以用来解决课程学习先后顺序等问题。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。