< Back

Undirected Graph

图的表示方式

  • 邻接矩阵。用一个 V 乘 V 的布尔 矩阵。当顶点v和顶点w之间有相连接的边 时，定义 v 行 w 列的元素值为 true，否则为 false。当有上百万个顶点的时候，需要的空间是不能满足的。且这种方式无法表示平行边的情况，（连接同一对顶点的两条边称为平行边，两个顶点间可以有多个平行边）
  • 边的数组。用一个 Edge 类，含有两个 int 实例变量来表示边，很简洁，但是如果要查找顶点的邻接点就需要遍历所有的边。
  • 邻接表数组。所有的顶点都用数组的索引来表示，每个数组元素都是该顶点的相邻顶点列表。这个感觉像是Map的实现，说白了就是链表数组。效率很高不用说，而且支持平行边和自环。
img

  • 定义图的数据类型

    export type TEdge = [number, number];

export type TGraphData = {
  V: number;
  edges: TEdge[];
}

export class Graph {
  private V: number;  // 顶点数
  private E: number;  // 边数
  private adj: number[][];  // 邻接数组，书里是用了个链表数组，这里直接用个二维数组算了

  constructor(data: TGraphData) {
    this.V = data.V;
    this.E = 0;
    this.adj = [];

    data.edges.forEach(([v, w]) => this.addEdge(v, w));
  }

  public addEdge(v: number, w: number) {
    this.adj[v] = this.adj[v] || [];
    this.adj[w] = this.adj[w] || [];
    this.adj[v].push(w);
    this.adj[w].push(v);
    this.E++;
  }

  public adjOf(v: number) {
    return this.adj[v];
  }

  public getV() {
    return this.V;
  }

  public getE() {
    return this.E;
  }
}

深度优先搜索（Depth First Search)

从点S出发，访问S所有没有被标记的相邻点，访问一个点后标记为已访问，这样一直递归的访问下去。如果图是连通的，那么每个点都会被访问到。且保证每个顶点都只会被访问一次，保证了时间上限。

测试数据tinyG：

img

书中是用的文件读取，我这里直接写在代码里：

const data: TGraphData = {
  V: 13,
  edges: [
    [0, 5],
    [4, 3],
    [0, 1],
    [9, 12],
    [6, 4],
    [5, 4],
    [0, 2],
    [11, 12],
    [9, 10],
    [0, 6],
    [7, 8],
    [9, 11],
    [5, 3],
  ]
}

dfs实现：

class DepthFirstSearch {
  private marked: boolean[];  // 标记所有与s连通的点
  private count: number; // 与s连通点的顶点总数

  constructor(g: Graph, s: number) {
    this.marked = [];
    this.count = 0;
    this.dfs(g, s);
  }

  private dfs(g: Graph, v: number) {
    this.marked[v] = true;  // 每访问一个点v则标记为已访问
    this.count++;
    g.adjOf(v).forEach(adj => {  // 遍历v的每一个相邻点
      if (!this.marked[adj]) {
        this.dfs(g, adj);
      }
    })
  }

  public getMarked(w: number) {
    return this.marked[w];
  }

  public getCount() {
    return this.count;
  }
}

const main = () => {
  const g = new Graph(data);
  const search = new DepthFirstSearch(g, 0);

  const marked = [];
  for (let v = 0; v < g.getV(); v++) {
    if (search.getMarked(v)) {
      marked.push(v);
    }
  }
  console.log(marked.join(', '));

  if (search.getCount() != g.getV()) {
    console.log('not connected');
  } else {
    console.log('connected');
  }
}

main();
// 0, 1, 2, 3, 4, 5, 6
// not connected

查找路径

查找下图中两点之间的路径。

img
const data: TGraphData = {
  V: 6,
  edges: Array.from<TEdge>([
    [0, 5],
    [2, 4],
    [2, 3],
    [1, 2],
    [0, 1],
    [3, 4],
    [3, 5],
    [0, 2],
  ]).reverse()
}

reverse一下是为了使输出结果和书中的一致，因为书里的邻接数组是链表数组，添加相邻顶点的时候是从链表的头部开始添加，而这里直接使用数组的push方法，那么dfs走出来的路径就是不一样的。

