Introduction au graphe de topologie de planification de tâches du graphe orienté

1. Type de données d'un graphe orienté

Utilisez Bag pour représenter un graphe orienté, où le bord v->w est représenté comme sommet. v La liste chaînée de contiguïté correspondante contient un sommet w Contrairement au graphe non orienté, chaque arête n'apparaît ici qu'une seule fois. Le type de structure de données du graphe orienté est le suivant :

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. Accessibilité dans un graphe orienté

Connectivité d'un graphe non orienté Semblable à , profondeur- la première recherche peut être utilisée pour résoudre le

problème d'accessibilité à un point unique dans un graphe orienté : c'est-à-dire : étant donné un graphe orienté Graph et un point de départ s, répondre à la question de savoir s'il existe un chemin dirigé de s à un sommet donné v.

Problème d'accessibilité multipoint : donné Étant donné un graphe orienté et un ensemble de sommets, répondez s'il existe un chemin dirigé depuis n'importe quel sommet de l'ensemble vers un sommet v donné ?

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];
    }
}

Une application importante du problème d'accessibilité multipoint se trouve dans les systèmes de gestion de mémoire typiques, y compris de nombreuses implémentations Java. Dans un graphe orienté, un sommet représente un objet et une arête représente une référence d'un objet à un autre.

Ce modèle représente bien l'utilisation de la mémoire lors de l'exécution de programmes Java. Certains objets sont accessibles directement à tout moment pendant l'exécution du programme, et tous les objets auxquels on ne peut pas accéder via ces objets doivent être recyclés pour

libérer de la mémoire. Il exécute périodiquement un algorithme d'accessibilité de graphique dirigé similaire à DirectedDFS pour marquer tous les objets accessibles.

3. La recherche de chemin dans les graphes orientés

est similaire aux graphes non orientés. dans les graphes orientés :

Chemin dirigé à un seul point. Étant donné un graphe orienté et un point de départ, répondez "Y a-t-il un chemin dirigé de s au sommet de destination donné v ? Si oui, trouvez ce chemin"

Le plus court en un seul point chemin dirigé. Étant donné un graphe orienté et un point de départ, répondez "Y a-t-il un chemin dirigé de s au sommet de destination donné v ? Si oui, trouvez le plus court (contenant le moins d'arêtes)"

4. Problème d'ordonnancement - tri topologique

4.1 Recherche d'anneaux dirigés

S'il existe un cycle dirigé dans un problème avec des contraintes prioritaires, alors le problème doit être insoluble. Par conséquent, une détection d’anneau dirigée est requise.

Le code suivant peut être utilisé pour détecter si un graphe orienté donné contient un cycle orienté. Si tel est le cas, renvoie tous les sommets du cycle en fonction de la direction du chemin.

Lors de l'exécution de dfs, ce qui est recherché est le chemin dirigé du point de départ vers v. Le tableau onStack marque tous les sommets sur la pile de l'appel récursif, et le tableau edgeTo est également ajouté . Après avoir trouvé, renvoie tous les sommets de l'anneau lors du déplacement vers l'anneau

Tri topologique : étant donné un graphe orienté, triez tous les sommets de manière à ce que toutes les arêtes dirigées pointent des éléments à l'avant vers. les éléments à l'arrière. S'il y en a S'il s'agit d'un cyclique, alors le tri topologique ne peut pas être effectué

/**
 * 有向图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;
    }
}

Pour réaliser un tri topologique des graphiques orientés, la tâche peut être effectuée en utilisant la norme. ordre de recherche en profondeur d'abord. Il y aura trois arrangements de sommets ici Ordre :

1. Précommande : ajoutez les sommets à la file d'attente avant l'appel récursif

2. Postorder : ajoutez les sommets après l'appel récursif Ajouter à la file d'attente

3. Séquence inverse : poussez les sommets sur la pile après l'appel récursif <.>

Voir le code ci-dessous pour les opérations spécifiques :

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

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

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

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

 

前序就时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;
    }
}

 

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!