数据结构-5-图

图的存储方式

图的顶点结构

public class Node {

    // 图节点的值
    public int value;

    // 图节点的出度
    public int out;

    // 图节点的入度
    public int in;

    // 图的邻接点
    public ArrayList<Node> nexts;

    // 图的边
    public ArrayList<Edge> edges;

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

图的边结构

public class Edge {

    // 边的权值
    public int weight;

    // 边的起始节点
    public Node from;

    // 边的终止节点
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

图的邻接表结构

public class Graph {

    // 图的顶点集合
    public HashMap<Integer, Node> nodes;

    // 图的边集合
    public HashSet<Edge> edges;

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

根据三元组生成图

public class GraphGenerator {

    /**
     * 根据三元组构造图
     *
     * @param matrix 邻接矩阵
     * @return 邻接表
     */
    public Graph createGraph(Integer[][] matrix) {
        Graph graph = new Graph();

        for (int i = 0; i < matrix.length; i++) {
            // 设置权值
            Integer weight = matrix[i][0];
            // 设置起始节点的值
            Integer from = matrix[i][1];
            // 设置终止节点的值
            Integer to = matrix[i][2];

            // 如果起始节点第一次出现，将（起始节点的值，起始节点）放入哈希表
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }

            // 初始化起始节点
            Node fromNode = graph.nodes.get(from);
            // 初始化终止节点
            Node toNode = graph.nodes.get(to);
            // 初始化边节点
            Edge newEdge = new Edge(weight, fromNode, toNode);

            // 起始节点的邻接点设置成toNode
            fromNode.nexts.add(toNode);
            // 起始节点的出度++
            fromNode.out++;
            // 终止节点的入度++
            toNode.in++;
            // 更新起始节点的边信息
            fromNode.edges.add(newEdge);
            // 更新图的边信息
            graph.edges.add(newEdge);

        }
        return graph;
    }
}

图的遍历

深度优先遍历

算法思想

方式1 非递归实现

1. 利用栈实现
2. 从源节点开始按照深度放入栈，然后弹出
3. 每弹出一个节点，就把节点下一个没有进栈的邻节点放入栈
4. 直到栈变空

// 非递归实现
public void dfs(Node node) {
    // 如果节点不存在，则返回
    if (node == null) {
        return;
    }

    // 定义递归栈
    Stack<Node> stack = new Stack<>();
    // 定义标记数组
    HashSet<Node> set = new HashSet<>();

    // 当前节点入栈
    stack.add(node);
    // 同时标记为已访问
    set.add(node);

    // Visit操作
    System.out.println(node.value);

    while (!stack.isEmpty()) {
        // 栈顶元素出栈
        Node cur = stack.pop();
        // 遍历栈顶元素的邻接点
        for (Node next : cur.nexts) {
            // 若next没有被访问过
            if (!set.contains(next)) {
                // 当前节点cur继续压栈，其邻接点没有被访问完
                stack.push(cur);
                // 当前节点cur的邻接点next压栈
                stack.add(next);
                // Visit操作
                System.out.println(next.value);
                // break
                break;
            }
        }
    }
}

方式2 递归实现

广度优先遍历

1. 利用队列实现
2. 从源节点开始依次按照宽度进队列，然后弹出
3. 每弹出一个节点，就把该节点所有没有进过队列的邻节点放入队列
4. 直到队列变空

public void bfs(Node node) {
    // 节点不存在，则返回
    if (node == null) {
        return;
    }

    // 定义队列存储节点
    Queue<Node> queue = new LinkedList<>();
    // 定义哈希集合标记是否已访问过
    HashSet<Object> set = new HashSet<>();

    // 当前节点入队
    queue.offer(node);
    // 并且标记为已访问
    set.add(node);

    while (!queue.isEmpty()) {
        // 当前节点出队
        Node cur = queue.poll();
        // 访问当前节点 Visit操作
        System.out.println(cur.value);

        // 将当前节点的所有邻节点访问完
        for (Node next : cur.nexts) {
            // 若当前节点的所有邻接点没有访问过
            if (!set.contains(next)) {
                // 标记为已访问
                set.add(next);
                // 该节点入队
                queue.offer(next);
            }
        }
    }
}

拓扑排序

public List<Node> sortedTopology(Graph graph) {
    // inMap存储节点的入度
    Map<Node, Integer> inMap = new HashMap<>();
    // zeroInQueue存储入度为0的节点
    Queue<Node> zeroInQueue  = new LinkedList<>();

    // 图的所有顶点的入度记录下来
    for (Node node : graph.nodes.values()) {
        // 存入node的入度
        inMap.put(node, node.in);
        if (node.in == 0) {
            zeroInQueue.add(node);
        }
    }
    // 存储拓扑排序结果
    List<Node> result = new ArrayList<>();

    while (!zeroInQueue.isEmpty()) {
        // 队列中挑选一个入度为0的节点存储在结果集中
        Node cur = zeroInQueue.poll();
        result.add(cur);
        for (Node next : cur.nexts) {
            // 更新cur节点所有邻接节点的入度
            inMap.put(next, inMap.get(next) - 1);
            // 一旦入度为0，则送入队列
            if (inMap.get(next) == 0) {
                zeroInQueue.add(next);
            }
        }
    }
    return result;
}

Prim

前提：

要求无向图

比较器

// 定义比较器
public class EdgeComparator  implements Comparator<Edge> {
    @Override
    public int compare(Edge o1, Edge o2) {
        return o1.weight - o2.weight;
    }
}

邻接表实现

// 邻接表实现
public Set<Edge> prim(Graph graph) {
    // 存储边集合的小根堆
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
    HashSet<Node> set = new HashSet<>();
    HashSet<Edge> result = new HashSet<>();

    for (Node node : graph.nodes.values()) {
        // 如果node没有访问过
        if (!set.contains(node)) {
            set.add(node);
            // 将node相连的边压入优先队列
            for (Edge edge : node.edges) {
                priorityQueue.add(edge);
            }
            while (!priorityQueue.isEmpty()) {
                // 弹出与node相连权值最小边
                Edge edge = priorityQueue.poll();
                // 选择该边的邻接点
                Node toNode = edge.to;
                if (!set.contains(toNode)) {
                    // 将toNode标记为已访问
                    set.add(toNode);
                    // 将选中的权值最小边纳入result
                    result.add(edge);
                    // 从加入到最小生成树的节点出发，将其相连的边放入优先队列
                    for (Edge nextEdge : toNode.edges) {
                        priorityQueue.add(nextEdge);
                    }
                }
            }
        }
    }
    return result;
}

邻接矩阵实现

// 邻接矩阵实现
public int Prim(int[][] graph) {
    int size = graph.length;
    // distances存储边权值的最小值
    int[] distances = new int[size];
    // 标记是否加入到最小生成树中
    boolean[] visit = new boolean[size];
    // 初始化
    visit[0] = true;
    // distances初始化成0到各顶点的权值
    for (int i = 0; i < size; i++) {
        distances[i] = graph[0][i];
    }
    // 定义最小代价
    int sum = 0;
    for (int i = 0; i < size; i++) {
        // 存储路径权值最小值
        int minPath = Integer.MAX_VALUE;
        // 存储顶点编号
        int minIndex = -1;
        // 从distances中选权值最小的边
        for (int j = 0; j < size; j++) {
            if (!visit[j] && distances[j] < minPath) {
                minPath = distances[j];
                minIndex = j;
            }
        }
        if (minIndex == -1) {
            return sum;
        }
        // 顶点为minIndex节点加入最小生成树
        visit[minIndex] = true;
        sum += minPath;
        // 更新distances数组
        for (int j = 0; j < size; j++) {
            // 如果当前顶点没有加入生成树且minIndex到j的距离小于原先distances[j]的距离
            if (!visit[j] && distances[j] > graph[minIndex][j]) {
                distances[j] = graph[minIndex][j];
            }
        }
    }
    return sum;
}

Kruskal

并查集结构

public class UnionFind {

