14. 无向图

14.1 术语

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

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

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

3. 子图：一幅图的子集（包括边和顶点）组成的图

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

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

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

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

6. 无环图：就是没有环的图

   树是一幅无环连通图

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

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

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

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 \times V$ 的布尔矩阵来表示图，当 $v$ 和 $w$ 相邻时，将 v 行 w 列的元素标记为 true，否则为 false

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

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

14.2.2 边的数组

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

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

14.2.3 邻接表数组

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

即，每个数组元素既是一个顶点也是一个链表头，链表储存着与该顶点（链表头）相邻的所有顶点。

它可以实现：

1. 使用的空间和 $V + 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];
    }
}