实现图数据结构：添加和删除边与顶点

背景简介

在数据结构的学习中，图是一种复杂但非常重要的结构。图由顶点（节点）和连接这些顶点的边组成，可以用来表示多种复杂的关系网络。在本章中，我们将深入探讨如何通过编程实现图，并详细学习如何在图中添加和删除顶点与边。

添加边和顶点

为了在图中添加边和顶点，我们首先定义了一个无向图类 UndirectedGraph 。此类使用一个对象来存储边，该对象中的每个键值对代表一个顶点及其相邻顶点的集合。通过以下代码实现添加顶点和边：

function UndirectedGraph() {
    this.edges = {};
}

UndirectedGraph.prototype.addVertex = function(vertex) {
    this.edges[vertex] = {};
}

UndirectedGraph.prototype.addEdge = function(vertex1, vertex2, weight) {
    if (weight === undefined) {
        weight = 0;
    }
    this.edges[vertex1][vertex2] = weight;
    this.edges[vertex2][vertex1] = weight;
}

使用上述类和方法，我们能够创建一个图，并向其中添加顶点和边。例如：

var graph1 = new UndirectedGraph();
graph1.addVertex(1);
graph1.addVertex(2);
graph1.addEdge(1, 2, 1);

移除边和顶点

在图的操作中，有时候我们需要从图中移除顶点或边。移除边的函数 removeEdge 会检查边是否存在，并使用JavaScript的 delete 操作符来删除。移除顶点的函数 removeVertex 则需要删除与该顶点相关联的所有边，并最终删除顶点本身：

UndirectedGraph.prototype.removeEdge = function(vertex1, vertex2) {
    // 删除边的代码略
}

UndirectedGraph.prototype.removeVertex = function(vertex) {
    for (var adjacentVertex in this.edges[vertex]) {
        this.removeEdge(adjacentVertex, vertex);
    }
    delete this.edges[vertex];
}

有向图

与无向图类似，有向图也由顶点和边组成，但边是有方向的。这意味着在有向图中，边从一个顶点指向另一个顶点。有向图的实现与无向图类似，但在添加边时，权重仅在起始顶点设置：

function DirectedGraph() {
    this.edges = {};
}

DirectedGraph.prototype.addVertex = function(vertex) {
    this.edges[vertex] = {};
}

DirectedGraph.prototype.addEdge = function(origVertex, destVertex, weight) {
    if (weight === undefined) {
        weight = 0;
    }
    this.edges[origVertex][destVertex] = weight;
}

图遍历

图遍历是图算法中的核心部分，用于访问图中的每个顶点。遍历图的方法主要有两种：广度优先搜索（BFS）和深度优先搜索（DFS）。BFS从根节点开始，逐层访问每个节点的邻居，而DFS则尽可能深地遍历图的分支。

总结与启发

通过本章的学习，我们了解了图数据结构在编码实现中的具体操作，包括添加和删除顶点与边的方法，以及图的遍历策略。这些知识对于解决实际中的复杂关系网络问题至关重要，无论是在社交网络分析、网络路由，还是在图形用户界面布局等领域中都有广泛的应用。

图数据结构的灵活性和表达能力使得它成为解决许多实际问题的有力工具。掌握如何在图中进行有效的遍历和修改，无疑将为你的编程技能库增添一项宝贵的资产。希望本章的内容能够激发你对图数据结构更深层次的探索和应用。