2021-02-03 图的创建与遍历

下面介绍图的创建与遍历，就算是给的不是int[][] metrics数组，我们转换成这样的数组，然后再应用图的基础算法就行。

/**
 * @Author: vividzcs
 * @Date: 2021/1/24 11:43 上午
 */
public class Graph {
    private Map<Integer, Node> nodes = new HashMap<>();
    private Set<Edge> edges = new HashSet<>();

    public static Graph createGraph(int[][] metrics) {
        Graph graph = new Graph();
        for (int i=0; i<metrics.length; i++) {
            int weight = metrics[i][0];
            int from = metrics[i][1];
            int to = metrics[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 currentFrom = graph.nodes.get(from);
            Node currentTo = graph.nodes.get(to);
            currentFrom.getNexts().add(currentTo);
            currentFrom.setOut(currentFrom.getOut() + 1);
            currentTo.setIn(currentTo.getIn() + 1);

            Edge edge = new Edge(weight, currentFrom, currentTo);
            currentFrom.getEdges().add(edge);
            graph.edges.add(edge);

        }
        return graph;
    }

    public void bfs(Graph graph, Node start) {
        if (start == null) {
            return;
        }
        List<Node> queue = new ArrayList<>();
        Set<Node> sets = new HashSet<>();
        queue.add(start);
        sets.add(start);
        while (queue.size()!=0) {
            Node currentNode = queue.remove(0);
            System.out.println(currentNode.getValue());
            for (Node node : currentNode.getNexts()) {
                if (!sets.contains(node)) {
                    queue.add(node);
                    sets.add(node);
                }
            }
        }
    }

    public void dfs(Graph graph, Node start) {
        List<Node> stack = new ArrayList<>();
        Set<Node> set = new HashSet<>();

        stack.add(start);
        set.add(start);

        System.out.println(start.getValue());
        while (stack.size()!=0) {
            Node currentNode = stack.remove(stack.size() - 1);
            for (Node node : currentNode.getNexts()) {

                if (!set.contains(node)) {
                    stack.add(currentNode);
                    stack.add(node);
                    set.add(node);
                    System.out.println(node.getValue());
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        int [][] metrics = {
                {2,1,3},
                {4,1,5},
                {4,5,1},
                {6,1,7},
                {2,3,5},
                {2,5,3},
                {2,5,7},
                {3,3,6},
                {1,5,6}
        };
        Graph graph = Graph.createGraph(metrics);
        graph.bfs(graph, graph.nodes.get(1));
        System.out.println();
        graph.dfs(graph, graph.nodes.get(1));
    }
}

/**
 * @Author: vividzcs
 * @Date: 2021/1/24 11:38 上午
 */
public class Node {
    private int value;
    private int in;
    private int out;
    private List<Node> nexts = new ArrayList<>();
    private List<Edge> edges = new ArrayList<>();

    public Node(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public int getIn() {
        return in;
    }

    public void setIn(int in) {
        this.in = in;
    }

    public int getOut() {
        return out;
    }

    public void setOut(int out) {
        this.out = out;
    }

    public List<Node> getNexts() {
        return nexts;
    }

    public void setNexts(List<Node> nexts) {
        this.nexts = nexts;
    }

    public List<Edge> getEdges() {
        return edges;
    }

    public void setEdges(List<Edge> edges) {
        this.edges = edges;
    }
}

/**
 * @Author: vividzcs
 * @Date: 2021/1/24 11:40 上午
 */
public class Edge {
    private int weight;
    private Node from;
    private Node to;

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