JavaScript中图形的实现-yiteyi-C++库

在本文中，我们将实现图形数据结构在JavaScript中。该图是一种非线性数据结构。图表 G 包含一组顶点五、还有一组边 E .图在计算机科学中有很多应用。 图表基本上分为两大类：

null

有向图（Di图） –边缘有方向。
无向图 –如果边缘不代表任何方向

有多种表示图形的方法：-

邻接矩阵
邻接表

还有其他几种方法，如关联矩阵等，但这两种方法是最常用的。提到图及其表示用于解释邻接矩阵和列表。在本文中，我们将使用 邻接表 表示图形，因为在大多数情况下，它比其他表示法有一定的优势。现在我们来看一个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)                         
                           }                         

上面的例子展示了一个图表班我们定义了两个私有变量，即 无生气 存储图形中的顶点数，并 形容词列表 ，它存储特定顶点的邻接列表。我们使用了地图对象，以实现邻接列表。其中，贴图的键包含一个顶点，值包含一个相邻节点的数组。现在，让我们实现函数来执行图形上的基本操作：

addVertex（v） –它会添加顶点五、作为 形容词列表 并用数组初始化其值。

JavaScript

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

附录（src、dest） –它在两条线之间增加了一条边 src 和 目的地 .

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

让我们看一个图表的例子

Graph Example

现在我们将使用graph类来实现上面所示的图形：

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 -> B D E                         
                           // B -> A C                         
                           // C -> B E F                         
                           // D -> A E                         
                           // E -> A D F C                         
                           // F -> E C                         
                           g.printGraph();                         

图的遍历

我们将实现最常见的图遍历算法：

BFS和DFS的实施：

bfs（启动节点） –它从给定的目标执行广度优先搜索 启动节点

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

在上述方法中，我们实现了BFS算法。A. 队列用于保持未访问的节点让我们使用上面的方法，沿着图进行遍历

JavaScript

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

下图显示了示例图上的BFS：

BFS on Graph

dfs（启动节点） –它在图形上执行深度优先遍历

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（启动节点） 用于初始化已访问的数组，以及 DFSutil（垂直，已访问） 包含DFS算法的实现让我们使用上面的方法沿着图形进行遍历

JavaScript

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

下图显示了示例图上的DFS

DFS on Graph

本文由 苏米特·戈什 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

Javascript