邻接表创建无向图

1.首先要明白邻接表的存储结构

      顶点集合（数组存储）           与顶点相连的其他顶点（链表存储）

         v0    -> v2->v3->v1

         v1    ->v2->v0

         v2    ->v0->v3->v1

        v3     ->v0->v2

2.顶点与边的数据结构

   顶点的数据结构

public class VertexNode {
    private String data;   //存放顶点结点信息   比如名称
    private EdgeNode firstEdge;  //指向与该结点相连的 顶点集合 的第一个结点
   //为了简洁，省略get,set方法
}

边的数据结构

public class EdgeNode {
    private int adjvex;  //存放该顶点在顶点列表中的下标（位置）
    private int weight;  //权值  对于非网图可以不需要  所谓网图：就是带权的图
    private EdgeNode next; //下一个邻接点

     //省略get,set方法

}

图的数据结构

public class AdjacentTable {
    private static final int MAX_SIZE = 100;        //能存放的最大顶点数
    private VertexNode[] vertexNodes = new VertexNode[MAX_SIZE];   //存放顶点的数组
    private int vertexNum;      //顶点数   不能超过能存放顶点数的最大值
    private int edgeNum;          //边数   不能超过无向图的最大边数 即  n(n-1)/2   n为顶点数

//省略get,set方法

}

3.实现与测试

/**
 * 测试：
 *      创建一个无向图 顶点集（v0,v1,v2,v3,v4)  边集{(v0,v1),(v1,v2),(v2,v3),(v3,v0),(v0,v2)}
 *      与顶点相关的其他结点插入的方法：头插法   比如  v0->v1   想插入v2 ,v3  1)v0->v2-v1 2)v0->v3->v2-v1
 *      vo是边的起始点，也是每个链表的头结点
 */
public class GraphApplication {

    public static void main(String[] args){
        AdjacentTable g = createGraph();
        traverseGraph(g);
    }

    private static AdjacentTable createGraph(){
        AdjacentTable graph = new AdjacentTable();
        System.out.println("输入顶点数：");
        Scanner sc = new Scanner(System.in);
        int vertexNum = sc.nextInt();

        System.out.println("输入边数（边数不能超过无向图的最大边数）：");
        int edgeNum = sc.nextInt();
        graph.setVertexNum(vertexNum);
        graph.setEdgeNum(edgeNum);

        //初始化顶点数组
        for(int i = 0; i < vertexNum; i++){
            VertexNode v = new VertexNode();
            v.setData("v" + i);  //此处直接赋 v0  v1 ...值
            graph.getVertexNodes()[i] = v;
        }

        //将各个顶点与边集进行连接
        VertexNode[] vertexNodes = graph.getVertexNodes();
        for(int i = 0; i < edgeNum; i++){
            System.out.println("输入边（vi,vj）的起点");
            int start = sc.nextInt();
            System.out.println("输入边（vi,vj）的终点");
            int end = sc.nextInt();

            //以头插法的方式插入到链表中
            EdgeNode edgeNodei = new EdgeNode();
            edgeNodei.setAdjvex(end);
            edgeNodei.setNext(vertexNodes[start].getFirstEdge());
            vertexNodes[start].setFirstEdge(edgeNodei);

            //因为是无向图  vi到vj有边  那么 vj到vi也有边
            EdgeNode edgeNodej = new EdgeNode();
            edgeNodej.setAdjvex(start);
            edgeNodej.setNext(vertexNodes[end].getFirstEdge());
            vertexNodes[end].setFirstEdge(edgeNodej);
        }
        return graph;
    }

    public static void traverseGraph(AdjacentTable g){
        for(int i = 0; i < g.getVertexNodes().length; i++){
            if(g.getVertexNodes()[i]  != null){
                System.out.print("顶点" + g.getVertexNodes()[i].getData() + " : ");    //输出该顶点信息
                EdgeNode node = g.getVertexNodes()[i].getFirstEdge();
                while(node != null){
                    System.out.print(g.getVertexNodes()[node.getAdjvex()].getData() + "-->"); //输出边集结点信息
                    node = node.getNext();
                }
                System.out.println();
            }
        }
    }

}

4.输出结果

按边的顺序进行输入(v0,v1),(v1,v2),(v2,v3),(v3,v0),(v0,v2)

顶点：v0 : v2-->v3-->v1-->
顶点：v1 : v2-->v0-->
顶点：v2 : v0-->v3-->v1-->
顶点：v3 : v0-->v2-->

突然发现，java的hash表好像就是用的邻接表，你们看是不是很像，顶点使用数组存储，与顶点相连的其他顶点用链表关联