蛮力法/u到v是否存在简单路径

深度优先看看从u出发是否能够到达v

package xcrj.kchalgorithm.bruteForce.graph;

import java.util.ArrayList;
import java.util.List;

/** * u到v的简单路径（路径上的顶点不重复） * 利用深度优先遍历 */
public class UVSimplePath {
    
    static int n = 5;
    static int[] visited = new int[n];

    /** * 从u到v是否存在简单路径 */
    static boolean dfsSimplePath(ALGraph alGraph, int u, int v) {
    
        visited[u] = 1;
        if (u == v) {
    
            return true;
        }
        // 取vertex第一个边点
        ArcNode p = alGraph.getAdjList().get(u).getFirstArcNode();
        while (p != null) {
    
            // 未被访问
            if (0 == visited[p.getAdjVertex()]) {
    
                // 深度取下一个边点
                System.out.println(" 点" + u + "-权值" + p.getWeight() + "->点" + p.getAdjVertex());
                boolean flag = dfsSimplePath(alGraph, p.getAdjVertex(), v);
                if (true == flag) {
    
                    return true;
                }
            }
            // 深度优先，广度次之
            p = p.getNextArcNode();
        }
        return false;
    }

    /** * 有方向带权图 */
    public static void directedWeightedGraph() {
    
        // 初始化邻接表
        int n = DFSAdjTable.n;
        int e = 6;
        ALGraph alGraph = new ALGraph();
        alGraph.setN(n);
        alGraph.setE(e);
        // adjList，AVNode顶点，ArcNode边点
        List<AVNode> adjList = new ArrayList<>(n);
        // 0到4
        AVNode avNode0 = new AVNode();
        avNode0.setNo(0);
        ArcNode arcNode04 = new ArcNode(6, 4, null);
        avNode0.setFirstArcNode(arcNode04);
        adjList.add(avNode0);
        // 1到0 2
        AVNode avNode1 = new AVNode();
        avNode1.setNo(1);
        ArcNode arcNode12 = new ArcNode(3, 2, null);
        ArcNode arcNode10 = new ArcNode(9, 0, arcNode12);
        avNode1.setFirstArcNode(arcNode10);
        adjList.add(avNode1);
        // 2到0 3
        AVNode avNode2 = new AVNode();
        avNode2.setNo(2);
        ArcNode arcNode23 = new ArcNode(5, 3, null);
        ArcNode arcNode20 = new ArcNode(2, 0, arcNode23);
        avNode2.setFirstArcNode(arcNode20);
        adjList.add(avNode2);
        // 3到4
        AVNode avNode3 = new AVNode();
        avNode3.setNo(3);
        ArcNode arcNode34 = new ArcNode(1, 4, null);
        avNode3.setFirstArcNode(arcNode34);
        adjList.add(avNode3);
        // 4
        AVNode avNode4 = new AVNode();
        avNode4.setNo(4);
        avNode4.setFirstArcNode(null);
        adjList.add(avNode4);
        alGraph.setAdjList(adjList);
        // dfs
        dfsSimplePath(alGraph, 1, 4);
    }

    /** * 无方向带权图 */
    public static void undirectedWeightedGraph() {
    
        // 初始化邻接表
        int n = DFSAdjTable.n;
        int e = 6;
        ALGraph alGraph = new ALGraph();
        alGraph.setN(n);
        alGraph.setE(e);
        // adjList，AVNode顶点，ArcNode边点
        List<AVNode> adjList = new ArrayList<>(n);
        // 0与1 2 4相连
        AVNode avNode0 = new AVNode();
        avNode0.setNo(0);
        ArcNode arcNode04 = new ArcNode(6, 4, null);
        ArcNode arcNode02 = new ArcNode(2, 2, arcNode04);
        ArcNode arcNode01 = new ArcNode(9, 1, arcNode02);
        avNode0.setFirstArcNode(arcNode01);
        adjList.add(avNode0);
        // 1与0 2相连
        AVNode avNode1 = new AVNode();
        avNode1.setNo(1);
        ArcNode arcNode12 = new ArcNode(3, 2, null);
        ArcNode arcNode10 = new ArcNode(9, 0, arcNode12);
        avNode1.setFirstArcNode(arcNode10);
        adjList.add(avNode1);
        // 2与0 1 3相连
        AVNode avNode2 = new AVNode();
        avNode2.setNo(2);
        ArcNode arcNode23 = new ArcNode(5, 3, null);
        ArcNode arcNode21 = new ArcNode(3, 1, arcNode23);
        ArcNode arcNode20 = new ArcNode(2, 0, arcNode21);
        avNode2.setFirstArcNode(arcNode20);
        adjList.add(avNode2);
        // 3与2 4相连
        AVNode avNode3 = new AVNode();
        avNode3.setNo(3);
        ArcNode arcNode34 = new ArcNode(1, 4, null);
        ArcNode arcNode32 = new ArcNode(5, 2, arcNode34);
        avNode3.setFirstArcNode(arcNode32);
        adjList.add(avNode3);
        // 4与0 3相连
        AVNode avNode4 = new AVNode();
        avNode4.setNo(4);
        ArcNode arcNode43 = new ArcNode(1, 3, null);
        ArcNode arcNode40 = new ArcNode(6, 0, arcNode43);
        avNode4.setFirstArcNode(arcNode40);
        adjList.add(avNode4);
        alGraph.setAdjList(adjList);
        // 深度优先遍历
        dfsSimplePath(alGraph, 0, 4);
    }

    public static void main(String[] args) {
    
        undirectedWeightedGraph();
// directedWeightedGraph();
    }
}