Ch11 图

1. 图

图是由一组顶点和一组可连接两个顶点的边组成的数据结构，根据边是否有指向或者是否带有权值可分为：

• 无向图：只由一组顶点和一组可连接两个顶点的边构成(a)
• 有向图：边是单向的，每条边连接的两个顶点是一个有序对(b)
• 加权有向图：除了有向图性质，其每条边还带有权重(c)

2. 图的实现

API

下列API构成后续一系列图算法的基础GraphADT.java

邻接矩阵实现(Adjacency Matrix)

Edge.java
Graphm.java
邻接矩阵实现中有几个数据结构

• int[][] matrix：边矩阵：matrix[1][2]中存储着顶点1到顶点2边的权重，当两点之间无边连接时权值为0
• int[] Mark：Mark数组，存放顶点v的邻接点：Mark[2]存放顶点2的邻接点 | | 执行 | 结果 | | —- | :—-: | :—-: | | | i=e() | i=6 | | | i=n() | i=5 | | | i=first(1) | i=3 | | | i=next(1,3) | i=5(点1无其他邻接点,返回n=5) | | | i=next(0,1) | i=4(点0的下一邻接点为4) | | | i=weight(2,4) | i=0(不存在边2-4,权值为0) |

邻接表实现(Adjacency List)

Graphl.java

	执行	结果
	i=e()	i=6
	i=n()	i=5
	i=first(1)	i=3
	i=next(1,3)	i=5(点1无其他相邻点,返回n=5)
	i=next(0,1)	i=4(点0的下一相邻点为4)
	i=weight(2,4)	i=0(不存在边2-4,权值为0)

:::danger 上例都以有向图说明，实际上这两种实现广泛适用于实现各类图结构 :::

3. 图的遍历

:::info

• DFS实现：使用递归/隐式栈

• BFS实现：队列，FIFO :::

  DFS

  下方递归方法实现了有向图的DFS，其中Pre/PostVisit可以是打印操作等行为：

• 在for循环前打印V，可实现**先根遍历**

• 在for循环后打印V，可实现**后根遍历**

  /** Depth first search */
  static void DFS(Graph G, int v) {
    PreVisit(G, v); // Take appropriate action
    G.setMark(v, VISITED);
    for (int w = G.first(v); w < G.n() ; w = G.next(v, w))
        if (G.getMark(w) == UNVISITED)
            DFS(G, w);
    PostVisit(G, v); // Take appropriate action
  }

  BFS

  /** Breadth first (queue-based) search */
  static void BFS(Graph G, int start) {
    Queue<Integer> Q = new AQueue<Integer>(G.n());
    Q.enqueue(start);
    G.setMark(start, VISITED);
    while (Q.length() > 0) { // Process each vertex on Q
        int v = Q.dequeue();
        PreVisit(G, v); // Take appropriate action
        for (int w = G.first(v); w < G.n(); w = G.next(v, w))
            if (G.getMark(w) == UNVISITED) { // Put neighbors on Q
                G.setMark(w, VISITED);
                Q.enqueue(w);
            }
        PostVisit(G, v); // Take appropriate action
    }
  }

  :::info 举例：给定无向图，求DFS和BFS结果
  :::

  Topology

  拓扑遍历只适用于有向无环图DAG，遍历思路有两种：
  (1)一般方法

1. 创建queue，将入度为0的顶点enqueue(按顶点序号入队)
2. 对已在队列中顶点按顺序dequeue(V)，输出V，对V的邻接顶点入度减1，若入度变成0，enqueue
3. 不断重复，直到queue为空

当非DAG时，直到queue为空时仍然会有顶点未输出，由此可判断非DAG
(2)逆后根DFS结果
该方法对于非DAG也会产生结果，无法判断是否非DAG

Topo结果不唯一，只要满足优先级限制即可

4. 最短路径问题

给定两点间SP

无法直接在图中得到两个指定点的SP，但可根据”单源SP or 任意顶点对SP”的执行结果得到给定两点间SP

单源SP

问题	在有向图 G=(V,E) 中，假设每条边权重/距离已知，找到由顶点S到其余各点的最短路径
思路	1. 求出V到某点长度最短的一条路径 1. 根据1得到的已知最短路径,求出长度次短的路径 1. 依次递推,即可得到顶点V到其余顶点的最短路径

每次确定次短路径时遵循
👆上式代表了图算法中最常见的松弛操作: 4.4 最短路径 | | | 数据结构准备 |
- Dist[]:Dist[k]即起点S->K的SP长度
- Mark[]:Mark[k]=VISTED表示该点已被访问,UNVISTED为未被访问
- Path[]:存放路径倒数第二个顶点,Path[k]即保存S->…->V->K路径的V顶点
| | | 辅助方法 |
- setMark():标记某个点是否已被访问
- minVertex(G,Dist[]):返回当前SP中,最短路径V->K的起点V
| | | 实现(起点S)
Dijkstra算法 |
1. **化Dist[]:令起点Dist[S]=0,其余都设为+∞(Integer.MAX VALUE);
1. Dist[]中选取最小值的对应起点V,需保证Mark[V]为UNVISTED：首先将Mark[V]设为VISTED
1. 遍历每个和V直接邻接的顶点W：
比较D[w]【已知S-W最短距离】和D[v] + G.weight(v, w)**【S-V-W距离】,选择更短的路径,更新Dist[w],Path[w]
4. 循环,直到次数等于G.n(),此时对每个顶点都执行了setMark(),即都访问过,通过Path[]可直到起点S到任意点的最短路径,通过Dist[]可知道最短路径的长度
(可以参考右图👉,来自百度百科,觉得蛮清晰) | | | 时间开销 |
- 下面的算法：
- 外层：Dijkstra()中for循环执行|V|次
- 内层：minVertex()中for循环|V|次，如果更新Dist[],会花费
- 合计
- 对于稀疏图(sparse),使用小顶堆delMin()代替minVertex()可以获得**
| |

