JavaScript 实现图数据结构

在计算机科学中，图是一种非常重要的数据结构，它由节点（顶点）和连接这些节点的边组成。图可以用来表示各种现实世界中的关系，如社交网络、地图路线等。在JavaScript中，我们可以通过多种方式来实现图数据结构。

我们可以使用邻接矩阵来表示图。邻接矩阵是一个二维数组，其中的元素表示节点之间是否存在边。如果节点i和节点j之间有边相连，那么邻接矩阵中第i行第j列的元素值为1，否则为0。以下是一个简单的JavaScript代码示例来创建和操作邻接矩阵表示的图：

class Graph {
    constructor(numVertices) {
        this.numVertices = numVertices;
        this.adjMatrix = new Array(numVertices).fill(0).map(() => new Array(numVertices).fill(0));
    }
    addEdge(v, w) {
        this.adjMatrix[v][w] = 1;
        this.adjMatrix[w][v] = 1;
    }
}

除了邻接矩阵，我们还可以使用邻接表来表示图。邻接表是一个数组，其中每个元素是一个链表，用于存储与该节点相邻的节点。使用邻接表可以更高效地表示稀疏图。以下是一个使用邻接表实现图的示例代码：

class Graph {
    constructor(numVertices) {
        this.numVertices = numVertices;
        this.adjList = new Array(numVertices).fill(null).map(() => []);
    }
    addEdge(v, w) {
        this.adjList[v].push(w);
        this.adjList[w].push(v);
    }
}

在实现了图数据结构后，我们还可以实现一些常见的图算法，如深度优先搜索（DFS）和广度优先搜索（BFS）。这些算法可以帮助我们遍历图、查找路径等。

例如，以下是一个简单的深度优先搜索算法的实现：

function dfs(graph, start, visited = {}) {
    visited[start] = true;
    console.log(start);
    for (let neighbor of graph.adjList[start]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

通过JavaScript实现图数据结构可以帮助我们更好地理解和处理各种复杂的关系。无论是使用邻接矩阵还是邻接表，都可以根据具体的应用场景选择合适的表示方法，并结合相关的算法来解决实际问题。