0%

14. 无向图

14.1 术语

图是由一组顶点和将点连接起来的组成的。

  1. 相邻:如果两个顶点被至少一条边连接,那么就称顶点相邻,并称边依附于顶点。

  2. 顶点的度:依附于它的边的条数

  3. 子图:一幅图的子集(包括边和顶点)组成的图

  4. 路径:由边顺序连接的一组顶点

    其中又分为简单路径
    简单路径:没有重复顶点的路径
    简单环:起点和终点必须相同的没有重复顶点和边的环

  1. 连通图:如果从任何一个顶点都存在一条路径到达另一个任意节点,那么称这幅图为连通图

    如果一副非联通图由若干个连通部分组成,那么这些部分都叫做极大连通子图

  2. 无环图:就是没有环的图

    树是一幅无环连通图

  3. 密度:已经连接的顶点对占所有可能被连接的顶点对的比例。

    这派生出了两个概念,稀疏图稠密图
    一般来说,如果一幅图中不同的边的数量在顶点总数VV的一个小常数倍内,那么这幅图就是稀疏的

  4. 二分图:一种能够将所有顶点分成两部分的图,其中每条边都连着两个不同的顶点

14.2 表示法

14.2.0 API

为了解决有关图的问题,下面定义一个图的基本 API

public class Graph {
    public Graph(int V) // Create graph using the Vertex number

    public Graph(In in) // Create graph from input stream

    public int V();      // The number of Vertex

    public int E();      // The number of Edge

    // Add edge v-w into graph
    public void addEdge(int v, int w);

    // The vertexes adjacent to v
    public Iterable<Integer> adj(int v);

    public String toString(); // The string explanation of graph
}

14.2.1 邻接矩阵

使用一个 V×VV \times V布尔矩阵来表示图,当 vvww 相邻时,将 vw 列的元素标记为 true,否则为 false

这种方法需要 V2V^2 个布尔值的空间,实际上十分耗费存储空间,不实用。

而且当图具有平行边时,邻接矩阵无法准确表示这一结构。

14.2.2 边的数组

我们可以定义一个 Edge 类,其中使用两个 int 变量来表示所连接的两个顶点。

但是这一结构无法实现 adj(),实现它需要检查图中所有的边。

14.2.3 邻接表数组

我们可以使用一个以顶点为索引的列表数组,其中每个元素都是和该顶点相邻的顶点列表

即,每个数组元素既是一个顶点也是一个链表头,链表储存着与该顶点(链表头)相邻的所有顶点

Adjacent Array

它可以实现:

  1. 使用的空间和 V+EV + E 成正比
  2. 添加一条边所需的时间为常数
  3. 遍历顶点 v 的所有相邻顶点所需要的时间和 v 的度数成正比

对于这些操作来说,这样的特性已经是最优的了,所以我们选择邻接表来作为图的数据结构

下面是图的代码实现:

public class Graph {
    private final int V;        // Vertex number
    private int E;              // Edge number
    private Bar<Integer>[] adj; // adjacent array

    public Graph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new Bag<Integer>();
        }
    }

    public Graph(In in) {
        this(in.readInt());
        int E = in.readInt();
        for (int i = 0; i < E; i++) {
            // Add Edge
            int v = in.readInt();
            int w = in.readInt();
            addEdge(v, w);
        }
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}