邻接表

目录

原理解析

遍历图解

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

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

举个栗子

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

    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指向bendIns[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♪(･ω･)ﾉ