数据结构之图形概览

一、概念

由非空的顶点有限集合 ( V )（包含 ( n>0 ) 个顶点）以及边的集合 ( E )（表示顶点之间的关系）所构成的结构。其形式化定义为 ( G=(V,E) )。

• 顶点（Vertex） ：图中的数据元素一般被称作顶点，在下面的示意图里用圆圈来代表顶点。
• 边（Edge） ：图中两个数据元素之间的关联关系通常叫做边，在示意图中用连接两个顶点的线段表示边。边的形式化定义为：( e = \langle u, v \rangle )，表示从 ( u ) 到 ( v ) 的一条边，其中 ( u ) 是起始点，( v ) 是终止点

• 子图（Sub Graph） ：对于图 ( G=(V,E) ) 和 ( G'=(V', E') )，若存在 ( V' \subseteq V )，( E' \subseteq E )，则称图 ( G' ) 是图 ( G ) 的一个子图。在示意图中给出了一个图 ( G ) 及其子图 ( G' )。特别地，根据定义，( G ) 自身也是它的子图。
• 

二、图的分类

1. 无向图和有向图

依据边是否有方向，可将图分为两类：「无向图」和「有向图」。

• 无向图（Undirected Graph） ：若图中的每条边都没有指向性，就称为无向图。比如朋友关系图、路线图都属于无向图。
• 有向图（Directed Graph） ：若图中的每条边都具有指向性，就称为有向图。比如流程图就是有向图。

在无向图中，每条边是由两个顶点组成的无序对。例如图左侧的顶点 ( v_1 ) 和顶点 ( v_2 ) 之间的边记为 ( (v_1, v_2) ) 或 ( (v_2, v_1) )。

在有向图中，有向边也叫弧，每条弧是由两个顶点组成的有序对，例如图右侧中从顶点 ( v_1 ) 到顶点 ( v_2 ) 的弧，记为 ( \langle v_1, v_2 \rangle )，( v_1 ) 是弧尾，( v_2 ) 是弧头，如下图所示

若无向图有 ( n ) 个顶点，那么无向图中最多有 ( n \times (n-1)/2 ) 条边。具有 ( n \times (n-1)/2 ) 条边的无向图称为 「完全无向图（Completed Undirected Graph）」 。

若有向图有 ( n ) 个顶点，那么有向图中最多有 ( n \times (n-1) ) 条弧。具有 ( n \times (n-1) ) 条弧的有向图称为 「完全有向图（Completed Directed Graph）」 。

如下图所示，左侧是包含 4 个顶点的完全无向图，右侧是包含 4 个顶点的完全有向图

下面介绍无向图和有向图中一个重要概念 「顶点的度」 。

• 顶点的度 ：与该顶点 ( v_i ) 相关联的边的条数，记为 ( TD(v_i) )。

例如上图左侧的完全无向图中，顶点 ( v_3 ) 的度是 3。

对于有向图，顶点的度可分为 「顶点的出度」 和 「顶点的入度」 。

• 顶点的出度 ：以该顶点 ( v_i ) 为出发点的边的条数，记为 ( OD(v_i) )。
• 顶点的入度 ：以该顶点 ( v_i ) 为终止点的边的条数，记为 ( ID(v_i) )。
• 有向图中某顶点的度 = 该顶点的出度 + 该顶点的入度，即 ( TD(v_i) = OD(v_i) + ID(v_i) )

例如上图右侧的完全有向图中，顶点 ( v_3 ) 的出度是 3，入度是 3，顶点 ( v_3 ) 的度是 ( 3+3=6 )

2. 环形图和无环图

3. 带权图

当图不仅要表示顶点之间是否存在某种关系，还需体现这种关系的具体细节时，就需要在边上赋予一些数据信息，这些数据信息被称作权。在实际应用中，权值可以有不同含义，比如代表距离、时间、价格等属性。

• 带权图 ：若图的每条边都被赋予一个权值，这种图称为带权图。
• 网络 ：带权的连通无向图称为网络。

下面示意图给出了一个带权图的示例。

三、图的存储结构

图的结构较为复杂，需要表示顶点和边。一个图可能有任意数量（有限个）的顶点，且任意两个顶点之间都可能有边。存储图时，关键是要关注边与顶点之间的关联关系。

图的存储可通过「顺序存储结构」和「链式存储结构」实现。其中顺序存储结构包含邻接矩阵和边集数组，链式存储结构包含邻接表、链式前向星、十字链表和邻接多重表。

1. 邻接矩阵

1.1. 概念

用一个二维数组 ( \text{adjmatrix} ) 来存储顶点之间的邻接关系。

对于无权图，若 ( \text{adjmatrix}[i][j] ) 为 1，表明顶点 ( v_i ) 到 ( v_j ) 存在边；若 ( \text{adjmatrix}[i][j] ) 为 0，则表明顶点 ( v_i ) 到 ( v_j ) 不存在边；若 ( \text{adjmatrix}[i][j] ) 为 ( w ) 且 ( w \neq \infty )，则表明顶点 ( v_i ) 到 ( v_j ) 的权值为 ( w )；若 ( \text{adjmatrix}[i][j] ) 为 ( \infty )，则表明顶点 ( v_i ) 到 ( v_j ) 不存在边。

对于带权图

• 优点：实现简单，能直接查询顶点 ( v_i ) 与 ( v_j ) 之间是否有边，还能直接查询边的权值。
• 缺点：初始化效率和遍历效率低，空间开销大，空间利用率低，不能存储重复边，增删节点不便。当顶点数目过大（比如 ( n>10^5 )）时，用邻接矩阵建立 ( n \times n ) 的二维数组不现实

1.2. 代码实现

class Graph {
  constructor(verCount) {
    this.verCount = verCount;
    this.adjMatrix = new Array(verCount).fill(null).map(() => new Array(verCount).fill(null));
  }

  addEdge(vi, vj, val) {
    if (!this.isValid(vi) || !this.isValid(vj)) {
      throw new Error(`${vi} 或 ${vj} 不是有效的顶点。`);
    }
    this.adjMatrix[vi][vj] = val;
  }

  getEdge(vi, vj) {
    if (!this.isValid(vi) || !this.isValid(vj)) {
      throw new Error(`${vi} 或 ${vj} 不是有效的顶点。`);
    }
    return this.adjMatrix[vi][vj];
  }

  printGraph() {
    for (let vi = 0; vi < this.verCount; vi++) {
      for (let vj = 0; vj < this.verCount; vj++) {
        const val = this.getEdge(vi, vj);
        if (val !== null && val !== undefined) {
          console.log(`${vi} - ${vj} : ${val}`);
        }
      }
    }
  }

  isValid(v) {
    return 0 <= v && v < this.verCount;
  }
}

const graph = new Graph(5);
const edges = [[1, 2, 5], [2, 1, 5], [1, 3, 30], [3, 1, 30], [2, 3, 14], [3, 2, 14], [2, 4, 26], [4, 2, 26]];

edges.forEach(([vi, vj, val]) => {
  graph.addEdge(vi, vj, val);
});

try {
  console.log(graph.getEdge(3, 4));
  graph.printGraph();
} catch (error) {
  console.error(error.message);
}

2. 边集数组

2.1. 概念

用一个数组存储顶点之间的邻接关系。数组中每个元素包含一条边的起点 ( v_i )、终点 ( v_j ) 和边的权值 ( val )（若为带权图）

2.2. 代码实现

class EdgeNode {
  constructor(vi, vj, val) {
    this.vi = vi;
    this.vj = vj;
    this.val = val;
  }
}

class Graph {
  constructor() {
    this.edges = [];
  }

  createGraph(edges = []) {
    edges.forEach(([vi, vj, val]) => {
      this.add_edge(vi, vj, val);
    });
  }

  add_edge(vi, vj, val) {
    const edge = new EdgeNode(vi, vj, val);
    this.edges.push(edge);
  }

  get_edge(vi, vj) {
    for (const edge of this.edges) {
      if (vi === edge.vi && vj === edge.vj) {
        return edge.val;
      }
    }
    return null;
  }

  printGraph() {
    this.edges.forEach(edge => {
      console.log(`${edge.vi} - ${edge.vj} : ${edge.val}`);
    });
  }
}

const graph = new Graph();
const edges = [[1, 2, 5], [1, 5, 6], [2, 4, 7], [4, 3, 9], [3, 1, 2], [5, 6, 8], [6, 4, 3]];

graph.createGraph(edges);

console.log(graph.get_edge(3, 4));
graph.printGraph();

3. 邻接表

3.1. 概念

采用顺序存储和链式存储相结合的存储结构来存储图的顶点和边。数据结构包含两部分，一部分是数组，用于存放顶点的数据信息；另一部分是链表，用于存放边信息。

在邻接表存储方式中，对图中每个顶点 ( v_i ) 建立一个线性链表，把所有邻接于 ( v_i ) 的顶点链接到单链表上。对于有 ( n ) 个顶点的图，其邻接表结构由 ( n ) 个线性链表组成。

然后在每个顶点前设置一个表头节点，称为「顶点节点」。每个顶点节点由「顶点域」和「指针域」组成，顶点域存放某个顶点的数据信息，指针域指出该顶点第 1 条边对应的链节点。

为方便随机访问任意顶点的链表，通常用一组顺序存储结构（数组）存储所有「顶点节点」部分，顺序存储结构（数组）的下标表示该顶点在图中的位置。

3.2. 代码实现

class EdgeNode {
  constructor(vj, val) {
    this.vj = vj;
    this.val = val;
    this.next = null;
  }
}

class VertexNode {
  constructor(vi) {
    this.vi = vi;
    this.head = null;
  }
}

class Graph {
  constructor(verCount) {
    this.verCount = verCount;
    this.vertices = [];
    for (let vi = 0; vi < verCount; vi++) {
      const vertex = new VertexNode(vi);
      this.vertices.push(vertex);
    }
  }

  isValid(v) {
    return 0 <= v && v < this.verCount;
  }

  createGraph(edges = []) {
    edges.forEach(([vi, vj, val]) => {
      this.addEdge(vi, vj, val);
    });
  }

  addEdge(vi, vj, val) {
    if (!this.isValid(vi) || !this.isValid(vj)) {
      throw new Error(`${vi} 或 ${vj} 不是有效的顶点。`);
    }
    const vertex = this.vertices[vi];
    const edge = new EdgeNode(vj, val);
    edge.next = vertex.head;
    vertex.head = edge;
  }

  getEdge(vi, vj) {
    if (!this.isValid(vi) || !this.isValid(vj)) {
      throw new Error(`${vi} 或 ${vj} 不是有效的顶点。`);
    }
    const vertex = this.vertices[vi];
    let curEdge = vertex.head;
    while (curEdge) {
      if (curEdge.vj === vj) {
        return curEdge.val;
      }
      curEdge = curEdge.next;
    }
    return null;
  }

  printGraph() {
    for (const vertex of this.vertices) {
      let curEdge = vertex.head;
      while (curEdge) {
        console.log(`${vertex.vi} - ${curEdge.vj} : ${curEdge.val}`);
        curEdge = curEdge.next;
      }
    }
  }
}

const graph = new Graph(7);
const edges = [[1, 2, 5], [1, 5, 6], [2, 4, 7], [4, 3, 9], [3, 1, 2], [5, 6, 8], [6, 4, 3]];

graph.createGraph(edges);

console.log(graph.getEdge(3, 4));
graph.printGraph();

四、图论问题应用

图论及图论算法在计算机科学中占据重要地位，为诸多问题提供了简洁且系统的建模方式。很多实际问题可转化为图论问题，再运用图论的经典算法解决。例如：

• 集成电路的设计与布线。
• 互联网及路由、移动电话网的路由设计。
• 工程项目的计划安排问题。

常见的图论问题应用大致可分为以下几类：图的遍历问题 、图的连通性问题 、图的生成树问题 、图的最短路径问题 、图的网络流问题 、二分图问题 等等