神马是图
简单来说，图就是由一些小圆点（称为顶点）和连接这些小圆点的直线（称为边）组成。
对于一个图，我们最常见的需要就是遍历一个图，通过这些边到达每一个顶点。通常我们有两种方式去遍历所有的顶点，一种是深度优先遍历，另一种是广度优先遍历。（对于深度与广度可以参考之前的文章）。
图的表示方法
在计算机语言中我们通常可以通过一个二维数组表示一个图。如同下图：
图中的1表示有边可以联通两个顶点，∞表示没有边联通，0表是自己到自己。这种存储图的方式称为图的邻接矩阵存储法。
图的深度优先遍历
public static Scanner scanner; public static int chart[][]=new int[5][5]; public static boolean book[][]=new boolean[5][5]; public static int sum=0; public static void dfs(int step){ sum++; if(sum==chart.length){ return; } //当遍历完成后结束遍历 System.out.print(step+"\t"); for(int i=0;i<chart.length;i++ ){ if(chart[step][i]==1&&book[step][i]==false){ book[step][i]=true; dfs(i); } } } //初始化数据 @Before public void init(){ scanner=new Scanner(System.in); for(int i=0;i<chart.length;i++){ for(int j=0;j<chart[i].length;j++){ if(i==j){ chart[i][j]=0; } else{ chart[i][j]=Integer.MAX_VALUE; } } } for(int i=0;i<5;i++){ int x=scanner.nextInt(); int y=scanner.nextInt(); chart[x][y]=1; } } @Test public void testDfs(){ dfs(0); }图的广度优先遍历
public static Scanner scanner; public static int chart[][]=new int[5][5]; public static boolean book[][]=new boolean[5][5]; public static int sum=0; public void bfs(){ Queue<Integer> queue=new LinkedList<Integer>(); queue.offer(0); while(!queue.isEmpty()){ int head=queue.poll(); sum++; System.out.println(head); if(sum==chart.length){ return; } for(int i=0;i<chart.length;i++){ if(chart[head][i]==1&&book[head][i]==false){ book[head][i]=true; queue.offer(i); } } } } @Before public void init(){ scanner=new Scanner(System.in); for(int i=0;i<chart.length;i++){ for(int j=0;j<chart[i].length;j++){ if(i==j){ chart[i][j]=0; } else{ chart[i][j]=Integer.MAX_VALUE; } } } for(int i=0;i<5;i++){ int x=scanner.nextInt(); int y=scanner.nextInt(); chart[x][y]=1; } } @Test public void testDfs(){ bfs(); }