// Compute shortest path distances from s, store them in D
static void Dijkstra(Graph G, int s, int[] D) {
    for (int i=0; i<G.n(); i++) // Initialize
        D[i] = Integer.MAX VALUE;
    D[s] = 0;
    for (int i=0; i<G.n(); i++) { // Process the vertices
        int v = minVertex(G, D); // Find next-closest vertex
        G.setMark(v, VISITED);
        if (D[v] == Integer.MAX VALUE) return; // Unreachable
        for (int w = G.first(v); w < G.n(); w = G.next(v, w))
            if (D[w] > (D[v] + G.weight(v, w)))
                D[w] = D[v] + G.weight(v, w);
    }
}
static int minVertex(Graph G, int[] D) {
    int v = 0; // Initialize v to any unvisited vertex;
    for (int i=0; i<G.n(); i++)
        if (G.getMark(i) == UNVISITED) { v = i; break; }
    for (int i=0; i<G.n(); i++) // Now find smallest value
        if ((G.getMark(i) == UNVISITED) && (D[i] < D[v]))
            v = i;
    return v;
}

:::info 例题：给定有向图，求起点0的单源最短路径
:::

顶点对间SP

因此对于顶点数为n的G来说,想办法推导出任意两点(v,w)的n阶最短路径即可得到任意顶点对(v,w)的最短路径

| | 数据结构准备 |
- Dist[][]:n阶方阵,Dist[v][w]即保存当前(v,w)的SP,不存在时为∞

- Path[][]:n阶方阵,Path[v][w]=k说明存放(v,w)的SP倒数第二个顶点为k,此时该SP为k阶最短路径,不存在时为-1
| | 实现(起点S)
Dijkstra算法 |
1.
1.
1.
| | 时间开销** | |

:::info 举例给定有向图，表示其floyd算法过程
:::

5.最小支撑树问题

Prim算法

| 思路 | 构造树时,|V|个顶点分属两个集合:
- 在树上的点集U
- 不在树上的点集V-U
则每次从连接两集合的边中选出权值最小的加入MST,直到有|V|-1个顶点在MST中 | | :—-: | —- | | 开销 |
|

/** Compute a minimal-cost spanning tree */
static void Prim(Graph G, int s, int[] D, int[] V) {
    for (int i=0; i<G.n(); i++) // Initialize
        D[i] = Integer.MAX VALUE;
    D[s] = 0;
    for (int i=0; i<G.n(); i++) { // Process the vertices
        int v = minVertex(G, D);
        G.setMark(v, VISITED);
        if (v != s) AddEdgetoMST(V[v], v);
        if (D[v] == Integer.MAX VALUE) return; // Unreachable
        for (int w = G.first(v); w < G.n(); w = G.next(v, w))
            if (D[w] > G.weight(v, w)) {
                D[w] = G.weight(v, w);
                V[w] = v;
            }
    }
}

:::info 举例
:::

Kruskal算法(避圈法)

/** Heap element implementation for Kruskal’s algorithm */
class KruskalElem implements Comparable<KruskalElem> {
    private int v, w, weight;
    public KruskalElem(int inweight, int inv, int inw)
    { weight = inweight; v = inv; w = inw; }
    public int v1() { return v; }
    public int v2() { return w; }
    public int key() { return weight; }
    public int compareTo(KruskalElem that) {
        if (weight < that.key()) return -1;
        else if (weight == that.key()) return 0;
        else return 1;
    }
}
    /** Kruskal’s MST algorithm */
    static void Kruskal(Graph G) {
        ParPtrTree A = new ParPtrTree(G.n()); // Equivalence array
        KruskalElem[] E = new KruskalElem[G.e()]; // Minheap array
        int edgecnt = 0; // Count of edges
        for (int i=0; i<G.n(); i++) // Put edges in the array
            for (int w = G.first(i); w < G.n(); w = G.next(i, w))
                E[edgecnt++] = new KruskalElem(G.weight(i, w), i, w);
        MinHeap<KruskalElem> H =
                new MinHeap<KruskalElem>(E, edgecnt, edgecnt);
        int numMST = G.n(); // Initially n classes
        for (int i=0; numMST>1; i++) { // Combine equiv classes
            KruskalElem temp = H.removemin(); // Next cheapest
            int v = temp.v1(); int u = temp.v2();
            if (A.differ(v, u)) { // If in different classes
                A.UNION(v, u); // Combine equiv classes
                AddEdgetoMST(v, u); // Add this edge to MST
                numMST--; // One less MST
            }
        }
    }

:::info 举例
:::