图的遍历算法有两种：深度优先遍历、广度优先遍历算法。

        深度优先遍历算法就是从起始结点开始，只要有相邻且未被访问的结点就要直接进行访问，直到最后不能向下遍历为止，再回溯寻找下一个策略。

        广度优先遍历算法，就是从起点开始向下一层一层的进行遍历，直到最后没有结点。

一、图的结点和边的相关类定义

        顶点：

package graph;import java.util.List;/*** 顶点类*/
public class Vertex {String name;List<Edge> edges;boolean flag;//是否被访问过int inDegree;//结点的入度public Vertex() {}public Vertex(String name, List<Edge> edges) {this.name = name;this.edges = edges;}public Vertex(String name) {this.name = name;}public String getName() {return name;}public void setName(String name) {this.name = name;}public List<Edge> getEdges() {return edges;}public void setEdges(List<Edge> edges) {this.edges = edges;}
}

        边：

package graph;/*** 边类*/
public class Edge {Vertex vertex;int weight;public Edge() {}public Edge(Vertex vertex) {this.vertex = vertex;}public Edge(Vertex vertex, int weight) {this.vertex = vertex;this.weight = weight;}public Vertex getVertex() {return vertex;}public void setVertex(Vertex vertex) {this.vertex = vertex;}public int getWeight() {return weight;}public void setWeight(int weight) {this.weight = weight;}
}

  二、深度优先遍历算法

package graph;import java.util.LinkedList;
import java.util.List;public class DFS {public static void main(String[] args) {Vertex v1=new Vertex("v1",new LinkedList<>());Vertex v2=new Vertex("v2",new LinkedList<>());Vertex v3=new Vertex("v3",new LinkedList<>());Vertex v4=new Vertex("v4",new LinkedList<>());Vertex v5=new Vertex("v5",new LinkedList<>());Vertex v6=new Vertex("v6",new LinkedList<>());v1.edges.add(new Edge(v3,9));v1.edges.add(new Edge(v2,7));v1.edges.add(new Edge(v6,14));v2.edges.add(new Edge(v4,15));v3.edges.add(new Edge(v4,11));v3.edges.add(new Edge(v6,2));v4.edges.add(new Edge(v5,6));v6.edges.add(new Edge(v5,9));//        dfs(v1);dfs2(v1);}//递归方式从一个结点开始深度遍历整个图public static void dfs(Vertex v){v.flag=true;System.out.println(v.name);for(Edge edge:v.edges){if(!edge.vertex.flag){dfs(edge.vertex);}}}//非递归方式从一个结点开始深度遍历整个图public static void dfs2(Vertex vertex){LinkedList<Vertex> stack=new LinkedList<>();stack.push(vertex);while (!stack.isEmpty()){Vertex pop = stack.pop();pop.flag=true;System.out.println(pop.name);for (Edge edge : pop.edges) {if(!edge.vertex.flag){stack.push(edge.vertex);}}}}
}

三、广度优先遍历算法

package graph;import java.util.LinkedList;
import java.util.List;public class BFS {public static void main(String[] args) {Vertex v1=new Vertex("v1",new LinkedList<>());Vertex v2=new Vertex("v2",new LinkedList<>());Vertex v3=new Vertex("v3",new LinkedList<>());Vertex v4=new Vertex("v4",new LinkedList<>());Vertex v5=new Vertex("v5",new LinkedList<>());Vertex v6=new Vertex("v6",new LinkedList<>());v1.edges.add(new Edge(v3,9));v1.edges.add(new Edge(v2,7));v1.edges.add(new Edge(v6,14));v2.edges.add(new Edge(v4,15));v3.edges.add(new Edge(v4,11));v3.edges.add(new Edge(v6,2));v4.edges.add(new Edge(v5,6));v6.edges.add(new Edge(v5,9));bfs(v1);}public static void bfs(Vertex vertex){LinkedList<Vertex> queue=new LinkedList<>();queue.offer(vertex);vertex.flag=true;while (!queue.isEmpty()){Vertex poll = queue.poll();System.out.println(poll.name);for (Edge edge : poll.edges) {if(!edge.vertex.flag){edge.vertex.flag=true;queue.offer(edge.vertex);}}}}
}