不知

拓扑排序

2021-11-02|来源:|发布者:

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

1. 算法步骤

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到不存在入度为0的顶点为止。

1、选择一个入度为0的顶点并输出之;

2、从网中删除此顶点及所有出边。

循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列。

2. 为什么会有拓扑排序?拓扑排序有何作用?

举个例子,学习java系列的教程

代号科目学前需掌握
A1javaSE
A2html
A3JspA1,A2
A4servletA1
A5ssmA3,A4
A6springbootA5

就比如学习java系类(部分)从java基础,到jsp/servlet,到ssm,到springboot,springcloud等是个循序渐进且有依赖的过程。在jsp学习要首先掌握java基础和html基础。学习框架要掌握jsp/servlet和jdbc之类才行。那么,这个学习过程即构成一个拓扑序列。当然这个序列也不唯一,你可以对不关联的学科随意选择顺序(比如html和java可以随便先开始哪一个)。那上述序列可以简单表示为:

拓扑排序

其中五种均为可以选择的学习方案,对课程安排可以有参考作用,当然,五个都是拓扑序列。只是选择的策略不同!
一些其他注意:
DGA:有向无环图
AOV网:数据在顶点 可以理解为面向对象
AOE网:数据在边上,可以理解为面向过程!

3. 规则

图中每个顶点只出现一次

A在B前面,则不存在B在A前面的路径。(不能成环!!!!)

顶点的顺序是保证所有指向它的下个节点在被指节点前面!(例如A—>B—>C那么A一定在B前面,B一定在C前面)。所以,这个核心规则下只要满足即可,所以拓扑排序序列不一定唯一!

4. 算法实现

拓扑排序JAVA

package 图论;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class tuopu {
	static class node
	{
		int value;
		List<Integer> next;
		public node(int value) {
			this.value=value;
			next=new ArrayList<Integer>();
		}
		public void setnext(List<Integer>list) {
			this.next=list;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		node []nodes=new node[9];//储存节点
		int a[]=new int[9];//储存入度
		List<Integer>list[]=new ArrayList[10];//临时空间,为了存储指向的集合
		for(int i=1;i<9;i++)
		{
			nodes[i]=new node(i);
			list[i]=new ArrayList<Integer>();
		}
		initmap(nodes,list,a);
		
		//主要流程
		//Queue<node>q1=new ArrayDeque<node>();
		Stack<node>s1=new Stack<node>();
		for(int i=1;i<9;i++)
		{
			//System.out.print(nodes[i].next.size()+" 55 ");
			//System.out.println(a[i]);
			if(a[i]==0) {s1.add(nodes[i]);}
			
		}
		while(!s1.isEmpty())
		{
			node n1=s1.pop();//抛出输出
		    
			System.out.print(n1.value+" ");
			
			List<Integer>next=n1.next;
			for(int i=0;i<next.size();i++)
			{
				a[next.get(i)]--;//入度减一
				if(a[next.get(i)]==0)//如果入度为0
				{
					s1.add(nodes[next.get(i)]);
				}
			}
		}
	}

	private static void initmap(node[] nodes, List<Integer>[] list, int[] a) {
		list[1].add(3);
		nodes[1].setnext(list[1]);
		a[3]++;
		list[2].add(4);list[2].add(6);
		nodes[2].setnext(list[2]);
		a[4]++;a[6]++;
		list[3].add(5);
		nodes[3].setnext(list[3]);
		a[5]++;
		list[4].add(5);list[4].add(6);
		nodes[4].setnext(list[4]);
		a[5]++;a[6]++;
		list[5].add(7);
		nodes[5].setnext(list[5]);
		a[7]++;
		list[6].add(8);
		nodes[6].setnext(list[6]);
		a[8]++;
		list[7].add(8);
		nodes[7].setnext(list[7]);
		a[8]++;
		
	}
}

拓扑排序C++

#include<iostream>
#include <list>
#include <queue>
using namespace std;

/************************类声明************************/
class Graph
{
    int V;             // 顶点个数
    list<int> *adj;    // 邻接表
    queue<int> q;      // 维护一个入度为0的顶点的集合
    int* indegree;     // 记录每个顶点的入度
public:
    Graph(int V);                   // 构造函数
    ~Graph();                       // 析构函数
    void addEdge(int v, int w);     // 添加边
    bool topological_sort();        // 拓扑排序
};

/************************类定义************************/
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];

    indegree = new int[V];  // 入度全部初始化为0
    for(int i=0; i<V; ++i)
        indegree[i] = 0;
}

Graph::~Graph()
{
    delete [] adj;
    delete [] indegree;
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); 
    ++indegree[w];
}

bool Graph::topological_sort()
{
    for(int i=0; i<V; ++i)
        if(indegree[i] == 0)
            q.push(i);         // 将所有入度为0的顶点入队

    int count = 0;             // 计数,记录当前已经输出的顶点数 
    while(!q.empty())
    {
        int v = q.front();      // 从队列中取出一个顶点
        q.pop();

        cout << v << " ";      // 输出该顶点
        ++count;
        // 将所有v指向的顶点的入度减1,并将入度减为0的顶点入栈
        list<int>::iterator beg = adj[v].begin();
        for( ; beg!=adj[v].end(); ++beg)
            if(!(--indegree[*beg]))
                q.push(*beg);   // 若入度为0,则入栈
    }

    if(count < V)
        return false;           // 没有输出全部顶点,有向图中有回路
    else
        return true;            // 拓扑排序成功
}
用手机扫一扫访问本站
利民吧文章数据均来自于互联网,版权归原作者所有。如有侵犯您权利的资源,请联系我们处理。
Copyright © 2016-2024 利民吧 版权所有