OpenDSA 全教程

Chapter 19 Graphs

| 关于   «  1. 图章引论   ::   目录   ::   3. 图遍历  »

2. 图的实现

接下来我们讨论实现通用 图 类的问题。 有两种传统的图表示方法： 邻接矩阵 和 邻接表。 在本模块中，我们将展示每种方法的实际实现。 我们将首先定义图的 ADT 接口， 给定的实现必须满足此接口。

interface Graph { // Graph class ADT
  // Initialize the graph with some number of vertices
  void init(int n);

  // Return the number of vertices
  int nodeCount();

  // Return the current number of edges
  int edgeCount();

  // Get the value of node with index v
  int getValue(int v);

  // Set the value of node with index v
  void setValue(int v, int val);
  
  // Adds a new edge from node v to node w with weight wgt
  void addEdge(int v, int w, int wgt);

  // Get the weight value for an edge
  int weight(int v, int w);

  // Removes the edge from the graph.
  void removeEdge(int v, int w);

  // Returns true iff the graph has the edge
  boolean hasEdge(int v, int w);

  // Returns an array containing the indicies of the neighbors of v
  int[] neighbors(int v);
}

interface Graph { // Graph class ADT
  // Initialize the graph with some number of vertices
  void init(int n);

  // Return the number of vertices
  int nodeCount();

  // Return the current number of edges
  int edgeCount();

  // Get the value of node with index v
  Object getValue(int v);

  // Set the value of node with index v
  void setValue(int v, Object val);
  
  // Adds a new edge from node v to node w with weight wgt
  void addEdge(int v, int w, int wgt);

  // Get the weight value for an edge
  int weight(int v, int w);

  // Removes the edge from the graph.
  void removeEdge(int v, int w);

  // Returns true iff the graph has the edge
  boolean hasEdge(int v, int w);

  // Returns an array containing the indicies of the neighbors of v
  int[] neighbors(int v);
}

此 ADT 假定图创建时顶点数是固定的， 但可以添加和删除边。 init 方法设置（或重置）图中的节点数， 并为邻接矩阵或邻接表创建必要的空间。

顶点由整数索引值定义。 换句话说，有顶点 0、顶点 1，一直到顶点 \(n-1\)。 我们可以假设图的客户端应用程序将有关给定顶点的 任何其他感兴趣的信息存储在其他地方， 例如名称或依赖于应用程序的值。 请注意，在 Java 或 C++ 这样的语言中， 此 ADT 不会使用泛型或模板等语言特性来实现， 因为 Graph 类的用户负责维护与顶点本身相关的信息。 Graph 类不需要知道与顶点关联的信息的类型或内容， 只需要知道该顶点的索引号。

接口 Graph 具有返回顶点和边数量的方法 （分别为方法 n 和 e）。 函数 weight 返回给定边的权值， 该边由其两个关联顶点标识。 例如，在图 19.1.1 (c) 上调用 weight(0, 4) 将返回 4。 如果不存在这样的边，则权值定义为 0。 因此在图 19.1.1 (c) 上调用 weight(0, 2) 将返回 0。

函数 addEdge 和 removeEdge 分别向图中 添加边（设置其权值）和删除边。 同样，边由其两个关联顶点标识。 addEdge 不允许用户将权值设置为 0， 因为此值用于表示不存在的边， 也不允许负的边权值。 函数 getValue 和 setValue 分别 获取和设置顶点 \(v\) 的请求值。 在我们的示例应用中，这些方法最频繁的用途 是指示给定节点在算法过程中是否已被访问过。

本章中介绍的几乎每个图算法都需要 访问给定顶点的所有邻居。 neighbors 方法返回一个数组， 其中包含相邻顶点的索引（按升序排列）。 以下几行出现在许多图算法中。

  int[] nList = G.neighbors(v);
  for (int i=0; i< nList.length; i++) {
    if (G.getValue(nList[i]) != VISITED) {
      DoSomething();
    }
  }

  int[] nList = G.neighbors(v);
  for (int i=0; i< nList.length; i++) {
    if (G.getValue(nList[i]) != VISITED) {
      DoSomething();
    }
  }

