1.相关概念
应用：图应用很广泛比如社交网络、地图导航、游戏开发等
有向图：
入度/出度：比如上面的有环3节点入度是2出度是1
无向图：（其实类似每一条边有2条入度和出度的有向图）
有权图：边可以拥有权值
连通图：如果无向图中任意2个顶点都是连通的
实现方式
邻接矩阵（一维数组存放顶点信息，二维数组存放边信息和权值，相比邻接表比较浪费内存）
邻接表（链表实现）
以下是图的基础接口、顶点定义、边定义
//顶点数量intverticesSize();//边数量intedgesSize();//操作顶点voidaddVertex(Vv);voidremoveVertex(Vv);//操作边voidaddEdge(VfromV,VtoV);voidaddEdge(VfromV,VtoV,Eweight);voidremoveEdge(VfromV,VtoV);privatestaticclassVertexV,E{VvalueSetEdgeV,EinEdges=newHashSet();SetEdgeV,EoutEdges=newHashSet();Vertex(Vvalue){this.value=value;}}privatestaticclassEdgeV,E{VertexV,Efrom;VertexV,Eto;}图的两种常见的遍历方式：
广度优先搜索（BreadthFirstSearch，BFS）(二叉树层序遍历就是一种BFS借助队列)
privatevoidbfs(VertexV,EbeginVertex){SetVertexV,EvisitedVertices=newHashSet();QueueVertexV,Equeue=newLinkedList();queue.offer(beginVertex);visitedVertices.add(beginVertex);while(!queue.isEmpty()){VertexV,Evertex=queue.poll();System.out.println(vertex.value);for(EdgeV,Eedge:vertex.outEdges){if(visitedVertices.contains(edge.to))continue;queue.offer(edge.to);visitedVertices.add(edge.to);}}}深度优先搜索（DepthFirstSearch，DFS）（二叉树前序遍历就是一种DFS借助栈）
//递归实现privatevoiddfs(VertexV,Evertex,SetVertexV,EvisitedVertices){System.out.println(vertex.value);visitedVertices.add(vertex);for(EdgeV,Eedge:vertex.outEdges){if(visitedVertices.contains(edge.to))contains;dfs(edge.to,visitedVertices);}}//非递归实现privatevoiddfs(VertexV,EbeginVertex){SetVertexV,EvisitedVertices=newHashSet();StackVertexV,Estack=newStack();stack.push(beginVertex);visitedVertices.add(beginVertex);System.out.println(beginVertex.value);while(!stack.isEmpty()){VertexV,Evertex=stack.pop()for(EdgeV,Eedge:vertex.outEdges){if(visitedVertices.contains(edge.to))continue;stack.push(edge.from);stack.push(edge.to);visitedVertices.add(edge.to);System.out.println(edge.to.value);break;}}}PS：未完待续，觉得写的不错的各位观众老爷点点左上角