用dfs实现：

class DepthFirstPaths {
  private marked: boolean[];
  private edgeTo: number[];
  private s: number;

  constructor(g: Graph, s: number) {
    this.marked = [];
    this.edgeTo = [];
    this.s = s;

    this.dfs(g, s);
  }

  private dfs(g: Graph, v: number) {
    this.marked[v] = true;

    g.adjOf(v).forEach(adj => {
      if (!this.marked[adj]) {
        this.edgeTo[adj] = v;
        this.dfs(g, adj);
      }
    })
  }

  public hasPathTo(v: number) {
    return this.marked[v];
  }

  public pathTo(v: number) {
    if (!this.hasPathTo(v)) {
      return null;
    }

    const path = [];
    for (let x = v; x !== this.s; x = this.edgeTo[x]) {
      path.push(x);
    }
    path.push(this.s);
    return path;
  }
}

const main = () => {
  const g = new Graph(data);
  const dfp = new DepthFirstPaths(g, 0);
  const path = dfp.pathTo(5);
  console.log(path); // [ 5, 3, 2, 0 ]
}

main();
img

广度优先搜索

dfs只是单纯的一直往下探索一下一个没有被访问过的点，知道没有路可走了才回到上一个岔路口继续走。他无法回答“找出s到v到最短路径”这样的问题。而bfs就是可以解决这个问题。

dfs是一条道走到黑，而bfs是想象同时向每个邻接点出发。

img

数据还是和上一个DepthFirstPaths用到的数据一样。这里没有用递归，而是控制一个队列。

class BreadthFirstPaths {
  private marked: boolean[];
  private edgeTo: number[];
  private s: number;

  constructor(g: Graph, s: number) {
    this.marked = [];
    this.edgeTo = [];
    this.s = s;

    this.bfs(g, s);
  }

  private bfs(g: Graph, s: number) {
    let queue = [s];

    while (queue.length) {
      const v = queue[0];
      queue.shift();
      g.adjOf(v).forEach(adj => {
        if (!this.marked[adj]) {
          this.marked[adj] = true;
          this.edgeTo[adj] = v;
          queue.push(adj);
        }
      })
    }
  }

  public hasPathTo(v: number) {
    return this.marked[v];
  }

  public pathTo(v: number) {
   	.... // 同上pathTo
  }
}

const main = () => {
  const g = new Graph(data);
  const bfs = new BreadthFirstPaths(g, 0);
  const path = bfs.pathTo(4);
  console.log(path);  // [ 4, 2, 0 ]
}

main();
img

连通分量

数据选择开头的tinyG的数据，

class CC {
  private marked: boolean[];
  private count: number;  // 连通分量数
  private id: number[];  // 记录每一个顶点的连通分量的标识符

  constructor(g: Graph) {
    this.marked = [];
    this.count = 0;
    this.id = [];

    for (let s = 0; s < g.getV(); s++) {
      if (!this.marked[s]) {
        this.dfs(g, s);
        // 每一次dfs走完都意味着走完了一个连通分量
        this.count++;
      }
    }
  }

  private dfs(g: Graph, v: number) {
    this.marked[v] = true;
    this.id[v] = this.count;
    g.adjOf(v).forEach(adj => {
      if (!this.marked[adj]) {
        this.dfs(g, adj);
      }
    })
  }

  public getMarked(w: number) {
    return this.marked[w];
  }

  public getCount() {
    return this.count;
  }

  public getId(v: number) {
    return this.id[v];
  }

  public connected(v: number, w: number) {
    return this.id[v] === this.id[w];
  }
}

const main = () => {
  const g = new Graph(data);
  const search = new CC(g);

  console.log(`components: ${search.getCount()}`);

  const components: number[][] = [];
  for (let i = 0; i < g.getV(); i++) {
    const id = search.getId(i);
    components[id] = components[id] || [];
    components[id].push(i);
  }
  console.log(components);
  // components: 3
  // [
  //   [
  //     0, 1, 2, 3,
  //     4, 5, 6
  //   ], 
  //   [7, 8], 
  //   [9, 10, 11, 12]
  // ]
}

main();

本节代码：https://github.com/Yuijam/algorithms-note/tree/main/graph/undirected