我们想要知道出度方向的顶点，可以使用邻接表，我们要了解入度就需要使用逆邻接表。但是我们既想要了解入度有想要了解出度，那么我们该如何处理？

这时就需要使用到有向图的一种存储方法：十字链表

顶点表结点结构

firstin表示入边表头指针，指向该顶点的入边表中第一个结点。
firstout表示出边表头指针，指向该顶点的出边表中第一个结点。

边表结点结构

tailvex是指弧起点在顶点表的下标
headvex是指弧终点在顶点表的下标。
headlink是指入边表指针域，指向终点相同的下一条边
taillink是指边表指针域，指向起点相同的下一条边。
如果是网，我们还要在其中加入权值域，来存储权值

我们可以看做横向是出度，竖向是入度
顶点的出度和入度。除了结构复杂一点外，其实创建图算法的时间复杂度和邻接表是相同的，因此很好的应用在有向图中。
注意：整张图的出度和入度是一致的（不是某个顶点，而是这张图）

代码实现：

//十字链表
public class OrthogonalList {
    private int MAXVEX;
    private VertexNode[] verArr;
    // 顶点数组赋值
    public OrthogonalList(String[] arr) {
        this.MAXVEX = arr.length;
        this.verArr = new VertexNode[this.MAXVEX];
        for (int i = 0; i < arr.length; i++) {
            this.verArr[i] = new VertexNode(arr[i]);
        }
    }
    //获取顶点在顶点数组中的位置
    private int getPosition(String str) {
        int pos = 0;
        for(int i=0;i<this.MAXVEX;i++){
            if(this.verArr[i].getData().equals(str)){
                pos=i;
                break;
            }
        }
        return pos;
    }
    /**
     *     输入的是边数组
     * @param strArr
     */
    public void addAdj(String[][] strArr) {
        for (int i = 0; i < strArr.length; i++) {
            //弧的起点在顶点数组中的下标
            int tailvex = getPosition(strArr[i][0]);
            //弧终点在顶点数组中的下标
            int headvex = getPosition(strArr[i][1]);
            //初始化边表邻接点
            EdgeNode adj = new EdgeNode();
            //设置位置开始位置
            adj.setTailvex(tailvex);
            //设置结束位置
            adj.setHeadvex(headvex);
            //获取开始节点的出边表邻接点
            EdgeNode firstout  = this.verArr[tailvex].getFristout();
            //获取结束节点的入边表邻接点
            EdgeNode firstin = this.verArr[headvex].getFristin();
            //直接使用头插法
            this.verArr[tailvex].setFristout(adj);
            if (firstout != null) {
                adj.setTaillink(firstout);
            }
            /**
             *     尾插法
            //处理开始节点的出边表（邻接矩阵）
            if (firstout == null) {
                this.verArr[tailvex].setFristout(adj);
            } else {
                //这里是找到最后的出边表，其实可以放在第一个即可
                while (true) {
                    if (firstout.getTaillink() != null) {
                        firstout = firstout.getTaillink();
                    } else {
                        firstout.setTaillink(adj);
                        break;
                    }
                }
            }
            **/
            //直接使用头插法
            this.verArr[headvex].setFristin(adj);
            if (firstin != null) {
                adj.setHeadlink(firstin);
            } 
            /**
             *     尾插法
            //处理结束节点的入边表（逆邻接矩阵）
            if (firstin == null) {
                this.verArr[headvex].setFristin(adj);
            } else {
                //这里也可以在
                while (true) {
                    if (firstin.getHeadlink() != null) {
                        firstin = firstin.getHeadlink();
                    } else {
                        firstin.setHeadlink(adj);
                        break;
                    }
                }
            }
            **/
        }
    }
    /**
     *     获取入度
     * @param str
     * @return
     */
    public int getIndegree(String str) {
        int i = 0;
        int pos=getPosition(str);
        EdgeNode temp = this.verArr[pos].getFristin();
        if (temp == null)
            return i;
        while (true) {
            if (temp != null) {
                i++;
                temp = temp.getHeadlink();
            } else {
                break;
            }
        }
        return i;
    }
    /**
     *     获取出度
     * @param str
     * @return
     */
    public int getOutdegree(String str) {
        int i = 0;
        int pos=getPosition(str);
        EdgeNode temp = this.verArr[pos].getFristout();
        if (temp == null)
            return i;
        while (true) {
            if (temp != null) {
                i++;
                temp = temp.getTaillink();
            } else {
                break;
            }
        }
        return i;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String[] str={"v0","v1","v2","v3"};
        OrthogonalList adj=new OrthogonalList(str);
        String[][] edges=new String[][]{
                {"v0","v3"},
                {"v1","v0"},
                {"v1","v2"},
                {"v2","v0"},
                {"v2","v1"}
        };
        adj.addAdj(edges);
        //出度
        System.out.println(adj.getOutdegree("v1"));
        //入度
        System.out.println(adj.getIndegree("v0"));
    }
}
// 顶点表节点
class VertexNode {
    private String data = null;
    private EdgeNode fristin = null;// 入边表（顶点为弧尾）
    private EdgeNode fristout = null;// 出边表（顶点为弧头）
    public VertexNode(String data) {
        super();
        this.data = data;
    }
    public String getData() {
        return data;
    }
    public void setData(String data) {
        this.data = data;
    }
    public EdgeNode getFristin() {
        return fristin;
    }
    public void setFristin(EdgeNode fristin) {
        this.fristin = fristin;
    }
    public EdgeNode getFristout() {
        return fristout;
    }
    public void setFristout(EdgeNode fristout) {
        this.fristout = fristout;
    }
}
//边表节点
class EdgeNode {
    private int tailvex = -1;// 弧的起点在顶点数组中的下标
    private int headvex = -1;// 弧终点在顶点数组中的下标
    private EdgeNode headlink = null;// 指向下一个终点相同的邻接点
    private EdgeNode taillink = null;// 指向下一个起点相同的邻接点
    public int getTailvex() {
        return tailvex;
    }
    public void setTailvex(int tailvex) {
        this.tailvex = tailvex;
    }
    public int getHeadvex() {
        return headvex;
    }
    public void setHeadvex(int headvex) {
        this.headvex = headvex;
    }
    public EdgeNode getHeadlink() {
        return headlink;
    }
    public void setHeadlink(EdgeNode headlink) {
        this.headlink = headlink;
    }
    public EdgeNode getTaillink() {
        return taillink;
    }
    public void setTaillink(EdgeNode taillink) {
        this.taillink = taillink;
    }
}

运行结果如下：

2
2