图结构的实现，从点到边再到图

大家好，我是一名计算机专业的大三在校生，自不量力想明年秋招进大厂BATJMZ。由于大学里面荒废了两年，所以决定从此刻开始改变。希望通过写博客记录自己学习和成长的历程；同时也能够增长见识，学习到更多的知识，遇见更多志同道合的人。本人目前还只是个青铜，希望和我的读者朋友们可以共同进步，一起探讨。如果我的文章能够帮到你的话，那实在是我的幸运，也希望我写的博客内容能够帮助一些在编程方面有问题的朋友。在这里如果你发现我写的有哪些不对或不足之处，请您谅解。你可以及时评论或私信来告诫我，我会积极采纳改正的，我会努力提升博客文章的质量。如果可以给个三连，那真是十分感谢，‍‍‍

什么是图

1)由点的集合和边的集合构成

2)虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达

3)边上可能带有权值

图结构的表达

1)邻接表法

2)邻接矩阵法

3)除此之外还有其他众多的方式，比如，请看下面图片（用户只给出一个二维数组，如何表示出该图呢，下面代码将会通过这种方式来表示图结构）

图的面试题如何搞定

1)图的算法都不算难，只不过coding 的代价比较高

2)先用自己最熟练的方式，实现图结构的表达

3)在自己熟悉的结构上，实现所有常用的图算法作为模板

4)把面试题提供的图结构转化为自己熟悉的图结构，再调用模板或改写即可

用代码实现图(点–>边–>图)

package com.harrison.class11;

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

public class Code01_NodeEdgeGraph {
    
	// 点结构的描述
	public static class Node {
    
		public int value;// 编号
		public int in;// 入度 进到我这个点的边的数量
		public int out;// 出度 从我这个点出去的边的数量
		public ArrayList<Node> nexts;// 直接邻居 只算出度
		public ArrayList<Edge> edges;// 从我这个点出发的边

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

	// 边结构描述
	public static class Edge {
    
		public int weight;
		public Node from;
		public Node to;

		public Edge(int w, Node f, Node t) {
    
			weight = w;
			from = f;
			to = t;
		}
	}

	// 图结构描述
	public static class Graph {
    
		// key是编号，value是实际的点
		public HashMap<Integer, Node> nodes;
		public HashSet<Edge> edges;

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

	// matrix 所有的边
	// N*3 的矩阵
	// [weight, from节点上面的值，to节点上面的值]
	// [ 5 , 0 , 7]
	// [ 3 , 0, 1]
	public static Graph generateGraph(int[][] matrix) {
    
		Graph graph=new Graph();
		for(int i=0; i<matrix.length; i++) {
    
			// 每拿到一条边 matrix[i]
			int weight=matrix[i][0];
			int from=matrix[i][1];
			int 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);
			fromNode.out++;
			toNode.in++;
			fromNode.nexts.add(toNode);
			fromNode.edges.add(newEdge);
			graph.edges.add(newEdge);
		}
		return graph;
	}
}

总结

这种方法看似比较冗余，比如，点集合里已经有边了，为啥还要单独存一份呢？因为有些算法只需要你处理所有的边（最小生成树），这种表达图的方式不是最精简的，但是在这种方式下，实现各种各样的算法会更加方便，有时候甚至只需要用到这个结构的一部分，甚至一小部分。