首先，生成一个数组，包含可以从节点 v 直接到达的节点的索引。 然后 for 循环遍历此邻居数组， 对每个邻居执行某个函数。

使用邻接表或邻接矩阵实现我们的图 ADT 是相当直接的。 这里提供的示例实现没有解决 图实际如何创建的问题。 这些实现的用户必须为此目的添加功能， 也许从文件读取图描述。 图可以使用 ADT 提供的 addEdge 函数构建。

以下是邻接矩阵的实现。

class GraphM implements Graph {
  private int[][] matrix;
  private int[] nodeValues;
  private int numEdge;

  // No real constructor needed
  GraphM() { }

  // Initialize the graph with n vertices
  public void init(int n) {
    matrix = new int[n][n];
    nodeValues = new int[n];
    numEdge = 0;
  }

  // Return the number of vertices
  public int nodeCount() { return nodeValues.length; }

  // Return the current number of edges
  public int edgeCount() { return numEdge; }
  
  // Get the value of node with index v
  public int getValue(int v) { return nodeValues[v]; }
  
  // Set the value of node with index v
  public void setValue(int v, int val) { nodeValues[v] = val; }

  // Adds a new edge from node v to node w
  // Returns the new edge
  public void addEdge(int v, int w, int wgt) {
    if (wgt == 0) { return; } // Can't store weight of 0
    if (matrix[v][w] == 0) {
      numEdge++;
    }
    matrix[v][w] = wgt;
  }

  // Get the weight value for an edge
  public int weight(int v, int w) { return matrix[v][w]; }

  // Removes the edge from the graph.
  public void removeEdge(int v, int w) {
    if (matrix[v][w] != 0) {
      matrix[v][w] = 0;
      numEdge--;
    }
  }
  
  // Returns true iff the graph has the edge
  public boolean hasEdge(int v, int w) { return matrix[v][w] != 0; }

  // Returns an array containing the indicies of the neighbors of v
  public int[] neighbors(int v) {
    int i;
    int count = 0;
    int[] temp;
    
    for (i=0; i<nodeValues.length; i++) {
      if (matrix[v][i] != 0) { count++; }
    }
    temp = new int[count];
    for (i=0, count=0; i<nodeValues.length; i++) {
      if (matrix[v][i] != 0) { temp[count++] = i; }
    }
    return temp;
  }
}

class GraphM implements Graph {
  private int[][] matrix;
  private Object[] nodeValues;
  private int numEdge;

  // No real constructor needed
  GraphM() { }

  // Initialize the graph with n vertices
  public void init(int n) {
    matrix = new int[n][n];
    nodeValues = new Object[n];
    numEdge = 0;
  }

  // Return the number of vertices
  public int nodeCount() { return nodeValues.length; }

  // Return the current number of edges
  public int edgeCount() { return numEdge; }
  
  // Get the value of node with index v
  public Object getValue(int v) { return nodeValues[v]; }
  
  // Set the value of node with index v
  public void setValue(int v, Object val) { nodeValues[v] = val; }

  // Adds a new edge from node v to node w
  // Returns the new edge
  public void addEdge(int v, int w, int wgt) {
    if (wgt == 0) { return; } // Can't store weight of 0
    if (matrix[v][w] == 0) {
      numEdge++;
    }
    matrix[v][w] = wgt;
  }

  // Get the weight value for an edge
  public int weight(int v, int w) { return matrix[v][w]; }

  // Removes the edge from the graph.
  public void removeEdge(int v, int w) {
    if (matrix[v][w] != 0) {
      matrix[v][w] = 0;
      numEdge--;
    }
  }
  
  // Returns true iff the graph has the edge
  public boolean hasEdge(int v, int w) { return matrix[v][w] != 0; }