    // 保存并查集中所有集合的所有元素的代表节点
    // <Node, Node's Father>
    private HashMap<Node, Node> fatherMap;

    // 保存节点所在集合的秩（集合元素数）
    private HashMap<Node, Integer> rankMap;

    public UnionFind() {
        this.fatherMap = new HashMap<>();
        this.rankMap = new HashMap<>();
    }

    // 找到father节点
    private Node findFather(Node node) {
        Node father =  fatherMap.get(node);
        if (father != node) {
            father = findFather(father);
        }
        fatherMap.put(node, father);
        return father;
    }

    // 初始化并查集所有单个元素，father指向自己，rank置1
    public void makeSets(Collection<Node> nodes) {
        fatherMap.clear();
        rankMap.clear();
        for (Node node : nodes) {
            fatherMap.put(node, node);
            rankMap.put(node, 1);
        }
    }

    // 判断a、b是否属于一个集合
    public boolean isSameSet(Node a, Node b) {
        return findFather(a) == findFather(b);
    }

    // 将a所在的集合和b所在的集合合并
    public void union(Node a, Node b) {
        // 若a、b为空
        if (a == null || b == null) {
            return;
        }
        // 找到a的代表节点
        Node aFather = findFather(a);
        // 找到b的代表节点
        Node bFather = findFather(b);
        // 合并操作
        if (aFather != bFather) {
            // a所在集合元素个数
            int aFrank = rankMap.get(aFather);
            // b所在集合元素个数
            int bFrank = rankMap.get(bFather);
            // 将少的归并到多的集合中
            if (aFrank <= bFrank) {
                // a所在的集合并到b所在的集合中
                fatherMap.put(aFather, bFather);
                rankMap.put(bFather, aFrank + bFrank);
            } else {
                // b所在的集合并到a所在的集合中
                fatherMap.put(bFather, aFather);
                rankMap.put(aFather, aFrank + bFrank);
            }
        }

    }
}

比较器

// 比较器
public class EdgeComparator implements Comparator<Edge> {
    @Override
    public int compare(Edge o1, Edge o2) {
        return o1.weight - o2.weight;
    }
}

Kruskal

public Set<Edge> kruskal(Graph graph) {
    // 定义并查集结构
    UnionFind unionFind = new UnionFind();
    // 初始化并查集
    unionFind.makeSets(graph.nodes.values());
    // 定义优先队列存储边集合
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());

