Definición del diagrama
El gráfico está compuesto por un conjunto finito no vacío de vértices y un conjunto de bordes entre vértices. Por lo general, se representa como: G (V, E), donde G representa un gráfico, V es el conjunto de vértices en el Gráfico G y E es el conjunto de bordes en Graph G.
Gráfico dirigido
Borde dirigido: si el borde del vértice VI a VJ tiene una dirección, este borde se llama borde dirigido, que también se convierte en un arco (arco). Está representado por un <VI, vj>. VI se llama la cola del arco y VJ se llama cabeza de arco.
Diagrama desordenado
Edge no dirigido: si el borde entre los vértices VI a VJ no tiene dirección, este borde se llama borde no dirigido (borde) y está representado por un par desordenado (VI, VJ).
Imagen simple
Diagrama simple: en la estructura del gráfico, si no hay vértice en su propio borde y el mismo borde no aparece repetidamente, esta imagen se llama diagrama simple.
Clase de imágenes
Indica un vértice
El primer paso para crear una clase gráfica es crear una clase de vértice para guardar vértices y bordes. Esta clase funciona igual que la clase de nodo de listas vinculadas y árboles de búsqueda binarios. La clase de vértice tiene dos miembros de datos: uno para identificar el vértice y el otro para indicar si se ha accedido. Se llaman etiqueta y fueron visitadas respectivamente.
La copia del código es la siguiente:
función vértice (etiqueta) {
this.label = etiqueta;
}
Guardamos todos los vértices en una matriz, y en la clase de gráficos, podemos referirnos a ellos por su posición en la matriz
Indica borde
La información real del gráfico se almacena en el "borde" porque describen la estructura del gráfico. Un nodo principal de un árbol binario solo puede tener dos nodos infantiles, pero la estructura del gráfico es mucho más flexible. Un vértice puede tener un borde o múltiples bordes conectados a él.
Utilizaremos el método para representar los bordes del gráfico para convertirse en una tabla de adyacencia o una matriz de tabla de adyacencia. Almacenará una matriz compuesta por una lista de vértices adyacentes de vértices
Construir un gráfico
Defina la siguiente clase de gráfico:
La copia del código es la siguiente:
Gráfico de funciones (v) {
this.vertices = v; // vértices al punto alto
this.edges = 0;
this.adj = [];
para (var i = 0; i <this.vertices; ++ i) {
this.adj [i] = [];
this.adj [i] .push ('');
}
this.addedge = adicional;
this.ToString = toString;
}
Esta clase registra cuántos bordes representa un gráfico y utiliza una longitud y el número de vértices del gráfico para registrar el número de vértices.
La copia del código es la siguiente:
función adicional () {
this.adj [v] .push (w);
this.adj [w] .push (v);
this.edges ++;
}
Aquí usamos un bucle for para agregar una subarrray para cada elemento en la matriz para almacenar todos los vértices adyacentes e inicializar todos los elementos en cadenas vacías.
El recorrido de la imagen
Traversal de prioridad de profundidad
DropeFirstSearch, también conocido como DropeFirstSearch, se conoce como DFS para abreviar.
Por ejemplo, en busca de una llave en una habitación, sin importar qué habitación comience, puede buscar las esquinas de la habitación, mesas de noche, mesas de noche, debajo de camas, armarios, gabinetes de televisión, etc. uno por uno, para no perderse ningún punto ciego. Después de buscar todos los cajones y gabinetes de almacenamiento, luego busque la siguiente habitación.
Búsqueda de prioridad de profundidad:
La búsqueda de profundidad primero significa acceder a un vértice que no se ha visitado, marcarlo como se accede y luego acceder recursivamente a otros vértices que no se han visitado en la tabla de adyacencia del vértice inicial.
Agregue una matriz a la clase de gráfico:
La copia del código es la siguiente:
this.marked = []; // Guardar los vértices visitados
para (var i = 0; i <this.vertices; ++ i) {
this.marked [i] = false; // inicializar a falso
}
Función de búsqueda de profundidad primero:
La copia del código es la siguiente:
función dfs (v) {
this.marked [v] = true;
// Si la declaración no es necesaria aquí
if (this.adj [v]! = Undefined) {
imprimir ("Vértice visitado:" + V);
para cada (var w w en this.adj [v]) {
if (! this.marked [w]) {
this.dfs (w);
}
}
}
}
Búsqueda de la primera
Broadness-First Search (BFS) es un método de búsqueda a ciegas, con el propósito de expandir y examinar sistemáticamente todos los nodos en el gráfico para encontrar resultados. En otras palabras, no tiene en cuenta la posible ubicación del resultado y busca la imagen completa a fondo hasta que se encuentre el resultado.
La búsqueda de amplitud primera comienza con el primer vértice e intente acceder al vértice lo más cerca posible, como se muestra en la siguiente figura:
Su principio de trabajo es:
1. Primero encuentre vértices no alcanzados adyacentes al vértice actual y agréguelos a la lista de vértices visitados y la cola;
2. Luego, saque el siguiente vértice V del gráfico y agréguelo a la lista de vértices visitados
3. Finalmente, agregue todos los vértices no visitados adyacentes a V a la cola
La siguiente es la definición de la función de búsqueda de amplitud:
La copia del código es la siguiente:
función bfs (s) {
var queue = [];
this.marked = true;
Queue.push (s); // Agregar al final de la cola
while (queue.length> 0) {
var v = queue.shift (); // Eliminar del líder del equipo
if (v == indefinido) {
imprimir ("Vértice visitado:" + V);
}
para cada (var w w en this.adj [v]) {
if (! this.marked [w]) {
this.Edgeto [W] = V;
this.marked [w] = true;
cola.push (w);
}
}
}
}
El camino más corto
Al realizar una búsqueda de amplitud primera, la ruta más corta de un vértice a otro vértice conectado se encuentra automáticamente
Determinar el camino
Para encontrar la ruta más corta, necesitamos modificar el algoritmo de búsqueda de amplitud primero para grabar la ruta de un vértice a otro. Necesitamos una matriz para guardar todos los bordes del siguiente vértice de un vértice. Nombramos esta matriz edgeto
La copia del código es la siguiente:
this.Edgeto = []; // Agregar esta línea a la clase Graph
// función bfs
función bfs (s) {
var queue = [];
this.marked = true;
Queue.push (s); // Agregar al final de la cola
while (queue.length> 0) {
var v = queue.shift (); // Eliminar del líder del equipo
if (v == indefinido) {
imprimir ("Vértice visitado:" + V);
}
para cada (var w w en this.adj [v]) {
if (! this.marked [w]) {
this.Edgeto [W] = V;
this.marked [w] = true;
cola.push (w);
}
}
}
}
Algoritmo de clasificación topológica
La clasificación topológica clasifica todos los vértices de un gráfico dirigido, de modo que los bordes dirigidos apuntan desde el vértice delantero hasta el vértice posterior.
El algoritmo de clasificación topológico es similar al BFS. La diferencia es que el algoritmo de clasificación topológico no genera los vértices accedidos de inmediato, sino que accede a todos los vértices adyacentes en la tabla adyacente del vértice actual. Hasta que esta lista esté agotada, el vértice actual no será empujado a la pila.
El algoritmo de clasificación topológico se divide en dos funciones. La primera función es TopSort (), que se utiliza para establecer el proceso de clasificación y llamar a una función de ayuda topSorthelper (), y luego mostrar la lista de vértices ordenados.
El trabajo principal del algoritmo de clasificación de topología se realiza en la función recursiva TopSorthelper (), que marca el vértice actual, y luego accede recursivamente a cada vértice en la tabla de adyacencia del vértice actual, marcando estos vértices a los que se accede. Finalmente, empuje el vértice actual en la pila.
La copia del código es la siguiente:
// función topsort ()
function topSort () {
var stack = [];
var visitado = [];
para (var i = 0; i <this.vertices; i ++) {
visitado [i] = falso;
}
para (var i = 0; i <this.vertices; i ++) {
if (visitado [i] == falso) {
this.topSorthelper (i, visitado, pila);
}
}
para (var i = 0; i <stack.length; i ++) {
if (stack [i]! = Undefined && stack [i]! = false) {
imprimir (this.vertexlist [pila [i]]);
}
}
}
// función topsorthelper ()
función topSorthelper (V, visitado, pila) {
visitado [v] = true;
para cada (var w w en this.adj [v]) {
if (! Visited [W]) {
this.topSorthelper (visitado [w], visitado, pila);
}
}
stack.push (v);
}