第四章 图(一)

4.1 无向图

定义：图是由一组顶点和一组能够将两个顶点相连的边组成的。

• 一般使用0至V-1来表示一张含有V个顶点的图的各个顶点，用v-w的记法来表示连接v和w的边
• 特殊的图：
  • 自环，即一条连接一个顶点和其自身的边
  • 连接同一对顶点的两条边称为平行边
• 数学家常常将含有平行边的图称为多重图，而将没有平行边或自环的图称为简单图

4.1.1 术语表

• 当两个顶点通过一条边相连时，我们称这两个顶点时相邻的，并称这条边依附于这两个顶点，某个顶点的度数即为依附于它的边的总数
• 子图是由一幅图的所有边的一个子集(以及它们所依附的所有顶点)组成的图

定义：在图中，路径是由边顺序连接的一系列顶点。简单路径是一条没有重复顶点的路径。环是一条至少含有一条边且起点和终点相同的路径。简单环是一条(除了起点和终点必须相同之外)不含有重复顶点和边的环。路径或者环的长度为其中所包含的边数。

• 当两个顶点之间存在一条连接双方的路径时，我们称一个顶点和另一个顶点时连通的

定义：如果从任意一个顶点都存在一条路径到达另一个任意顶点，我们称这幅图是连通图，一幅非连通的图由若干连通的部分组成，它们都是其极大连通子图。

• 无环图是一种不包含环的图

定义：树是一幅无环连通图。互不相连的树组成的集合称为森林。连通图的生成树是它的一幅子图，它含有图中的所有顶点且是一棵树。图的生成树森林是它的所有连通子图的生成树的集合。

• 当且仅当一幅含有V个结点的图G满足下列5个条件之一时，它就是一棵树：

  • G有V-1条边且不含有环
  • G有V-1条边且是连通的
  • G是连通的，但删除任意一条边都会使它不再连通
  • G是无环图，但添加任意一条边都会产生一条环
  • G中任意一对顶点之间仅存在一条简单路径

• 图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例，分为稀疏图和稠密图

• 二分图是一种能将所有结点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分

4.1.2 表示无向图的数据类型

• 无向图的API如下：

• toString()方法和adj()方法用来允许用例遍历给定顶点的所有相邻顶点

• 第二个构造函数接收的输入由2E+2个整数组成：首先是V，然后是E，再然后是E对0到V-1之间的整数，每个整数对都表示一条边

• 最常用的图处理方法：

4.1.2.1 图的几种表示方法

• 邻接矩阵：使用一个V乘V的布尔矩阵，顶点相连时为true。但可能无法满足所需的V²的空间
• 边的数组：使用一个Edge类，包含两个int实例变量。但不能实现adj()中的检查所有边
• 邻接表数组：使用一个以顶点为索引的列表数组，其中的每个元素都是和该顶点相邻的顶点列表

4.1.2.2 邻接表的数据结构

• 非稠密图的标准表称为邻接表的数据结构
• 这里使用Bag抽象数据类型来实现这个链表
• 这种Graph的实现的性能有如下特点：
  • 使用的空间和V+E成正比
  • 添加一条边所需的时间为常数
  • 遍历顶点v的所有相邻顶点所需的时间和v的度数成正比(处理每个相邻顶点所需的时间为常数)
• 具体实现如下：

public class Graph{
    private final int v;
    private int E;
    private Bag<Integer>[] adj;
    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++){
			int v = in.readInt();
            int w = in.readInt();
            addEdge(v, w);
        }
    }
    public void addEdge(int v, int w){
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public Iterable<Integer> adj(int v){
        return adj[v];
    }
}

4.1.2.3 图的处理算法的设计模式

• 图处理算法的API：