  // Returns an array containing the indicies of the neighbors of v
  public int[] neighbors(int v) {
    int i;
    int count = 0;
    int[] temp;
    
    for (i=0; i<nodeValues.length; i++) {
      if (matrix[v][i] != 0) { count++; }
    }
    temp = new int[count];
    for (i=0, count=0; i<nodeValues.length; i++) {
      if (matrix[v][i] != 0) { temp[count++] = i; }
    }
    return temp;
  }
}

数组 nodeValues 存储由 setValue 和 getValue 函数操作的信息。 边矩阵实现为大小为 \(n \times n\) 的整数数组， 其中 \(n\) 是图的顶点数。 矩阵中的位置 \((i, j)\) 存储边 \((i, j)\) 的权值 （如果存在）。 边 \((i, j)\) 的权值为零用于表示 没有边连接顶点 \(i\) 和 \(j\)。

给定顶点 \(v\)，neighbors 方法扫描 矩阵的第 v 行以定位各个邻居的位置。 如果 \(v\) 上没有边， 则返回的邻居数组长度为 0。 函数 addEdge 和 removeEdge 调整 数组中的相应值。 函数 weight 返回数组中 适当位置的值。

以下是图的邻接表表示的实现。 其主要数据结构是链表数组， 每个顶点一个链表。 这些链表存储 Edge 类型的对象， 该对象仅存储边指向的顶点的索引以及边的权值。

public class GraphL implements Graph {

  private class Edge { // Doubly linked list node
    int vertex, weight;
    Edge prev, next;

    Edge(int v, int w, Edge p, Edge n) {
      vertex = v;
      weight = w;
      prev = p;
      next = n;
    }
  }

  private Edge[] nodeArray;
  private int[] nodeValues;
  private int numEdge;

  // No real constructor needed
  GraphL() {}

  // Initialize the graph with n vertices
  public void init(int n) {
    nodeArray = new Edge[n];
    // List headers;
    for (int i=0; i<n; i++) { nodeArray[i] = new Edge(-1, -1, null, null); }
    nodeValues = new int[n];
    numEdge = 0;
  }

  // Return the number of vertices
  public int nodeCount() { return nodeArray.length; }

  // Return the current number of edges
  public int edgeCount() { return numEdge; }

  // Get the value of node with index v
  public int getValue(int v) { return nodeValues[v]; }

  // Set the value of node with index v
  public void setValue(int v, int val) { nodeValues[v] = val; }
  
  // Return the link in v's neighbor list that preceeds the
  // one with w (or where it would be)
  private Edge find (int v, int w) {
    Edge curr = nodeArray[v];
    while ((curr.next != null) && (curr.next.vertex < w)) {
      curr = curr.next;
    }
    return curr;
  }

  // Adds a new edge from node v to node w with weight wgt
  public void addEdge(int v, int w, int wgt) {
    if (wgt == 0) { return; } // Can't store weight of 0
    Edge curr = find(v, w);
    if ((curr.next != null) && (curr.next.vertex == w)) {
      curr.next.weight = wgt;
    }
    else {
      curr.next = new Edge(w, wgt, curr, curr.next);
      numEdge++;
      if (curr.next.next != null) { curr.next.next.prev = curr.next; }
    }
  }

  // Get the weight value for an edge
  public int weight(int v, int w) {
    Edge curr = find(v, w);
    if ((curr.next == null) || (curr.next.vertex != w)) { return 0; }
    else { return curr.next.weight; }
  }

  // Removes the edge from the graph.
  public void removeEdge(int v, int w) {
    Edge curr = find(v, w);
    if ((curr.next == null) || curr.next.vertex != w) { return; }
    else {
      curr.next = curr.next.next;
      if (curr.next != null) { curr.next.prev = curr; }
    }
    numEdge--;
  }

  // Returns true iff the graph has the edge
  public boolean hasEdge(int v, int w) { return weight(v, w) != 0; }

