유향 그래프의 작업 스케줄링 토폴로지 그래프 소개

1. 방향성 그래프의 데이터 유형

Bag를 사용하여 방향성 그래프를 표현합니다. 여기서 가장자리 v->w는 정점 v에 해당하는 인접 연결 리스트로 표현되며 이는 정점 v와 다릅니다. 무방향 그래프 여기서 각 모서리는 한 번만 나타납니다. 유방향 그래프의 데이터 구조 유형은 다음과 같습니다.

public class Digraph {private final int V;private int E;private Bag<Integer>[] adj;public Digraph(int V) {this.V=V;this.E=0;
        adj=(Bag<Integer>[])new Bag[V];for(int v=0;v<V;v++) {
            adj[v]=new Bag<Integer>();
        }
    }public int V() {return V;
    }public int E() {return E;
    }//添加一条边v->w,由于是有向图只要添加一条边就可以了public void addEdge(int v,int w) {
        adj[v].add(w);
        E++;
    }public Iterable<Integer> adj(int v) {return adj[v];
    }//返回当前图的一个反向的图public Digraph reverse() {
        Digraph R=new Digraph(V);for(int v=0;v<V;v++) {for(int w:adj(v)) {
                R.addEdge(w, v);
            }
        }return R;
    }
}

2. 유방향 그래프의 도달 가능성

그래프 연결성 과 유사하게 깊이 우선 검색을 사용하여 유향 그래프의

단일 지점 도달 가능성 문제를 해결할 수 있습니다. 즉, 유향 그래프와 시작점 s가 주어지면 다음이 있는지 여부에 답합니다. path from s 주어진 꼭지점으로 향하는 경로의 문제 v.

다지점 도달 가능성 문제: 유향 그래프와 꼭지점 집합이 주어지면 집합의 어떤 꼭지점에서 다음으로 가는 경로가 있는지 답하세요. 정점 v에 대한 지정된 경로는 무엇입니까?

public class DirectedDFS {private boolean[] marked;//从G中找出所有s可达的点public DirectedDFS(Digraph G,int s) {
        marked=new boolean[G.V()];
        dfs(G,s);
    }//G中找出一系列点可达的点public DirectedDFS(Digraph G,Iterable<Integer> sources) {
        marked=new boolean[G.V()];for(int s:sources) {if(!marked[s]) dfs(G,s);
        }
    }//深度优先搜素判断.private void dfs(Digraph G, int v) { 
        marked[v]=true;for(int w:G.adj(v)) {if(!marked[w]) dfs(G,w);
        }
    }//v是可达的吗public boolean marked(int v) {return marked[v];
    }
}

다지점 도달 가능성 문제의 중요한 적용은 많은 Java 구현을 포함한 일반적인 메모리 관리 시스템에 있습니다. 유향 그래프에서 정점은 개체를 나타내고 가장자리는 한 개체에서 다른 개체로의 참조를 나타냅니다.

이 모델은 Java 프로그램 실행 시 메모리 사용량을 잘 나타냅니다. 프로그램 실행 중 언제든지 직접 접근할 수 있는 특정 개체가 있으며, 이러한 개체를 통해 접근할 수 없는 모든 개체는

메모리 확보를 위해 재활용되어야 합니다. DirectedDFS와 유사한 방향성 그래프 도달 가능성 알고리즘을 주기적으로 실행하여 액세스 가능한 모든 개체를 표시합니다.

3. 유향 그래프의 길 찾기

유향 그래프의 일반적인 문제는 다음과 같습니다.

단일 지점 방향 경로. 유향 그래프와 시작점이 주어지면 "s에서 주어진 대상 정점 v까지의 유향 경로가 있습니까? 그렇다면 이 경로를 찾으십시오."

단일 지점 최단 유향 경로를 찾으십시오. 유향 그래프와 시작점이 주어지면 "s에서 주어진 대상 정점 v까지의 방향 경로가 있습니까? 그렇다면 가장 짧은 경로(최소 모서리 수를 포함하는)를 찾으십시오."

4 . 스케줄링 문제 - 위상 정렬

4.1 방향성 주기 찾기

우선순위 제약 조건이 있는 문제에 방향성 주기가 있는 경우 이 문제에는 해결책이 없습니다. 따라서 방향성 링 감지가 필요합니다.

다음 코드를 사용하면 주어진 방향성 그래프에 방향성 사이클이 포함되어 있는지 여부를 감지할 수 있습니다. 그렇다면 경로 방향에 따라 사이클의 모든 정점을 반환합니다.

dfs를 실행할 때 검색은 다음과 같습니다. 시작점에서 v까지의 방향 경로. onStack 배열은 재귀 호출 스택의 모든 정점을 표시합니다. 방향성 링이 발견되면 링의 모든 정점을 반환하기 위해 edgeTo 배열도 추가됩니다.

