JavaScript 中图的实现

图是一种非线性数据结构，表示一组顶点（也称为节点）以及它们之间的关系（或边）。顶点表示实体或对象，而边表示顶点之间的关系或连接。图可用于对许多不同类型的关系进行建模，例如社交网络、交通系统或信息流。,图有两种主要类型：有向图（也称为有向图）和无向图。在有向图中，边有一个方向，并且只能在一个方向上遍历，即从起始顶点到结束顶点。在无向图中，边没有方向，可以在两个方向上遍历。,图可以使用邻接矩阵或邻接列表来实现。在这里，我们将使用邻接列表在 JavaScript 中实现图形。,这里我们创建了图形类的蓝图。,登录后复制,该函数通过在 adjacencyList 对象中创建一个新键并将空数组作为其值来向图中添加一个新顶点（或节点）。新顶点将作为键，空数组将用于存储其邻居。,登录后复制,此函数在两个顶点之间添加一条新边。它接受两个参数：vertex1 和 vertex2，并将 vertex2 添加到 vertex1 的邻居数组中，反之亦然。这会在两个顶点之间创建连接。,登录后复制,此函数将图表记录到控制台。它迭代 adjacencyList 对象中的每个顶点并记录该顶点及其邻居。,登录后复制,在下面的示例中，我们定义一个图并向该图添加顶点和边。最后打印图表。,登录后复制,登录后复制,此函数删除两个顶点之间的边。它接受两个参数：vertex1 和 vertex2，并从 vertex1 的邻居数组中过滤掉 vertex2，反之亦然。,登录后复制,该函数从图中删除一个顶点。它接受一个顶点参数，并首先删除连接到该顶点的所有边。然后，它从 adjacencyList 对象中删除该键。,登录后复制,在下面的示例中，我们定义一个图并添加顶点和边，然后打印该图。我们从图中删除一条边 AC，最后打印结果图。,登录后复制,登录后复制,图遍历是指访问图的所有顶点（或节点）并处理与其关联的信息的过程。图遍历是图算法中的重要操作，用于查找两个节点之间的最短路径、检测环路、查找连通分量等任务。,图遍历主要有两种方法：广度优先搜索（BFS）和深度优先搜索（DFS）,它是使用breadthFirstSearch()函数实现的。该函数实现广度优先搜索算法并采用 start 参数，即起始顶点。它使用队列来跟踪要访问的顶点，使用结果数组来存储访问过的顶点，并使用访问对象来跟踪已经访问过的顶点。该函数首先将起始顶点添加到队列中并将其标记为已访问。然后，当队列不为空时，它从队列中取出第一个顶点，将其添加到结果数组中，并将其标记为已访问。然后它将所有未访问的邻居添加到队列中。这个过程一直持续到所有顶点都被访问过，并且结果数组作为 BFS 的结果返回。,登录后复制,深度优先搜索方法通过使用以顶点作为参数的递归内部函数 dfs 来实现 DFS 算法。该函数使用访问的对象来跟踪访问的顶点，并将每个访问的顶点添加到结果数组中。该函数首先将当前顶点标记为已访问并将其添加到结果数组中。然后，它迭代当前顶点的所有邻居，并为每个未访问的邻居递归调用 dfs 函数。该过程一直持续到所有顶点都被访问过并且结果数组作为 DFS 的结果返回。,登录后复制,在下面的示例中，我们演示了广度优先搜索（BFS）和深度优先搜索（DFS）。,登录后复制,登录后复制,图是一种有用的数据结构，可用于表示对象之间的关系和连接。在 JavaScript 中实现图可以使用多种技术来完成，包括使用邻接列表或邻接矩阵。本答案中演示的 Graph 类使用邻接列表表示形式，其中每个顶点都作为键存储在对象中，其相应的边作为该键的值存储在数组中。,Graph 类实现了向图形添加顶点和边、打印图形以及执行深度优先搜索和广度优先搜索遍历的方法。,以上就是JavaScript 中图的实现的详细内容，更多请关注www.92cms.cn其它相关文章！