java.有向图邻接表深度优先遍历手写心得

基本思路就是：构造一个列表这个列表的每个元素是一个列表，

private List<List<Integer>> arrList;

然后就是为arrList添加列表，和顶点数相同，一定要注意的是不能光写一个for循环，

for (int i=1;i<=total;i++){ arrList.add(new ArrayList<>()); }

要这样写！如下图，在这个构造方法中for循环之前一定要多一步arrList.add(new ArrayList<>());

因为你循环为每个节点加列表的时候，arrList.add默认会从尾部加，也就是说我想跳过arrList[0]，只加到索引1~5，是不可能的，系统会默认从索引0开始加所以，只用for循环加列表，实际上是从arrList的索引为0开始加，加到索引为4，最后一个索引5不会拥有一个列表，因此程序会报错。

public youGraphDfs2(int total){ this.total=total; this.arrList=new ArrayList<>(total+1); //total +1 arrList.add(new ArrayList<>()); for (int i=1;i<=total;i++){ arrList.add(new ArrayList<>()); } }

接着就是添加边，邻接表法构造有向图，就是arrList中的每个元素代表一个顶点，顶点又是一个列表，每个顶点的列表存储顶点的邻居顶点，又因为是有向图不需要双向添加，只需要添加一次即可，然后再进行深度优先遍历。

public void addEdge(int i,int j){ arrList.get(i).add(j); //添加用list操作方法，get和add }

深度优先遍历，有两个方法，两个方法的本质是一样的都是递归遍历，其二是封装调用函数。其一：

public void dfs(int start,boolean[] visit){ visit[start]=true; System.out.print("V"+start+" "); //邻接表深度优先是队列形式 for(int neighbor:arrList.get(start)){ if(!visit[neighbor]){ dfs(neighbor,visit); } }

其二：

public void dfs(int start){ boolean[] visit=new boolean[total+1]; dfsUtil(start,visit); } public void dfsUtil(int i,boolean[] visit){ visit[i]=true; System.out.print("V"+i+" "); //！！遍历它所有的邻居节点,就是不断的先遍历第一个列表找到每一个的邻居 for(int neighbor:arrList.get(i)){ if(!visit[neighbor]){ dfsUtil(neighbor,visit); } }

完整代码展示：

package 算法; import java.util.ArrayList; import java.util.List; public class youGraphDfs2 { //链表法写 private int total; private List<List<Integer>> arrList; public youGraphDfs2(int total){ this.total=total; this.arrList=new ArrayList<>(total+1); //total +1 arrList.add(new ArrayList<>()); for (int i=1;i<=total;i++){ arrList.add(new ArrayList<>()); } } public void addEdge(int i,int j){ arrList.get(i).add(j); //添加用list操作方法，get和add } public void dfs(int start,boolean[] visit){ visit[start]=true; System.out.print("V"+start+" "); //邻接表深度优先是队列形式 for(int neighbor:arrList.get(start)){ if(!visit[neighbor]){ dfs(neighbor,visit); } } // public void dfs(int start){ // boolean[] visit=new boolean[total+1]; // dfsUtil(start,visit); // } // public void dfsUtil(int i,boolean[] visit){ // visit[i]=true; // System.out.print("V"+i+" "); // //！！遍历它所有的邻居节点,就是不断的先遍历第一个列表找到每一个的邻居 //// for(int j=1;j<=total;j++){ //// if(arrList.get(i).get()) //// } // //for // for(int neighbor:arrList.get(i)){ // if(!visit[neighbor]){ // dfsUtil(neighbor,visit); // } // } // } public static void main(String[] args) { youGraphDfs2 y=new youGraphDfs2(5); y.addEdge(1, 2); y.addEdge(1, 4); y.addEdge(4, 3); y.addEdge(3, 2); y.addEdge(3, 5); y.addEdge(2, 5); boolean[] visit=new boolean[y.total+1]; y.dfs(1,visit); } }