4 图

定义:由一组顶点和一组可连接两个顶点的边组成

4.1 无向图

定义:边只和两个顶点连接

4.1.1 术语表

  • 自环:一条连接一个顶点和自身的边
  • 平行边:连接同一对顶点的两条边
  • 多重图:含有平行边的图
  • 简单图:无平行边和自环的图
  • 子图:由一幅图的所有边和所依附顶点组成的图(边诱导子图)

  • 路径:由边顺序连接的一系列点

    • 简单路径(基本道路):无重复顶点的路径

      • 简单环(圈):起点终点相同的闭简单路径
  • 连通图:任意一个顶点都存一条路径到任意一个顶点

  • 树:无环连通图

    • 森林:互不相连的树

    • 生成树:含有连通图所有顶点且为树的连通图子图

      • 生成树森林:所有连通子图生成树的集合

  • 树的六个等价命题:对于G=(V,E)

    1. G不含简单环(圈)且G连通
    2. G有V-1条边且连通
    3. G有V-1条边且无简单环
    4. G连通,但删除任意一条边不再连通
    5. G无环,但加上任意一条边产生环
    6. G中任意一对顶点间仅存在一条简单路径

  • 密度:已经连接的顶点对占所有可能连接的顶点对比例

    • 稀疏/稠密图:图中不同边的数量在/不在顶点总数的一个小常数倍内
  • 二分图:可以将所有结点分为两部分的图,每条边连接两点分属不同部分

4.1.2 无向图API:public class Graph

返回类型 方法 描述
Graph(int V) 创建V个顶点的无边图
Graph(In in) 从标准输入in读入一幅图
int V() 顶点数
int E() 边数
void addEdge(int v, int w) 添加边v-w
Iterable adj(int v) 和v相邻的所有顶点
String toString() 对象的字符串表示
  • 本节所有算法基于adj()抽象
  • 第二个构造函数接收2E+2个整数:V,E,E对0~V-1的整数(边)

常用图处理代码

  • 计算v的度数
  1. public static int degree(Graph G, int v){
  2.     int degree = 0;
  3.     for(int w: G.adj(v))
  4.         degree++;
  5.     return degree;
  6. }
  • 计算所有顶点的最大度数
  1. public static int maxDegree(Graph G){
  2.     int max = 0;
  3.     for(int v = 0; v < G.V(); v++){
  4.         if(max < degree(G, v)) max = degree(G, v);
  5.     return max;
  6.     }
  7. }
  • 计算所有结点平均度数
  1. public static double avgDegree(Graph G){
  2.     return 2.0*G.E()/G.V();
  3. }
  • 计算自环个数
  1. public static int loopNum(Graph G){
  2.     int num = 0;
  3.     for(int v = 0; v < G.V(); v++){
  4.         for(int w: G.adj(v)){
  5.             if(w == v) num++;
  6.         }
  7.     }
  8.     return num;
  9. }

4.1.2.1 图的表示

  • 需求:

    1. 必须为可能的各种类型图留出足够空间
    2. Graph的实例方法实现要快

  • 对比:

    • 邻接矩阵:使用V*V的boolean矩阵,true表示两点之间有连接,否则为false

      • 第一个条件不满足:V²空间在数组极大时不实际

    • 边类数组:使用Edge类,含有int v, int w表示两端点

      • 第二个条件不满足:adj()的实现需要遍历所有元素
    • 邻接表数组:使用一个以顶点为索引的列表数组(如拉链法散列表),每个元素都是和该顶点相邻的顶点列表

4.1.2.2 邻接表数据结构

  • 实现:将每个顶点的所有相邻顶点保存在顶点对应元素指向的链表中,链表有Bag(类似Stack),addEdge(int v, int w)时,既要添加v-w也要添加w-v,所以邻接表中每条边出现两次

  • 性能特点:

    • 空间:和V(数组大小)+E(链表大小)成正比
    • 添加一条边的时间为常数:链表插入
    • 遍历顶点v相邻结点的时间和v的度数成正比:遍历链表
  • 顺序问题:有上述说明可知,邻接表中每个元素对应链表的元素顺序取决于输入顺序和图本身,顺序不同的邻接表可以表示相同的图

Graph数据类型

  1. public class Graph {
  2.     private final int V;//顶点数
  3.     private int E;//边数
  4.     private Bag<Integer>[] adj;//邻接表
  6.     public Graph(int V){
  7.         this.V = V;
  8.         this.E = 0;//构造无边图
  9.         adj = (Bag<Integer>[]) new Bag[V];
  10.         for (int v = 0; v < V; v++){
  11.             adj[v] = new Bag<Integer>();//对象数组单个元素需要实例化
  12.         }
  13.     }
  15.     public Graph(In in){
  16.         this(in.readInt());//读取V并执行第一个构造函数
  17.         int E = in.readInt();//读取E,边数(非实例变量E)
  18.         for(int i = 0; i < E; i++){
  19.             int v = in.readInt();
  20.             int w = in.readInt();
  21.             addEdge(v,w);
  22.         }
  23.     }
  25.     //加入边
  26.     public void addEdge(int v, int w){
  27.         adj[v].add(w);
  28.         adj[w].add(v);
  29.         E++;
  30.     }
  32.     public int V(){ return V; }
  33.     public int E(){ return E; }
  34.     //返回与v相邻所有点
  35.     public Iterable<Integer> adj(int v){
  36.         return adj[v];
  37.     }
  39.     //字符串显示邻接表
  40.     public String toString(){
  41.         String s = V + " vertices, " + E + " edges\n";
  42.         for(int v = 0; v < V; v++){
  43.             s += v + ": ";
  44.             for (int w: this.adj(v))
  45.                 s += w + " ";
  46.             s += "\n";
  47.         }
  48.         return s;
  49.     }
  50. }

4.1.2.3 图处理算法设计模式

  • 图的实现和图的处理应该分离:构造一副图,将图作为参数传递给某个算法的类

4.1.3 深度优先搜索(算法4.1)

4.1.4 寻找路径(算法4.1)

4.1.5 广度优先搜索(算法4.2)

4.1.6 连通分量(算法4.3)