Implementación de Graph en JavaScript

En este artículo, estaríamos implementando la estructura de datos Graph en JavaScript. El gráfico es una estructura de datos no lineal. El gráfico G contiene un conjunto de vértices V y un conjunto de aristas E. Graph tiene muchas aplicaciones en informática. 
El gráfico se divide básicamente en dos grandes categorías: 
 

• Gráfico dirigido (dígrafo) : donde los bordes tienen dirección.
• Gráfico no dirigido: donde los bordes no representan ninguna dirección

Hay varias formas de representar un gráfico: – 
 

• Array de adyacencia
• Lista de adyacencia

Hay varias otras formas, como la array de incidencia, etc., pero estas dos son las más utilizadas. Consulte Graph y sus representaciones para obtener una explicación de la lista y la array de adyacencia.
En este artículo, usaríamos la Lista de adyacencia para representar un gráfico porque en la mayoría de los casos tiene cierta ventaja sobre la otra representación. 
Ahora veamos un ejemplo de la clase Graph. 
 

// create a graph class
class Graph {
    // defining vertex array and
    // adjacent list
    constructor(noOfVertices)
    {
        this.noOfVertices = noOfVertices;
        this.AdjList = new Map();
    }
 
    // functions to be implemented
 
    // addVertex(v)
    // addEdge(v, w)
    // printGraph()
 
    // bfs(v)
    // dfs(v)
}

El ejemplo anterior muestra un marco de la clase Graph . Definimos dos variables privadas, es decir, noOfVertices para almacenar el número de vértices en el gráfico y AdjList , que almacena una lista de adyacencia de un vértice en particular. Utilizamos un objeto de mapa proporcionado por ES6 para implementar la lista de adyacencia. Donde la clave de un mapa contiene un vértice y los valores contienen una array de un Node adyacente.
Ahora implementemos funciones para realizar operaciones básicas en el gráfico: 
 

• addVertex(v) – Agrega el vértice v como clave a adjList e inicializa sus valores con una array. 
   

// add vertex to the graph
addVertex(v)
{
    // initialize the adjacent list with a
    // null array
    this.AdjList.set(v, []);
}

• addEdge (src, dest) : agrega un borde entre src y dest . 
   

// add edge to the graph
addEdge(v, w)
{
    // get the list for vertex v and put the
    // vertex w denoting edge between v and w
    this.AdjList.get(v).push(w);
 
    // Since graph is undirected,
    // add an edge from w to v also
    this.AdjList.get(w).push(v);
}

• Para agregar borde, obtenemos la lista de adyacencia del vértice src correspondiente y agregamos el dest a la lista de adyacencia.
• printGraph() – Imprime vértices y su lista de adyacencia. 
   

// Prints the vertex and adjacency list
printGraph()
{
    // get all the vertices
    var get_keys = this.AdjList.keys();
 
    // iterate over the vertices
    for (var i of get_keys)
{
        // great the corresponding adjacency list
        // for the vertex
        var get_values = this.AdjList.get(i);
        var conc = "";
 
        // iterate over the adjacency list
        // concatenate the values into a string
        for (var j of get_values)
            conc += j + " ";
 
        // print the vertex and its adjacency list
        console.log(i + " -> " + conc);
    }
}

• Veamos un ejemplo de un gráfico.
   

Ahora usaremos la clase de gráfico para implementar el gráfico que se muestra arriba: 
 

// Using the above implemented graph class
var g = new Graph(6);
var vertices = [ 'A', 'B', 'C', 'D', 'E', 'F' ];
 
// adding vertices
for (var i = 0; i < vertices.length; i++) {
    g.addVertex(vertices[i]);
}
 
// adding edges
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'F');
g.addEdge('E', 'C');
g.addEdge('C', 'F');
 
// prints all vertex and
// its adjacency list
// A -> B D E
// B -> A C
// C -> B E F
// D -> A E
// E -> A D F C
// F -> E C
g.printGraph();

Gráfico transversal

Implementaremos el algoritmo de recorrido de grafos más común: 
 

• Recorrido primero en amplitud para un gráfico
• Primer recorrido de profundidad para un gráfico

Implementación de BFS y DFS: 
 

• bfs(startingNode) – Realiza la búsqueda primero en amplitud desde el Node inicial dado 
   

// function to performs BFS
bfs(startingNode)
{
 
    // create a visited object
    var visited = {};
 
    // Create an object for queue
    var q = new Queue();
 
    // add the starting node to the queue
    visited[startingNode] = true;
    q.enqueue(startingNode);
 
    // loop until queue is empty
    while (!q.isEmpty()) {
        // get the element from the queue
        var getQueueElement = q.dequeue();
 
        // passing the current vertex to callback function
        console.log(getQueueElement);
 
        // get the adjacent list for current vertex
        var get_List = this.AdjList.get(getQueueElement);
 
        // loop through the list and add the element to the
        // queue if it is not processed yet
        for (var i in get_List) {
            var neigh = get_List[i];
 
            if (!visited[neigh]) {
                visited[neigh] = true;
                q.enqueue(neigh);
            }
        }
    }
}

• En el método anterior, hemos implementado el algoritmo BFS. Se usa una cola para mantener los Nodes no visitados  . Usemos
  el método anterior y recorramos junto con el gráfico. 
   

// prints
// BFS
// A B D E C F
console.log("BFS");
g.bfs('A');

• El siguiente diagrama muestra el BFS en el gráfico de ejemplo:
   

• Complejidad temporal: O(V+E), donde V es el número de Nodes y E es el número de aristas.
• Espacio Auxiliar: O(V)

• dfs (startingNode) : realiza el recorrido de profundidad primero en un gráfico 
   

// Main DFS method
dfs(startingNode)
{
 
    var visited = {};
 
    this.DFSUtil(startingNode, visited);
}
 
// Recursive function which process and explore
// all the adjacent vertex of the vertex with which it is called
DFSUtil(vert, visited)
{
    visited[vert] = true;
    console.log(vert);
 
    var get_neighbours = this.AdjList.get(vert);
 
    for (var i in get_neighbours) {
        var get_elem = get_neighbours[i];
        if (!visited[get_elem])
            this.DFSUtil(get_elem, visited);
    }
}

• En el ejemplo anterior, dfs(startingNode) se usa para inicializar una array visitada, y DFSutil(vert,visited) 
  contiene la implementación del algoritmo DFS  . Usemos
  el método anterior para recorrer junto con el gráfico. 
   

// prints
// DFS
// A B C E D F
console.log("DFS");
g.dfs('A');

• El siguiente diagrama muestra el DFS en el gráfico de ejemplo 
   

Complejidad temporal:  O(V + E), donde V es el número de vértices y E es el número de aristas del gráfico.

Espacio Auxiliar: O(V), ya que se requiere un arreglo extra visitado de tamaño V.

Este artículo es una contribución de Sumit Ghosh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.