  // Returns an array containing the indicies of the neighbors of v
  public int[] neighbors(int v) {
    int cnt = 0;
    Edge curr;
    for (curr = nodeArray[v].next; curr != null; curr = curr.next) {
      cnt++;
    }
    int[] temp = new int[cnt];
    cnt = 0;
    for (curr = nodeArray[v].next; curr != null; curr = curr.next) {
      temp[cnt++] = curr.vertex;
    }
    return temp;
  }
}

public class GraphL implements Graph {

  private class Edge { // Doubly linked list node
    int vertex, weight;
    Edge prev, next;

    Edge(int v, int w, Edge p, Edge n) {
      vertex = v;
      weight = w;
      prev = p;
      next = n;
    }
  }

  private Edge[] nodeArray;
  private Object[] nodeValues;
  private int numEdge;

  // No real constructor needed
  GraphL() {}

  // Initialize the graph with n vertices
  public void init(int n) {
    nodeArray = new Edge[n];
    // List headers;
    for (int i=0; i<n; i++) { nodeArray[i] = new Edge(-1, -1, null, null); }
    nodeValues = new Object[n];
    numEdge = 0;
  }

  // Return the number of vertices
  public int nodeCount() { return nodeArray.length; }

  // Return the current number of edges
  public int edgeCount() { return numEdge; }

  // Get the value of node with index v
  public Object getValue(int v) { return nodeValues[v]; }

  // Set the value of node with index v
  public void setValue(int v, Object val) { nodeValues[v] = val; }
  
  // Return the link in v's neighbor list that preceeds the
  // one with w (or where it would be)
  private Edge find (int v, int w) {
    Edge curr = nodeArray[v];
    while ((curr.next != null) && (curr.next.vertex < w)) {
      curr = curr.next;
    }
    return curr;
  }

  // Adds a new edge from node v to node w with weight wgt
  public void addEdge(int v, int w, int wgt) {
    if (wgt == 0) { return; } // Can't store weight of 0
    Edge curr = find(v, w);
    if ((curr.next != null) && (curr.next.vertex == w)) {
      curr.next.weight = wgt;
    }
    else {
      curr.next = new Edge(w, wgt, curr, curr.next);
      numEdge++;
      if (curr.next.next != null) { curr.next.next.prev = curr.next; }
    }
  }

  // Get the weight value for an edge
  public int weight(int v, int w) {
    Edge curr = find(v, w);
    if ((curr.next == null) || (curr.next.vertex != w)) { return 0; }
    else { return curr.next.weight; }
  }

  // Removes the edge from the graph.
  public void removeEdge(int v, int w) {
    Edge curr = find(v, w);
    if ((curr.next == null) || curr.next.vertex != w) { return; }
    else {
      curr.next = curr.next.next;
      if (curr.next != null) { curr.next.prev = curr; }
    }
    numEdge--;
  }

  // Returns true iff the graph has the edge
  public boolean hasEdge(int v, int w) { return weight(v, w) != 0; }

  // Returns an array containing the indicies of the neighbors of v
  public int[] neighbors(int v) {
    int cnt = 0;
    Edge curr;
    for (curr = nodeArray[v].next; curr != null; curr = curr.next) {
      cnt++;
    }
    int[] temp = new int[cnt];
    cnt = 0;
    for (curr = nodeArray[v].next; curr != null; curr = curr.next) {
      temp[cnt++] = curr.vertex;
    }
    return temp;
  }
}

GraphL 成员函数的实现原则上很简单， 关键函数是 addEdge、removeEdge 和 weight。 它们只需从邻接表的开头开始， 沿表移动直到找到所需的顶点。 私有方法 find 是一个工具函数， 用于在存在时找到保存顶点 \(v\) 的边之前的最后一条边。

待处理

type: Exercise

添加一系列问题以测试对实现知识的掌握。

   «  1. 图章引论   ::   目录   ::   3. 图遍历  »

© Copyright 2011-2025 by OpenDSA Project Contributors and distributed under an MIT license. 最后更新于 9月 30, 2026. Created using Sphinx 8.2.0.
关闭窗口