Clasificación topológica
La clasificación topológica de un gráfico acíclico dirigido (DAG para abreviar) G consiste en organizar todos los vértices de G en una secuencia lineal, de modo que cualquier par de vértices u y v en el gráfico, si Edge lt; u, vgt; ∈ E(G), entonces u aparece antes de v en la secuencia lineal. Por lo general, dicha secuencia lineal se denomina secuencia que satisface el orden topológico, o se denomina secuencia topológica. En pocas palabras, desde un orden parcial en un determinado conjunto hasta un orden total en el conjunto, esta operación se denomina clasificación topológica.
Un proyecto más grande a menudo se divide en muchos subproyectos y los proyectos dependen unos de otros, como los proyectos A, B y C. El proyecto A comienza a depender de B para su finalización y B comienza a depender de C para su finalización. Si desea completar el proyecto, debe ejecutarlo en el orden C-gt.
Sin embargo, una vez que se agrega la condición de que C depende de A, se formará una estructura de anillo C-gt; B-A-gt;
La clasificación topológica puede convertir un gráfico dirigido en un gráfico dirigido lineal para comprobar visualmente si hay una estructura de anillo en el gráfico dirigido.
Grado de entrada: el grado de entrada de un vértice se basa en esto El número de aristas dirigidas con el vértice como punto final
Grado exterior: el grado de entrada de un vértice es el número de aristas dirigidas con el vértice como punto inicial
Por ejemplo:
A-gt; B, el grado de entrada de B es 1 y el grado de salida de A es 1
Si todo el programa del curso El gráfico es un gráfico acíclico dirigido (es decir, se puede programar), entonces todos los nodos deben estar en la cola Y fuera de la cola, es decir, se completa la clasificación topológica. Para decirlo de otra manera, si hay un ciclo en el gráfico dirigido, debe haber un nodo cuyo grado de entrada no sea 0.
Por lo tanto, el número de colas en la clasificación topológica es igual al número de nodos y se devuelve num == 0 para determinar si el curso se puede organizar con éxito.
Aquí utilizamos un conjunto de diagramas que se encuentran en Internet para ilustrar:
Durante el proceso de recorrido de la tabla en grados, las listas de adyacencia, el almacenamiento de la matriz de adyacencia y la relación de conectividad entre cualquier A menudo se utilizan dos vértices para encontrar el nodo crítico correspondiente al nodo actual en tiempo constante, así como el grado de entrada y salida entre el nodo actual y el nodo adyacente.
Utilice un. bandera enumera banderas para determinar cada nodo i (curso) Estado:
Ejecute DFS en num nodos en secuencia y determine si hay un bucle en el DFS inicial de cada nodo. Si existe un bucle, Falso es. Regresó directamente. Proceso DFS;
Para casos específicos, consulte aquí: Horario del curso