JavaScript 图

图的基本概念

图是一种数据结构，它由一组顶点和一组能够将这些顶点配对的边组成。图可以用来表示各种各样的关系网，比如社交网络、网页链接结构、电路网络等。

顶点与边

• 顶点：图中的基本元素，通常用一个点或一个圆圈表示。
• 边：连接两个顶点的线，可以是有向的也可以是无向的。有向边表示从一个顶点到另一个顶点的单向关系，无向边则表示双向关系。

图的类型

根据边是否有方向性，图可以分为两类：

• 无向图：边没有方向性的图。
• 有向图：边具有方向性的图。

图的存储方式

在计算机中，图可以通过不同的方式来存储，以便于算法处理。以下是几种常见的存储方法：

邻接矩阵

邻接矩阵是一种使用二维数组来表示图的方法。如果图中有n个顶点，则邻接矩阵是一个n×n的矩阵。矩阵的行和列分别代表图中的顶点，矩阵中的每个元素表示对应的两个顶点之间是否存在边。

示例代码

// www.javascriptcn.com code example
class Graph {
    constructor(vertices) {
        this.vertices = vertices;
        this.adjMatrix = Array.from({length: vertices}, () => new Array(vertices).fill(0));
    }

    addEdge(v, w) {
        this.adjMatrix[v][w] = 1;
        this.adjMatrix[w][v] = 1; // 如果是无向图，则需要添加反向边
    }

    display() {
        for (let i = 0; i < this.vertices; i++) {
            for (let j = 0; j < this.vertices; j++) {
                process.stdout.write(this.adjMatrix[i][j] + " ");
            }
            console.log();
        }
    }
}

邻接表

邻接表是一种使用数组来存储图的方法。数组的每个元素都是一个链表，链表中的每个节点都对应一个邻接顶点。

示例代码

// www.javascriptcn.com code example
class Graph {
    constructor(vertices) {
        this.vertices = vertices;
        this.adjList = new Map();
    }

    addVertex(v) {
        if (!this.adjList.has(v)) {
            this.adjList.set(v, []);
        }
    }

    addEdge(v, w) {
        this.adjList.get(v).push(w);
        this.adjList.get(w).push(v); // 如果是无向图，则需要添加反向边
    }

    display() {
        this.adjList.forEach((vertices, key) => {
            let adjVertices = vertices.join(" ");
            console.log(`${key} -> ${adjVertices}`);
        });
    }
}

图的遍历

图的遍历是指访问图中的每一个顶点，且每个顶点仅被访问一次。常见的图遍历算法有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

深度优先搜索通过递归的方式访问图中的顶点。首先访问一个起始顶点，然后递归地访问该顶点的所有未访问过的邻接顶点。

示例代码

// www.javascriptcn.com code example
function dfs(graph, startVertex) {
    const visited = new Set();

    function dfsRecursive(vertex) {
        if (!visited.has(vertex)) {
            console.log(vertex);
            visited.add(vertex);
            const neighbors = graph.adjList.get(vertex);

            for (const neighbor of neighbors) {
                dfsRecursive(neighbor);
            }
        }
    }

    dfsRecursive(startVertex);
}

// 使用示例
const g = new Graph(6);
const vertices = ["A", "B", "C", "D", "E", "F"];
for (let i = 0; i < vertices.length; i++) {
    g.addVertex(vertices[i]);
}

const edges = [
    ["A", "B"], ["A", "D"],
    ["B", "C"], ["B", "D"],
    ["C", "D"], ["D", "E"],
    ["E", "F"]
];

edges.forEach(edge => g.addEdge(edge[0], edge[1]));

dfs(g, "A");

广度优先搜索（BFS）

广度优先搜索通过队列的方式逐层访问图中的顶点。首先访问起始顶点，然后依次访问其所有未访问过的邻接顶点，之后再访问这些邻接顶点的所有未访问过的邻接顶点，以此类推。

示例代码

// www.javascriptcn.com code example
function bfs(graph, startVertex) {
    const visited = new Set();
    const queue = [];

    queue.push(startVertex);
    visited.add(startVertex);

    while (queue.length > 0) {
        const vertex = queue.shift();
        console.log(vertex);

        const neighbors = graph.adjList.get(vertex);

        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

// 使用示例
bfs(g, "A");

最短路径算法

图中的最短路径问题是指找到从一个顶点到另一个顶点的最短路径。常见的最短路径算法包括Dijkstra算法和Bellman-Ford算法。

Dijkstra算法

Dijkstra算法用于求解加权图中从一个顶点到其他所有顶点的最短路径。它通过维护一个距离表来记录从起始顶点到其他顶点的距离，并逐步更新这些距离值。

示例代码

// www.javascriptcn.com code example
function dijkstra(graph, startVertex) {
    const distances = {};
    const previous = {};

    // 初始化距离表
    for (const vertex of graph.adjList.keys()) {
        distances[vertex] = Infinity;
        previous[vertex] = null;
    }
    distances[startVertex] = 0;

    const unvisited = new Set(graph.adjList.keys());

    while (unvisited.size > 0) {
        let currentVertex = null;
        let smallestDistance = Infinity;

        for (const vertex of unvisited) {
            if (distances[vertex] < smallestDistance) {
                smallestDistance = distances[vertex];
                currentVertex = vertex;
            }
        }

        unvisited.delete(currentVertex);

        const neighbors = graph.adjList.get(currentVertex);

        for (const neighbor of neighbors) {
            const tentativeDist = distances[currentVertex] + 1; // 假设权重为1

            if (tentativeDist < distances[neighbor]) {
                distances[neighbor] = tentativeDist;
                previous[neighbor] = currentVertex;
            }
        }
    }

    return {distances, previous};
}

// 使用示例
const result = dijkstra(g, "A");
console.log(result.distances);

以上是关于JavaScript中图的基础知识、存储方式、遍历算法以及最短路径算法的详细介绍。希望这些内容能够帮助您更好地理解和应用图的相关概念和技术。