/**
 * 有向图G是否含有有向环
 * 获取有向环中的所有顶点
 * @author Administrator
 * */public class DirectedCycle {private boolean[] marked;    private int[] edgeTo;private Stack<Integer> cycle;    //有向环中的所有顶点private boolean[] onStack;        //递归调用的栈上的所有顶点public DirectedCycle(Digraph G) {
        edgeTo=new int[G.V()];
        onStack=new boolean[G.V()];
        marked=new boolean[G.V()];for(int v=0;v<G.V();v++) {if(!marked[v]) dfs(G,v);
        }
    }/**
 * 该算法的关键步骤在于onStack数组的运用.
 * onStack数组标记的是当前遍历的点.如果对于一个点指向的所有点中的某个点
 * onstack[v]=true.代表该点正在被遍历也就是说
 * 该点存在一条路径,指向这个点.而这个点现在又可以指向该点,
 * 即存在环的结构~
 * @param G
 * @param v */ private void dfs(Digraph G, int v) {
        onStack[v]=true;
        marked[v]=true;for(int w:G.adj(v)) {if(this.hasCycle()) return;else if(!marked[w]) {
                edgeTo[w]=v;
                dfs(G,w);
            }else if(onStack[w]) {
                cycle=new Stack<Integer>();for(int x=v;x!=w;x=edgeTo[x])
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);
            }
        }//dfs方法结束,对于该点的递归调用结束.该点指向的所有点已经遍历完毕onStack[v]=false;
    }private boolean hasCycle() {return cycle!=null;
    }public Iterable<Integer> cycle() {return cycle;
    }
}

4.2 위상 정렬

위상 정렬: 유향 그래프가 주어지면 모든 방향 가장자리가 앞쪽 요소에서 뒤쪽 요소를 가리키도록 모든 정점을 정렬합니다. 방향이 있는 경우

유향 그래프의 위상 정렬을 구현하려면 표준 깊이 우선 검색 순서를 사용하여 작업을 완료할 수 있습니다.

　1. : 재귀 호출 이전에 정점을 큐에 추가

　2. 포스트 오더: 재귀 호출 이후 큐에 정점을 추가

　3. 역 포스트 오더: 재귀 호출 스택 이후에 정점을 푸시합니다.

특정 작업에 대해서는 아래 코드를 참조하세요.

//有向图中基于深度优先搜索的拓补排序public class DepthFirstOrder {private boolean[] marked;private Queue<Integer> pre;        //所有顶点的前序排列private Queue<Integer> post;    //所有顶点的后序排列private Stack<Integer> reversePost;//所有顶点的逆后序排列public DepthFirstOrder(Digraph G) {
        pre=new Queue<>();
        post=new Queue<>();
        reversePost=new Stack<>();
        marked=new boolean[G.V()];        for(int v=0;v<G.V();v++) {if(!marked[v]) dfs(G,v);
        }
    }private void dfs(Digraph G, int v) {        pre.enqueue(v);marked[v]=true;for(int w:G.adj(v)) {if(!marked[w]) {
                dfs(G,w);
            }
        }        post.enqueue(v);    reversePost.push(v);}public Iterable<Integer> pre() {return pre;
    }public Iterable<Integer> post() {return post;
    }public Iterable<Integer> reversePost() {return reversePost;
    }
}

遍历的顺序取决于这个数据结构的性质以及是在递归调用之前还是之后进行保存。

前序：在递归调用之前将顶点加入队列。

后序：在递归调用之后将顶点加入队列。

逆后序：在递归调用之后将顶点压入栈。

 

前序就时dfs()的调用顺序；后序就是顶点遍历完成的顺序；逆后序就是顶点遍历完成顺序的逆。

拓补排序的实现依赖于上面的API,实际上拓补排序即为所有顶点的逆后序排列

拓补排序的代码如下:

public class Topological {private Iterable<Integer> order;    //顶点的拓补排序public Topological(Digraph G) {
        DirectedCycle cyclefinder=new DirectedCycle(G);if(!cyclefinder.hasCycle()) {//只有无环才能进行拓补排序DepthFirstOrder dfs=new DepthFirstOrder(G);
            order=dfs.reversePost();
        }
    }public Iterable<Integer> order() {return order;
    }public boolean isDAG() {return order!=null;
    }
}

 

5.有向图的强连通性

定义:如果两个顶点v和w是互相可达的,则称它们为强连通的.也就是说既存在一条从v到w的有向路径也存在一条从w到v的有向路径.

如果一幅有向图中的任意两个顶点都是强连通的,则称这副有向图也是强连通的.任意顶点和自己都是强连通的.

下面的代码采用如下步骤来计算强连通分量以及两个点是否是强连通的:

　　1.在给定的有向图中,使用DepthFirsetOrder来计算它的反向图G^R的逆后序排列

　　2.按照第一步计算得到的顺序采用深度优先搜索来访问所有未被标记的点

　　3.在构造函数中,所有在同一个递归dfs()调用中被访问到的顶点都是在同一个强连通分量中.

　　下面的代码实现遵循了上面的思路:

/**
 * 该算法实现的关键:
 * 使用深度优先搜索查找给定有向图的反向图GR.根据由此得到的所有顶点的逆后序
 * 再次用深度优先搜索处理有向图G.其构造函数的每一次递归调用所标记的顶点都在
 * 同一个强连通分量中.
 * 解决问题:
 * 判断两个点是否是强连通的
 * 判断总共有多少个连通分量
 * @author Administrator
 * */public class KosarajuSCC {private boolean[] marked;//已经访问过的顶点private int[] id;        //强连通分量的标识符private int count;        //强联通分量的数量public KosarajuSCC(Digraph G) {
        marked=new boolean[G.V()];
        id=new int[G.V()];
        DepthFirstOrder order=new DepthFirstOrder(G.reverse());for(int s:order.reversePost()) {if(!marked[s]) {
                dfs(G,s);
                count++;
            }
        }
    }private void dfs(Digraph G, int v) {
        marked[v]=true;
        id[v]=count;for(int w:G.adj(v)) {if(!marked[w]) {
                dfs(G,w);
            }
        }
    }public boolean stronglyConnected(int v,int w) {return id[v]==id[w];
    }public int id(int v) {return id[v];
    }public int count() {return count;
    }
}

 

위 내용은 유향 그래프의 작업 스케줄링 토폴로지 그래프 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!