无向图（邻接表实现）

为什么采用邻接表实现？

因为在处理实际问题中，我们经常处理的是稀疏矩阵；

不可接受的；

实现类和方法：

1.点的定义；

2.图的构造方法；

3.增加点；

4.增加边；

5.删除边；

6.打印顶点表；

7.打印邻接表；

测试只用了5个点，主要是实现图；

/**

* FileName: Graph

* Author: Jerry

* Date: 2020/2/7 16:38

* Description: 图及深度搜索和广度搜索

*/

package Graph_DFS_AND_BFS;

import java.util.*;

public class Graph {

//图的顶点集合

private Set vertexSet = new HashSet();

//图的邻接表集合

private Map> vertexListMap=new HashMap>();

//空的构造函数

public Graph(){

}

//带有参数的构造函数

public Graph(Set set,Map> vertexListMap){

this.vertexSet=set;

this.vertexListMap=vertexListMap;

for(Vertex vertex:this.vertexSet){

vertex.isVisiable=false;

}//初始化

}

public Set getVertexSet(){

return vertexSet;

}

public Map> getVertexListMap(){

return vertexListMap;

}

//插入边

public void putEdge(Vertex vertex1,Vertex vertex2){

if(!vertexSet.contains(vertex1)){

vertexSet.add(vertex1);

LinkedList vertexList1 =new LinkedList();

vertexList1.add(vertex2);

vertexListMap.put(vertex1,vertexList1);

}

else{

vertexListMap.get(vertex1).add(vertex2);

}

if(!vertexSet.contains(vertex2)){

vertexSet.add(vertex2);

LinkedList vertexList2 = new LinkedList();

vertexList2.add(vertex1);

vertexListMap.put(vertex2,vertexList2);

}

else{

vertexListMap.get(vertex2).add(vertex1);

}

}

//插入点

public void putVertex(Vertex vertex){

if(vertexSet.contains(vertex))

return;

else{

vertexSet.add(vertex);

LinkedList vertexlist = new LinkedList();

vertexListMap.put(vertex,vertexlist);

}

}

//打印顶点集

public void printVertex(){

System.out.println("顶点集为：");

for(Vertex vertex:vertexSet){

System.out.print(" "+vertex.name);

}

}

//打印邻接表

public void printEdge(){

System.out.println("邻接表为：");

for(Vertex vertex:vertexSet){

System.out.print("与"+vertex.name+"临接的点为：");

List vertexList = getVertexListMap().get(vertex);

if(vertexList!=null){

for(Vertex vertex1:vertexList){

System.out.print(vertex1.name+" ");

}

}

System.out.println();

}

}

//删除边

public void deleteEdge(Vertex vertex1,Vertex vertex2){

if(!vertexSet.contains(vertex1)||!vertexSet.contains(vertex2)){

System.out.println("输入错误！无法操作！");

return;

}

getVertexListMap().get(vertex1).remove(vertex2);

getVertexListMap().get(vertex2).remove(vertex1);

}

public boolean equal(Vertex vertex1,Vertex vertex2){

if(vertex1.name==vertex2.name){

return true;

}

else{

return false;

}

}

//删除点，复杂度较高，需要遍历邻接表，应该不会被使用

//顶点类

static class Vertex{

int name;

int weight;

boolean isVisiable;

Vertex(int data){

this.name = data;

}

}

public static void main(String []args){

Graph graph = new Graph();

Vertex vertex0 = new Vertex(0);

Vertex vertex1 = new Vertex(1);

Vertex vertex2 = new Vertex(2);

Vertex vertex3 = new Vertex(3);

Vertex vertex4 = new Vertex(4);

graph.putEdge(vertex0,vertex1);

graph.putEdge(vertex0,vertex2);

graph.putEdge(vertex1,vertex3);

graph.putEdge(vertex2,vertex3);

graph.putVertex(vertex4);

graph.deleteEdge(vertex1,vertex3);

graph.printVertex();

graph.printEdge();

}

}