1.遍历
图的遍历，所谓遍历，就是对结点的访问，一个图有那么多的结点，如何遍历这些结点，需要特定的策略，一般有两种访问策略：
深度优先搜索和广度优先搜索
2.深度优先搜索DFS
深度优先搜索，从图的任一顶点V1开始，输出顶点V1，将V1作为当前顶点，寻找当前顶点的邻接点V2，并进行如下判断：如果目前尚未输出顶点V2，则输出V2，V2成为新的当前顶点，继续这个过程；如果V2已经输出，则检查V1的另一个邻接点；如果V1的所有邻接点均已输出，则退回到V1之前的顶点深度优先搜索过程是一个递归过程，程序实现时使用栈记录遍历路径，当遍历一个顶点时，顶点入栈；当某个顶点的所有邻接点均已访问过，则退栈，栈顶顶点又作为当前顶点，继续遍历过程。当栈空时，检查是否已遍历图中所有顶点，若是，说明图为连通图，否则，图是不连通的
具体算法表述如下：
访问初始结点v，并标记结点v为已访问。
查找结点v的第一个邻接结点w。
若w存在，则继续执行4，否则算法结束。
若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
查找结点v的w邻接结点的下一个邻接结点，转到步骤3。
例如下图，其深度优先遍历顺序为 1->2->4->8->5->3->6->7
3.广度优先搜索BFS
广度优先搜索是一个迭代的过程，类似于二叉树层序遍历过程，从图中的任一顶点V1开始，将顶点V1入队列，当队列不空时，循环执行：出队列，并输出该顶点，标记该顶点为已输出，将该顶点所有尚未输出的邻接点入队列
具体算法表述如下：
访问初始结点v并标记结点v为已访问。
结点v入队列
当队列非空时，继续执行，否则算法结束。
出队列，取得队头结点u。
查找结点u的第一个邻接结点w。
若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
1). 若结点w尚未被访问，则访问结点w并标记为已访问。 2). 结点w入队列 3). 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。如上图，其广度优先算法的遍历顺序为：1->2->3->4->5->6->7->8
4.程序package graph; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class Graph { private ArrayList vertexList; //存储点的链表 private int[][] edges; //邻接矩阵，用来存储边 private Stack<Integer> stack; private Queue<Integer> queue; public Graph(int n){ this.vertexList=new ArrayList(n); this.edges=new int[n][n]; this.stack=new Stack<Integer>(); this.queue=new LinkedList<Integer>(); } //插入结点 public void insertVertex(Object vertex){ vertexList.add(vertexList.size(), vertex); } //插入边 public void insertEdge(int v1,int v2,int weight){ edges[v1][v2]=weight; } //深度优先搜索 public void DFS(boolean[] isVisited){ int i=this.stack.peek(); boolean mark=false; for(int j=0;j<vertexList.size();j++){ if(edges[i][j]>0&&!isVisited[j]){ System.out.print(vertexList.get(j)+"-"); isVisited[j]=true; this.stack.push(j); mark=true; DFS(isVisited); } } if(!mark) this.stack.pop(); if(this.stack.isEmpty()) return; } public void initDFS(boolean[] isVisited){ System.out.print(vertexList.get(0)+"-"); isVisited[0]=true; this.stack.push(0); DFS(isVisited); } //广度优先搜索 public void BFS(boolean[] isVisited){ if(this.queue.isEmpty()) return; int i=this.queue.poll(); System.out.print(vertexList.get(i)+"-"); for(int j=0;j<this.vertexList.size();j++){ if(this.edges[i][j]>0&&!isVisited[j]){ isVisited[j]=true; this.queue.add(j); } } BFS(isVisited); } public void initBFS(boolean[] isVisited){ this.queue.add(0); isVisited[0]=true; } public static void main(String[] args){ int n=8; String labels[]={"1A","2B","3C","4D","5E","6F","7G","8H"}; Graph graph=new Graph(n); for(String label:labels) graph.insertVertex(label); //插入九条边 graph.insertEdge(0, 1, 1); graph.insertEdge(0, 2, 1); graph.insertEdge(1, 3, 1); graph.insertEdge(1, 4, 1); graph.insertEdge(3, 7, 1); graph.insertEdge(4, 7, 1); graph.insertEdge(2, 5, 1); graph.insertEdge(2, 6, 1); graph.insertEdge(5, 6, 1); graph.insertEdge(1, 0, 1); graph.insertEdge(2, 0, 1); graph.insertEdge(3, 1, 1); graph.insertEdge(4, 1, 1); graph.insertEdge(7, 3, 1); graph.insertEdge(7, 4, 1); graph.insertEdge(6, 2, 1); graph.insertEdge(5, 2, 1); graph.insertEdge(6, 5, 1); System.out.println("深度优先搜索序列为："); boolean[] isVisited=new boolean[8]; graph.initDFS(isVisited); graph.DFS(isVisited); System.out.println(); System.out.println("广度优先搜索序列为："); isVisited=new boolean[8]; graph.initBFS(isVisited); graph.BFS(isVisited); } }
