【数据结构的魅力】008.图

import java.util.ArrayList;

//点结构的描述
public class Node {
    public int value;
    //入度
    public int in;
    //出度
    public int out;
    public ArrayList nexts;
    public ArrayList 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;
    }
}

import java.util.HashMap;
import java.util.HashSet;

public class Graph {
    public HashMap nodes;
    public HashSet edges;

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

public class GraphGenerator {
    public static Graph createGraph(Integer[][] matrix){
        Graph graph = new Graph();
        for(int i=0;i 
广度优先 
import java.util.HashSet;
import java.util.linkedList;
import java.util.Queue;

public class BFS {
    public static void bfs(Node node){
        if(node == null){
            return;
        }
        Queue queue = new linkedList<>();
        HashSet set = new HashSet<>();
        queue.add(node);
        set.add(node);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.println(cur.value);
            for(Node next : cur.nexts){
                if(!set.contains(next)){
                    set.add(next);
                    queue.add(next);
                }
            }
        }
    }
}
 
深度优先 
import java.util.HashSet;
import java.util.Stack;

public class DFS {
    public static void dfs(Node node){
        if(node == null){
            return;
        }
        Stack stack = new Stack<>();
        HashSet set = new HashSet<>();
        stack.add(node);
        set.add(node);
        System.out.println(node.value);
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            for(Node next : cur.nexts){
                if(!set.contains(next)){
                    stack.push(cur);
                    stack.push(next);
                    set.add(next);
                    System.out.println(next.value);
                    break;
                }
            }
        }
    }
}
 
拓扑排序 
import java.util.*;

public class TopologySort {
    public static List sortedTopology(Graph graph){
        HashMap inMap = new HashMap<>();
        //只有入度为0的点才能进入队列
        Queue zeroInQueue = new linkedList<>();
        for(Node node : graph.nodes.values()){
            inMap.put(node, node.in);
            if(node.in == 0){
                zeroInQueue.add(node);
            }
        }
        //拓扑排序的结果,依次加入result
        List result = new ArrayList<>();
        while (!zeroInQueue.isEmpty()){
            Node cur = zeroInQueue.poll();
            result.add(cur);
            for(Node next : cur.nexts){
                inMap.put(next,inMap.get(next)-1);
                if(inMap.get(next) == 0){
                    zeroInQueue.add(next);
                }
            }
        }
        return result;
    }
}