Реализация Graph в JavaScript

Опубликовано: 14 Декабря, 2021

В этой статье мы будем реализовывать структуру данных Graph в JavaScript. График - это нелинейная структура данных. Граф G содержит набор вершин V и множество ребер E. Граф имеет множество приложений в информатике.
Граф в основном делится на две большие категории:

Направленный график (диаграмма) - где ребра имеют направление.
Ненаправленный граф - где ребра не представляют никаких направленных

Есть несколько способов представить график: -

Матрица смежности
Список смежности

Есть несколько других способов, таких как матрица инцидентности и т. Д., Но эти два используются чаще всего. Обратитесь к Графику и его представлениям для объяснения матрицы и списка смежности.
В этой статье мы будем использовать список смежности для представления графа, потому что в большинстве случаев он имеет определенное преимущество перед другим представлением.
Теперь давайте посмотрим на пример класса Graph -

JavaScript

 // 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)
 }

В приведенном выше примере показана структура класса Graph. Мы определяем две закрытые переменные, то есть noOfVertices для хранения количества вершин в графе и AdjList , в котором хранится список смежности конкретной вершины. Мы использовали объект карты, предоставленный ES6, чтобы реализовать список смежности. Где ключ карты содержит вершину, а значения - массив соседнего узла.
Теперь реализуем функции для выполнения основных операций над графиком:

addVertex (v) - добавляет вершину v в качестве ключа в adjList и инициализирует ее значения с помощью массива.

JavaScript

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

addEdge (src, dest) - добавляет границу между src и dest .

JavaScript

// 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);
}

Чтобы добавить ребро, мы получаем список смежности соответствующей вершины src и добавляем цель в список смежности.
printGraph () - печатает вершины и их список смежности.

JavaScript

// 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);
    }
}

Давайте посмотрим на пример графика

Теперь мы будем использовать класс графа для реализации графа, показанного выше:

JavaScript

 // 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 -> BDE
 // B -> AC
 // C -> BEF
 // D -> AE
 // E -> ADFC
 // F -> EC
 g.printGraph();

Обход графа

Мы реализуем наиболее распространенный алгоритм обхода графа:

Первый обход графа в ширину
Обход графа в глубину

Реализация BFS и DFS:

bfs (startNode) - выполняет поиск в ширину от данного начального узла

JavaScript

 // 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 element
    while (!q.isEmpty()) {
        // get the element from the queue
        var getQueueElement = q.dequeue();
 
        // passing the current vertex to callback funtion
        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);
            }
        }
    }
 }

В описанном выше методе мы реализовали алгоритм BFS. Очередь используется для хранения непосещенных узлов
Воспользуемся описанным выше методом и пройдемся по графику.

JavaScript

 // prints
 // BFS
 // ABDECF
 console.log( "BFS" );
 g.bfs( 'A' ); 

На диаграмме ниже показана BFS на примере графика:

dfs (startNode) - выполняет первый обход глубины на графике

JavaScript

 // 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);
    }
 }

В приведенном выше примере dfs (startNode) используется для инициализации массива посещений и DFSutil (vert, посещено)
содержит реализацию алгоритма DFS
Давайте воспользуемся описанным выше методом для перемещения по графику.

JavaScript

 // prints
 // DFS
 // ABCEDF
 console.log( "DFS" );
 g.dfs( 'A' ); 

На диаграмме ниже показана DFS на примере графика.

Эта статья предоставлена Сумитом Гошем . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью с помощью provide.geeksforgeeks.org или отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

JavaScript

Реализация Graph в JavaScript

JavaScript

JavaScript

JavaScript

JavaScript

JavaScript

JavaScript

JavaScript

JavaScript

JavaScript

РЕКОМЕНДУЕМЫЕ СТАТЬИ