大家好，我是一名计算机专业的大三在校生，自不量力想明年秋招进大厂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; } }
总结
这种方法看似比较冗余，比如，点集合里已经有边了，为啥还要单独存一份呢？因为有些算法只需要你处理所有的边（最小生成树），这种表达图的方式不是最精简的，但是在这种方式下，实现各种各样的算法会更加方便，有时候甚至只需要用到这个结构的一部分，甚至一小部分。
