网站建设销售销售流程/商丘 峰少 seo博客

 注意：

 有环无环的时候注意看箭头方向

不要看见成环就当成是有环了

_____________________________________________________________________________

出度，入度：

 无向图：

直接看图说：从1到0也可以  从0到1也可以  这是没有方向的 叫做无向图

 

平行边：

如图：有向图的有向边 平行边 

 

无向完全图：

 

这个权值最好是泛型的 那样通用一点，，，，，

 连通分量：

 

 邻接矩阵：

 对于边数组：两个顶点能达到则为1  不能则为0

 

无穷大  这个符号可以理解为没有这个边。。。，，，，， 

这种方式起到了节省空间的作用  ，。。。没有存在边的都省略了，，，，，

不会再开辟空间取存储0.。。 

 

我们使用邻接表进行实现

代码如下：

测试类 ： 

通过addEdge 来实现模拟出这一个图形： 

实现类：

package 图;import java.util.*;public class ListGraph<V,E> implements Graph<V,E>{private Map<V,Vertex<V,E>> vertices=new HashMap<>();private Set<Edge<V,E>> edges=new HashSet<>();@Overridepublic int EdgesSize() {return edges.size();}@Overridepublic int VerticesSize() {return vertices.size();}@Overridepublic void addVertex(V v) {if(vertices.containsKey(v)){return;}//v这个顶点上存储的值相当于key  这个顶点new Vertex<>(v) 相当于valuevertices.put(v,new Vertex<>(v));}@Overridepublic void addEdge(V from, V to, E weight) {//增加的边的起点 get()返回值为V类型  看这个点以前有没有加过//有的话返回对应value  无则返回nullVertex<V,E> fromVertex=vertices.get(from);if(fromVertex==null){fromVertex=new Vertex<>(from);//把这个对象存入  from相当于key  fromVertex这个起始顶点对象相当于Map中的valuevertices.put(from,fromVertex);}//增加边的终点Vertex<V,E> toVertex=vertices.get(to);if(toVertex==null){toVertex=new Vertex<>(to);//把这个对象存入  from相当于key  toVertex相当于Map中的valuevertices.put(to,toVertex);}Edge<V,E> edge=new Edge<>(fromVertex,toVertex);edge.weight=weight;if(fromVertex.outEdges.contains(edge)){fromVertex.outEdges.remove(edge);toVertex.outEdges.remove(edge);}fromVertex.outEdges.add(edge);toVertex.inEdges.add(edge);}@Overridepublic void addEdge(V from, V to) {addEdge(from,to,null);}@Overridepublic void removeEdge(V from, V to) {Vertex<V,E> fromVertex=vertices.get(from);if(fromVertex==null){return;}Vertex<V,E> toVertex=vertices.get(to);if(toVertex==null){return;}Edge<V,E> edge=new Edge<>(fromVertex,toVertex);if(fromVertex.outEdges.remove(edge)){toVertex.inEdges.remove(edge);edges.remove(edge);}}@Overridepublic void removeVertex(V v) {}/*** 创建内部类 用来存储属性信息* 这个节点是不对外公开的 只能传进来V E*///顶点private static class Vertex<V,E> {V value;//表示点上面对应的值 应该是泛型 可能表示微信好友之类的等等泛型对象可能/*** inEdges表示以Vertex这个点为 从它这里进来的边  就是以这个点为终点的边** outEdges表示从它这里出去的边  就是以这个点为起点的边** 因为inEdges outEdges这里面存放的是边对象Edge<V,E>*/Set<Edge<V,E>> inEdges=new HashSet<>();Set<Edge<V,E>> outEdges=new HashSet<>();public Vertex(V value) {this.value=value;}@Overridepublic int hashCode() {return value==null?0:value.hashCode();}/***比较传进来的obj与自身value是否相同*/@Overridepublic boolean equals(Object obj) {return Objects.equals(value,((Vertex<V,E>)obj).value);}}//边private static class Edge<V,E>{Vertex<V,E> from;//边要有一个起点Vertex<V,E> to;//边要有一个终点E weight;//边要有一个权重public Edge(Vertex<V,E> from, ListGraph.Vertex<V,E> to) {this.from = from;this.to = to;}@Overridepublic int hashCode() {return from.hashCode()*31+ to.hashCode();}@Overridepublic boolean equals(Object obj) {ListGraph.Edge<V,E> edge=((ListGraph.Edge<V, E>)obj);return Objects.equals(from,edge.from)&&Objects.equals(to,edge.to);}}}

接口：

package 图;public interface Graph<V,E>{int EdgesSize();//边数int VerticesSize();//顶点数void addVertex(V v);//增加顶点void addEdge(V from,V to,E weight);void addEdge(V from,V to);//可能有权重 也可能不增加权重void removeVertex(V v);void removeEdge(V from,V to);
}

其他的还没写完 

准备把哈希表再学一遍再学图，，，，

未完待续。。。。。这两天有其他任务了，，，，，，

第八个第5min