一、总体架构
总体架构.png
二、重点说明
1.作用
现实生活中的项目工程、生产活动，都有一个所谓的流程，流程中包含各个步骤，步骤间具有优先级。可以把这个流程抽象为一个有向图。并且有向图中不能有环（因为有环意味着设计逻辑出错）。
2.来源
是对实际问题的抽象。现实生活中的工程项目、生产过程都有一个流程，按照特定的步骤进行执行，步骤之间具有执行的优先级，把这个抽象为有向无环图（DAG图）。
3.定义
4.前提条件
在有向无环图中才可找到拓扑排序，其余的情况找不到拓扑排序。
5. 思想
- 选取一个入度为0的点输出
- 将该节点、以及由该节点出发的边从图中删除
- 重复上述两个步骤，直到当前DAG图为空或不存在入度为0的节点。（后一种情况说明图中必有环）
6.实现
此处用图的邻接表进行存储。需要存储每个节点的入度数。
public class 拓扑排序 {
public static void main(String[] args) {
new 拓扑排序().exe();
}
public void exe() {
// 构建图
Scanner scan=new Scanner(System.in);
int N=scan.nextInt();
// 边数
int E=scan.nextInt();
ArcGraph2 g=new ArcGraph2(N,E);
for(int i=0;i<E;i++){
int vi=scan.nextInt();
int vj=scan.nextInt();
g.insertAdj(vi,vj);
}
System.out.println("深度优先遍历********");
travel(g);
System.out.println("拓扑排序********");
topSort(g);
}
// 遍历图
public void travel(ArcGraph2 g){
int[] visited=new int[g.n];
for(int i=0;i<g.n;i++){
if(visited[i]==0){
DFS(g,i,visited);
System.out.println("***********");
}
}
}
public void DFS(ArcGraph2 g,int v,int[] visited){
// 从节点v开始访问
visited[v]=1;
print(g,v);
ArcNode p=g.nodes[v].firstArc;
while(p!=null){
if(visited[p.num]==0){
DFS(g,p.num,visited);
}
p=p.nextArc;
}
}
private void print(ArcGraph2 g, int v) {
System.out.println(g.nodes[v].toString());
}
/**
* 输出有向无环图的拓扑排序
* @param g
* @return：true：拓扑排序成功；flase：不成功
*/
public boolean topSort(ArcGraph2 g){
// 计数器，记录已经输出的节点
int n=0;
Stack<Integer> stack=new Stack<Integer>();
// 遍历图的n个节点，将入度为0的节点入栈
for(int i=0;i<g.n;i++){
if(g.nodes[i].count==0){
stack.push(i);
}
}
// 开始访问栈中入度为0的节点
while(!stack.isEmpty()){
// 出栈
int t=stack.pop();
n++;
print(g,t);
// 将该节点，及从该节点出发的边去掉（即对应的入度减1）
ArcNode p=g.nodes[t].firstArc;
// 对于每一个邻接节点，入度减1
while(p!=null){
g.nodes[p.num].count--;
if(g.nodes[p.num].count==0){
stack.push(p.num);
}
p=p.nextArc;
}
}
if(n==g.n){
return true;
}else{
return false;
}
}
}
public class ArcGraph2 {
class ArcNode{
int num;// 节点编号（从0开始）
ArcNode nextArc;
public ArcNode(int num){
this.num=num;
this.nextArc=null;
}
}
class VNode{
int num;// 节点编号（从0开始）
String info;// 节点信息
int count;// 节点入度
ArcNode firstArc;
public VNode(int num){
this.num=num;
count=0;
this.info=null;
this.firstArc=null;
}
@Override
public String toString() {
return "VNode [num=" + num + ", info=" + info + ", count=" + count
+ ", firstArc=" + firstArc + "]";
}
}
// 节点数
int n;
// 边数
int e;
// 节点数组
VNode[] nodes;
public ArcGraph2(int n,int e){
this.n=n;
this.e=e;
nodes=new VNode[n];// 因为节点编号从0开始
for(int i=0;i<n;i++){
nodes[i]=new VNode(i);
}
}
// 节点vi的邻接节点vj
public void insertAdj(int vi, int vj) {
nodes[vj].count++;
ArcNode p=nodes[vi].firstArc;
if(p==null){
nodes[vi].firstArc=new ArcNode(vj);
}else{
while(p.nextArc!=null){
p=p.nextArc;
}
p.nextArc=new ArcNode(vj);
}
}
}
测试
输入的图.png
测试.png
