【Java】数组实现模拟实现邻接表**原理解析**图解超详细

邻接表

目录

原理解析

遍历图解

---

是图论中一种表示图的方法，它用一个表来表示图中的所有顶点以及与它们相邻的顶点。邻接表通常用于表示稀疏图，其中每个顶点只与一小部分顶点相邻。它的基本思想是用一个数组来存储图中的所有顶点，每个顶点对应的数组元素是一个链表，链表中存储的是与该顶点相邻的顶点。

 

好啰嗦建议直接看图捏,不是上面的呀,是下面的!!!

举个栗子

对于上面单向无环图,我们采用数组模拟

    static  final int N =10001;
    //定义头结点
    static int []head=new int[N];
    //定义指向的数组
    static int [] elem=new int[N];
    //定义当前边的终点
    static int [] endIns=new int[N];

    static int id;

    //加入新的指向边
    static void add(int a,int b){
        elem[id] =b;//当前a指向b
        endIns[id]=head[a];//把a的下一条边的起点存入
        head[a]=id++;//id是索引下标自增
        /*
        每次head数组都会存入id下标
        且是起点的下标做改变
         */
    }

    public static void main(String[] args) {
        add(1,2);
        add(1,3);
        add(1,4);
        add(2,5);
        add(2,6);
    }

原理解析

当我们传入参数1,2的时候

 

当我们传入参数1,3的时候 

 

当我们传入参数1.4

 

此时我们就建立了一个这样的有向无环图

 

这个时候我们依旧开始第一次遍历邻接表

    static void sower(int index){

        int ids = head[index];
        while (endIns[ids]!=-1){//终边下标为-1表示走到头了
            System.out.println(index+"->"+elem[ids]);
            ids=endIns[ids];//指向终边下标

        }
        //最后一个由于下标等于-1不会进入循环也就不会打印
        System.out.println(index+"->"+elem[ids]);
    }

当我们传入参数2,5的时候 

 

 当我们传入参数2,6的时候 

 最终的形态!!!

 

遍历图解

        sower(1);
        sower(2);

1->4
1->3
1->2
2->6
2->5

 

 

哈，谢谢各位同志的阅读，然后呢如果觉得本文对您有所帮助的话，还给个免费的赞捏

Thanks♪(･ω･)ﾉ