图的数据结构

秒速五厘米 2022-02-05 07:19 234阅读 0赞

# 图的表示（数组） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70]

# 图的数据结构 #

/*** * 图 */
    public class Graph { 
    	public HashMap<Integer,Node> nodes;//点
    	public HashSet<Edge> edges;//边
    
    	public Graph() { 
    		nodes = new HashMap<>();
    		edges = new HashSet<>();
    	}
    }

# 点的数据结构 #

/*** *图中节点 */
    public class Node { 
    	public int value;
    	public int in;//入（多少节点指向我）
    	public int out;//出
    	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;
    	}
    }

# 生成图算法 #

/*** * 从数组获取两节点，和权重 * 将两个点添加到图中 * 从图中获取两个点 * 起始点的邻居添加结束点 * 起始点的出度增加1 * 结束点的入度增加1 * 起始点的边添加一条新的边 * 图的边添加一条新的边 * @param matrix * @return */
    	public static Graph createGraph(Integer[][] matrix) { 
    		Graph graph = new Graph();
    		for (int i = 0; i < matrix.length; i++) { 
    			Integer from = matrix[i][0];
    			Integer to = matrix[i][1];
    			Integer weight = 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);
    			fromNode.nexts.add(toNode);
    			fromNode.out++;
    			toNode.in++;
    			fromNode.edges.add(newEdge);
    			graph.edges.add(newEdge);
    		}
    		return graph;
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzA5MzUwMQ_size_16_color_FFFFFF_t_70]: /images/20220205/eea92cc5085d4bc58ad1884d6443b298.png