邻接矩阵（以顶点为中心），比较稀疏时，采用邻接表；图的两种遍历

邻接矩阵（以顶点为中心），比较稀疏时，采用邻接表；图的两种遍历2014-12-10 csdn博客 u010026901对于边比较稠密的图，可以采用邻接矩阵（以顶点为中心）的方式表示，而边比较稀疏时，采用邻接表的结构更合适。两种都不能直观表达哪两个点相连或者最短路径是什么。

深度优先遍历类似于树的先根序遍历。与树不同的是，它需要对已经访问过的节点添加标记以免被重复遍历。

public class Depth {/** * 对k号节点深度遍历 * @param a * @param color * @param k 节点 */public static void depthTraversal（int[][] a,int[] color,int k）{System.out.println（k）;color[k]=1;//0未染色，1染色表示遍历过//找到与k连接的for（int i=0;i<a[k].length;i++）{if（a[k][i]==1&&color[i]==0）{depthTraversal（a,color,i）;}}}/** * @param args */public static void main（String[] args） {//邻接矩阵标记是否相连，1表示相连，0表示不连int[][] a={{0,1,1,1,0},{1,0,1,1,1},{1,1,0,1,1},{1,1,0,0,1},{1,1,1,1,0}};//需要一个数组来记录染色信息,int[] color=new int[a.length];//int数组内部默认值为0depthTraversal（a,color,0）;}}

广度优先遍历类似于对树进行逐层遍历。它按照与开始节点的距离由近到远地进行遍历。当然，因为图的特点，也需要对遍历过的节点做标记。

import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Set;public class Breadth {/** * @param args */@SuppressWarnings（"unchecked"）public static void main（String[] args） {//邻接矩阵标记是否相连，稠密的图，我们的写法可以是邻接表int[][] a={{0,1,1,1,0,1},{1,0,1,1,1,0},{1,1,0,0,1,1},{1,1,0,0,1,0},{0,1,1,1,0,0},{1,0,1,0,0,0}};//广度遍历List lst=new ArrayList（）;//等待遍历Set set=new HashSet（）;//保存已遍历的节点lst.add（0）;//先添加个0节点while（true）{if（lst.isEmpty（））break;int node=（Integer）lst.get（0）;System.out.println（node）;set.add（node）;lst.remove（0）;for（int i=0;i<a[node].length;i++）{//相连，未遍历，lst中不含有该节点（可能这个节点的孩子中存在下个节点的孩子）if（a[node][i]==1&&set.contains（i）==false&&lst.indexOf（i）==-1）{lst.add（i）;}}}}}