ListUDF

前文我们通过邻接矩阵创建了无向图，本文通过Java实现邻接表创建无向图。

一. 邻接表无向图的介绍

邻接表无向图是一种数据结构，与之前邻接矩阵无向图不同的是，它使用链表来存储顶点的关系,也就是用链表存储边。如下面所示

Tips: 之前用矩阵存储会造成空间上的额外开销，用链表就可以很好地改善，但代价是要花费更多的时间依次遍历链表每个节点。在实际工程中优化的话，可以考虑将链表换成哈希表、跳表或者是红黑树

二. 邻接矩阵无向图的代码说明

1. 基本定义

public class ListDG {

    // 存储所有的顶点
    private VNode[] vNodes;

    // 边节点
    private class ENode{
        // 边的索引
        int index;
        // 边的下一条边
        ENode next;
    }

    // 顶点
    private class VNode{
        // 顶点存储的值
        char data;
        // 顶底相连的第一条边
        ENode firstEdge;
    }
}

• vNodes 用于存储顶点值
• ENode是边的数据结构，其实一个链表的表示形式
• VNode实顶点的数据结构

2. 创建图

创建图有两种方法，一种是已知数据创建图，一种是用户输入创建图。这里用的是前者

public ListUDG(char[] vertexs, char[][] edges){

        int v1 = vertexs.length;
        vNodes = new VNode[v1];

        // 创建顶点
        for (int i = 0; i < vertexs.length; i++) {
            VNode vNode = new VNode();
            vNode.data = vertexs[i];
            vNode.firstEdge = null;
            vNodes[i] = vNode;
        }

        // 创建边
        for (int i = 0; i < edges.length; i++) {

            // 获取两条边对应的下标
            int p1 = getPos(edges[i][0]);
            int p2 = getPos(edges[i][1]);

            ENode node1 = new ENode();
            node1.index = p2;
            if(vNodes[p1].firstEdge == null)
                vNodes[p1].firstEdge = node1;
            else
                linkLast(vNodes[p1].firstEdge, node1);

            // 创建无向图
            ENode node2 = new ENode();
            node2.index = p1;
            if(vNodes[p2].firstEdge == null)
                vNodes[p2].firstEdge = node2;
            else
                linkLast(vNodes[p2].firstEdge, node2);
        }


    }

方便大家学习，提供了源代码