    for (Edge edge : graph.edges) {
        priorityQueue.add(edge);
    }

    Set<Edge> result = new HashSet<>();

    while (!priorityQueue.isEmpty()) {
        // 弹出边集合中最小的边
        Edge edge = priorityQueue.poll();
        if (!unionFind.isSameSet(edge.from, edge.to)) {
            result.add(edge);
        }
    }
    return result;
}

Dijkstra

原始版本

getMinDistanceAndUnselectedNode

// 获取最小距离且没有选择的结点，返回没有被选入最短路径且head到nodes距离更短的节点
public Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {

    Node minNode = null;
    int minDistance = Integer.MAX_VALUE;
    for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
        // 获取视图的键，即图顶点
        Node node = entry.getKey();
        // 获取距离[head-->node]
        int distance = entry.getValue();
        // 如果当前nodes没有被选入最短路径中，且[head-->nodes]距离更短，更新一下minNode和最小距离
        if (!touchedNodes.contains(node) && distance < minDistance) {
            minNode = node;
            minDistance = distance;
        }
    }
    return minNode;
}

Dijkstra

// 未优化版本
//  从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
public HashMap<Node, Integer> dijkstra(Node head, int size) {
    /**
     * distanceMap 表示从head出发到所有点的最小距离
     * Node 从head出发到Node
     * Integer 从head出发到达Node的最小距离
     * 如果在表中，没有T的记录，含义是从head出发到T这个点的距离为正无穷
     */
    HashMap<Node, Integer> distanceMap = new HashMap<>();
    // 初始化distanceMap
    distanceMap.put(head, 0);
    // 已经求过距离的节点存储在selectedNodes
    HashSet<Node> selectedNodes = new HashSet<>();
    // 得到最小距离并且没有求过的节点
    Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
    while (minNode != null) {
        // 从head出发到minNode的最小距离
        int distance = distanceMap.get(minNode);
        for (Edge edge : minNode.edges) {
            // edge的另一个邻节点
            Node toNode = edge.to;
            // 如果toNode第一次出现过，计算距离
            if (!distanceMap.containsKey(toNode)) {
                // 距离更新成 distance[head-->minNode] + edge.weight[midNode-->toNode]
                distanceMap.put(toNode, distance + edge.weight);
            } else {
                distanceMap.put(edge.to,
                        // 从源节点出发到toNode的最小距离[head-->toNode]   原路径
                        Math.min(distanceMap.get(toNode),
                                // 当前处理结点 找到的新路径[head-->minNode]+[minNode-->toNode] 新路径
                                distance + edge.weight));
            }
            // 设置成已求过
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
    }
    return distanceMap;
}

优化版本

存在问题 对于dist数组每次挑选最小距离改用堆存储，需要手动改写堆，降低该操作的时间复杂度

系统提供的堆无法做到的事情:

• 已经入堆的元素，如果参与排序的指标方法变化，系统提供的堆无法做到时间复杂度O(logN)调整！都是O(N)的调整！
• 系统提供的堆只能弹出堆顶，做不到自由删除任何一个堆中的元素，或者说，无法在时间复杂度O(logN)内完成！一定会高于O(logN)
• 在一个已经组织好的大根堆或者小根堆中，更改其中的某个值后，仍要求其为大根堆或者小根堆 ，系统堆是无法实现的
• 根本原因：：无反向索引表

手写堆

定义结构

//堆
private Node[] nodes;
//堆上节点的索引
private HashMap<Node, Integer> heapIndexMap;
//head到Node的最小距离
private HashMap<Node, Integer> distanceMap;
//堆大小
private int size;

public NodeHeap(int size) {
    this.nodes = new Node[size];
    this.heapIndexMap = new HashMap<>();
    this.distanceMap = new HashMap<>();
    this.size = 0;
}

判断堆空

/**
 * 判断堆空
 * @return
 */
public boolean isEmpty() {
    return size == 0;
}

弹出堆顶元素

/**
 * 弹出堆顶元素
 * @return
 */
public NodeRecord pop() {
    //记录下堆顶元素信息
    NodeRecord nodeRecord = new NodeRecord(nodes[0],                  distanceMap.get(nodes[0]));
    //堆顶元素下去
    swap(0, size - 1);
    /**
     * 记录换下去的堆顶元素的位置，-1表示进过堆但不在堆上了
     */
    heapIndexMap.put(nodes[size - 1], -1);
    //原堆顶元素弹出，说明已经纳入最短路径了，distanceMap释放掉他
    distanceMap.remove(nodes[size - 1]);
    //释放掉
    nodes[size - 1] = null;
    //重新调整成小根堆
    heapify(0, --size);
    //返回原先堆顶元素的信息，即最小距离的那个节点信息
    return nodeRecord;
}

堆结构变化后调整

/**
 * 堆结构变化后堆的调整
 * @param node
 * @param index
 */
private void insertHeapify(Node node, int index) {
    //孩子距离小于父亲距离时，向上调整
    while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
        swap(index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

就地调整

/**
 * 就地调整
 * @param index
 * @param size
 */
public void heapify(int index, int size) {
    //指向index的左孩子
    int left = index * 2 + 1;
    while (left < size) {
        //挑出index左右两个孩子较小的进行调整
        int smallest = left + 1 < size &&
        distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left]) ? left + 1 : left;
        //当前距离较小的孩子与父亲比较，若父亲大需要调整
        smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
        if (smallest == index) {
            break;
        }
        swap(smallest, index);
        index = smallest;
        left = index * 2 + 1;
    }
}

是否进过堆

/**
 * 是否进过堆
 * @param node
 * @return
 */
private boolean isEntered(Node node) {
    return heapIndexMap.containsKey(node);
}

是否在堆上

/**
 * 当前进来过且index不是-1 说明在堆上
 * @param node
 * @return 是否在堆上
 */
private boolean inHeap(Node node) {
    return isEntered(node) && heapIndexMap.get(node) != -1;
}

交换堆上的节点

/**
 * 交换堆上的节点
 * @param index1
 * @param index2
 */
private void swap(int index1, int index2) {
    //index1的位置换成index2
    heapIndexMap.put(nodes[index1], index2);
    //index2的位置换成index1
    heapIndexMap.put(nodes[index2], index1);
    //交换index1和index2两个Node节点
    Node tmp = nodes[index1];
    nodes[index1] = nodes[index2];
    nodes[index2] = tmp;
}

决定node是否并入路径

/**
 * 决定node是否并入最短路径
 * @param node 从head出发到node节点
 * @param distance 新的距离
 */
public void addOrUpdateOrIgnore(Node node, int distance) {
    //如果node在堆上
    if (inHeap(node)) {
        //node之前的距离distanceMap.get(node)和现在的距离distance取最小
        distanceMap.put(node, Math.min(distanceMap.get(node), distance));
        //距离更新了，可能需要调整（维持的是以距离为媒介的小根堆）
        insertHeapify(node, heapIndexMap.get(node));
    }
    //没有进过堆，新建记录
    if (!isEntered(node)) {
        nodes[size] = node;
        heapIndexMap.put(node, size);
        //当前到node的距离设置成distance
        distanceMap.put(node, distance);
        //向上调整
        insertHeapify(node, size++);
    }
    //剩下进来但不在堆上，直接忽略（计算过了）
}

Dijkstra优化算法

/**
 * Dijkstra优化算法
 * @param head
 * @param size
 * @return
 */
public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
    //新建堆
    NodeHeap nodeHeap = new NodeHeap(size);
    //从head开始，旧的最短距离是0
    nodeHeap.addOrUpdateOrIgnore(head,0);
    HashMap<Node, Integer> result = new HashMap<>();
    while (!nodeHeap.isEmpty()) {
        //将小根堆堆顶弹出
        NodeRecord record = nodeHeap.pop();
        //记录节点
        Node cur = record.node;
        //记录下新的距离[head:node]
        int distance = record.distance;

        for (Edge edge : cur.edges) {
            //新的距离 [head:node] + [node:toNode] 和 老的距离 [head:toNode]
            //是否并入最短路径的节点toNode
            nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
        }
        result.put(cur, distance);
    }
    return result;
}

Floyd

/**
 * Floyd
 * @author Cyan
 * @date 2022-06-06
 */
public class Code7Floyd {
    public static void Floyd(int[][] graph, int[][] path) {
        int i, j, k;
        int[][] temp = new int[graph.length][graph.length]; 
        
        for (i = 0; i < graph.length; i++) {
            for (j = 0; j < graph.length; j++) {
                path[i][j] = -1;
                temp[i][j] = graph[i][j];
            }
        }
        
        /**
         * 以k顶点为中介对所有顶点对(i, j)进行检测和修改
         */
        for (i = 0; i < graph.length; i++) {
            for (j = 0; j < graph.length; j++) {
               for (k = 0; k < graph.length; k++) {
                   if (temp[i][j] > temp[i][k] + temp[k][j]) {
                       temp[i][j] = temp[i][k] + temp[k][j];
                       path[i][j] = k;
                   }
               }
            }
        }
    }
}