ListDG

本文我们用Java实现邻接表有向图的创建。

一. 邻接表有向图介绍

邻接表底层使用了一个数组+链表来存储图，数组用于存储图的顶点，链表存储两个顶点之间的关系。如下图所示

二.代码说明

1. 基本定义

这里定义还是和之前一样

public class ListDG {

    private VNode[] vNodes;

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

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

2. 算法实现

这边只需要把创建边的方法稍作改动就可以了。

public ListDG(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);

    }


}

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