金融网站织梦模板,专门看广告的网站,做外贸无法登录国外网站怎么办,wordpress设置只显标题拓扑排序介绍
拓扑排序(Topological Order)是指#xff0c;将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。
这样说#xff0c;可能理解起来比较抽象。下面通过简单的例子进行说明#xff01; 例如#xff0c;一个项目包括A、B、…拓扑排序介绍
拓扑排序(Topological Order)是指将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。
这样说可能理解起来比较抽象。下面通过简单的例子进行说明 例如一个项目包括A、B、C、D四个子部分来完成并且A依赖于B和DC依赖于D。现在要制定一个计划写出A、B、C、D的执行顺序。这时就可以利用到拓扑排序它就是用来确定事物发生的顺序的。
在拓扑排序中如果存在一条从顶点A到顶点B的路径那么在排序结果中B出现在A的后面。
拓扑排序算法的基本步骤
构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological) 把所有没有依赖顶点的节点放入Q 当Q还有顶点的时候执行下面步骤 3.1 从Q中取出一个顶点n(将n从Q中删掉)并放入T(将n加入到结果集中) 3.2 对n每一个邻接点m(n是起点m是终点) 3.2.1 去掉边
#define MAX 100
// 邻接表
class ListDG
{private: // 内部类// 邻接表中表对应的链表的顶点class ENode{int ivex; // 该边所指向的顶点的位置ENode *nextEdge; // 指向下一条弧的指针friend class ListDG;};// 邻接表中表的顶点class VNode{char data; // 顶点信息ENode *firstEdge; // 指向第一条依附该顶点的弧friend class ListDG;};private: // 私有成员int mVexNum; // 图的顶点的数目int mEdgNum; // 图的边的数目VNode *mVexs; // 图的顶点数组public:// 创建邻接表对应的图(自己输入)ListDG();// 创建邻接表对应的图(用已提供的数据)ListDG(char vexs[], int vlen, char edges[][2], int elen);~ListDG();// 深度优先搜索遍历图void DFS();// 广度优先搜索类似于树的层次遍历void BFS();// 打印邻接表图void print();// 拓扑排序int topologicalSort();private:// 读取一个输入字符char readChar();// 返回ch的位置int getPosition(char ch);// 深度优先搜索遍历图的递归实现void DFS(int i, int *visited);// 将node节点链接到list的最后void linkLast(ENode *list, ENode *node);
};
(01) ListDG是邻接表对应的结构体。 mVexNum是顶点数mEdgNum是边数mVexs则是保存顶点信息的一维数组。 (02) VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据而firstEdge是该顶点所包含链表的表头指针。 (03) ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引而nextEdge是指向下一个节点的。
拓扑排序
/** 拓扑排序** 返回值* -1 -- 失败(由于内存不足等原因导致)* 0 -- 成功排序并输入结果* 1 -- 失败(该有向图是有环的)*/
int ListDG::topologicalSort()
{int i,j;int index 0;int head 0; // 辅助队列的头int rear 0; // 辅助队列的尾int *queue; // 辅组队列int *ins; // 入度数组char *tops; // 拓扑排序结果数组记录每个节点的排序后的序号。ENode *node;ins new int[mVexNum];queue new int[mVexNum];tops new char[mVexNum];memset(ins, 0, mVexNum*sizeof(int));memset(queue, 0, mVexNum*sizeof(int));memset(tops, 0, mVexNum*sizeof(char));// 统计每个顶点的入度数for(i 0; i mVexNum; i){node mVexs[i].firstEdge;while (node ! NULL){ins[node-ivex];node node-nextEdge;}}// 将所有入度为0的顶点入队列for(i 0; i mVexNum; i )if(ins[i] 0)queue[rear] i; // 入队列while (head ! rear) // 队列非空{j queue[head]; // 出队列。j是顶点的序号tops[index] mVexs[j].data; // 将该顶点添加到tops中tops是排序结果node mVexs[j].firstEdge; // 获取以该顶点为起点的出边队列// 将与node关联的节点的入度减1// 若减1之后该节点的入度为0则将该节点添加到队列中。while(node ! NULL){// 将节点(序号为node-ivex)的入度减1。ins[node-ivex]--;// 若节点的入度为0则将其入队列if( ins[node-ivex] 0)queue[rear] node-ivex; // 入队列node node-nextEdge;}}if(index ! mVexNum){cout Graph has a cycle endl;delete queue;delete ins;delete tops;return 1;}// 打印拓扑排序结果cout TopSort: ;for(i 0; i mVexNum; i )cout tops[i] ;cout endl;delete queue;delete ins;delete tops;return 0;
}
说明 (01) queue的作用就是用来存储没有依赖顶点的顶点。它与前面所说的Q相对应。 (02) tops的作用就是用来存储排序结果。它与前面所说的T相对应。
