有向无环图中的LCA（最近共同祖先），依据广度优先搜索和图G的反向图

Dear 丶 2022-07-19 02:52 17阅读 1赞

今天写题目的时候遇到的，感觉自己的想法还有点意思就写博客了，如果有错误，欢迎指正

算法用到的数据结构：

有向图的数据结构：https://github.com/xiaoyuzdy/Algorithms/blob/master/Algorithms/src/Number\_4/Digraph.java

队列：https://github.com/xiaoyuzdy/Algorithms/blob/master/Algorithms/src/Numbe\_1/Queue.java

广度优先遍历的查找顺序，比如一个无环有向图G（V，E）-----G（5，4）：   0-->1     0--->2    1--->4    1--->3 , 顶点0为起点，先找到顶点0并标记，再找顶点0指向的顶点1和顶点

2，这两个顶点标记以后再找1指向的顶点（先找1还是2有添加的边的顺序决定），1指向的顶点找完以后再找顶点2指向的顶点，如此反复

根据这个性质我们就可以使用一个链表保存顶点0可达的顶点且保存的顺序就是与顶点0由近到远的顺序

这样的话在查找顶点v和顶点w的最近共同祖先时就可以利用广度优先搜索分别以v和w为顶点得到两条链表，而链表的交集就是两个顶点的共同祖先

总体思路就是这样，下面是代码：

package Num2_4_02;
    
    import java.util.LinkedList;
    import java.util.List;
    import edu.princeton.cs.algs4.Digraph;
    import edu.princeton.cs.algs4.Queue;
    
    /**
     * P387 T21 顶点v和w的共同祖先（图G无环）
     * 顶点的输入请按规定输入，在这不做判断
     * 思路：所谓的最近祖先就是最近的一个顶点能够分别到达v和w，因此我们可以使用G的反向图和广度优先搜索结合的办法找到
     * 
     * 
     * 
     * @author he
     *
     */
    
    class LAC {
    	private Digraph G;// 图G的反向图
    	private boolean marked[];
    
    	public LAC(Digraph G) {
    		this.G = G.reverse();
    	}
    
    	/**
    	 * 在逆向图G中顶点v
    	 * 
    	 * 
    	 * 因为使用广度优先搜索，所以linkedlist保存的顺序就是顶点v指向的最近的顶点的顺序
    	 * 
    	 * @param v
    	 */
    	public Iterable<Integer> find(Digraph G, int v) {
    		marked = new boolean[G.V()];// 重置
    		Queue<Integer> queue = new Queue<Integer>();
    		List<Integer> l = new LinkedList<Integer>();
    		marked[v] = true;
    		queue.enqueue(v);
    		while (!queue.isEmpty()) {
    			int t = queue.dequeue();
    			for (int w : G.adj(t)) {
    				if (!marked[w]) {
    					l.add(w);
    					marked[w] = true;
    					queue.enqueue(w);
    				}
    			}
    		}
    		return l;
    	}
    
    	/**
    	 * 找出顶点v和顶点w的最近共同祖先
    	 * 
    	 * @param v
    	 * @param w
    	 * @return
    	 */
    	public int findLAC(int v, int w) {
    		List<Integer> lv = (List<Integer>) find(G, v);
    		List<Integer> lw = (List<Integer>) find(G, w);
    		if (lv.size() > lw.size()) {
    			for (int t : lw) {
    				if (lv.contains(t))
    					return t;
    			}
    		} else {
    
    			for (int t : lv) {
    				if (lw.contains(t))
    					return t;
    			}
    		}
    		return -1;
    	}
    
    }
    
    public class Num_4_02_21 {
    	public static void main(String[] args) {
    		Digraph G = new Digraph(6);
    		G.addEdge(2, 3);
    		G.addEdge(0, 1);
    		G.addEdge(0, 2);
    		G.addEdge(1, 4);
    		G.addEdge(1, 3);
    		G.addEdge(3, 5);
    		LAC lac = new LAC(G);
    		System.out.println(lac.findLAC(3, 4));
    
    	}
    
    }