Java实现图的深度优先搜索和广度优先搜索（无向图和有向图）

直接上代码

package mytest;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BFS_DFS{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int m = in.nextInt();
		int n = in.nextInt();
		int[][] nums = new int[n][2];
		for(int i = 0; i < n; i++) {
			nums[i][0] = in.nextInt();
			nums[i][1] = in.nextInt();
		}
		Graph g = new Graph(m, nums, 0);
		Deep d = new Deep();
		System.out.print("深度优先搜索的顺序为：");
		d.DFSTraverse2(g);
		// 注意：不要连续搜索同一个图，因为第一次搜素已经将图顶点的标志位设为已读
//		Board b = new Board();
//		System.out.print("广度优先搜索的顺序为：");
//		b.boradTraverse2(g);
	}
}

class Board{
	int d = 0;  // 有向图的层数
	/*
	 * 无向图广度优先搜索
	 * @param 图
	 */
	public void boradTraverse1(Graph g) {
		Queue<Node> q = new LinkedList<Node>();
		for(int i = 0; i < g.vexnum; i++) {
			if(g.nodeList[i].isVisited() == false) {
				q.add(g.nodeList[i]);
				g.nodeList[i].setVisited(true);
				// 对顶点i的函数操作
				System.out.print(g.nodeList[i].getNum()+" ");
				//d ++;
			}
			while(! q.isEmpty()) {
				int j = q.poll().getNum() - 1;
				for(int k = 0; k < g.vexnum; k++) {
					if(g.graph[j][k] == 1 && g.nodeList[k].isVisited() == false) {
						g.nodeList[k].setVisited(true);
						// 对顶点k的函数操作
						System.out.print(g.nodeList[k].getNum()+" ");
						q.add(g.nodeList[k]);
					}
				}
			}
		}
	}
	
	/*
	 * 有向图广度优先搜索，从顶点入度为0的顶点开始
	 * @param 图
	 */
	public void boradTraverse2(Graph g) {
		Queue<Node> q = new LinkedList<Node>();
		g.setInNode();
		for(int i = 0; i < g.vexnum; i++) {
			if(g.inNode[i] == 0) {
				q.add(g.nodeList[i]);
				g.nodeList[i].setVisited(true);
				// 对顶点i的函数操作
				System.out.print(g.nodeList[i].getNum()+" ");
			}
		}
		d = 0;
		while(! q.isEmpty()) {
			int len = q.size();
			for(int i = 0; i < len; i++) {
				int j = q.poll().getNum() - 1;
				for(int k = 0; k < g.vexnum; k++) {
					if(g.graph[j][k] == 1 && g.nodeList[k].isVisited() == false) {
						q.add(g.nodeList[k]);
						g.nodeList[k].setVisited(true);
						// 对顶点k的函数操作
						System.out.print(g.nodeList[k].getNum()+" ");
						
					}
				}
			}
			d++;
		}
	}
}

class Deep{
	public int count = 0;  // 搜索次数
	/* 从第n个节点开始对图进行深度优先遍历
	 * @param 图
	 * @param 第x个节点
	 */
	private void DFS(Graph g, int x) {
		System.out.print(g.nodeList[x].getNum()+" ");
		g.nodeList[x].setVisited(true);
		
		// 此处添加对顶点x的访问函数
		for(int i = 0; i < g.vexnum; i++) {
			if((g.graph[x][i] == 1) && (g.nodeList[i].isVisited() == false)) {
				DFS(g, i);	
			}
		}
	}
	/*
	 * 无向图
	 * 全局深度优先搜索
	 * @param 图
	 */
	public void DFSTraverse1(Graph g) {
		for(int i = 0; i < g.vexnum; i++) {
			if(g.nodeList[i].isVisited() == false) {
				DFS(g, i);
				count++;
				//System.out.println(count);
			}
		}
	}
	/*
	 * 有向图,从入度为0的顶点开始
	 * 全局深度优先搜索
	 * @param 图
	 */
	public void DFSTraverse2(Graph g) {
		g.setInNode();
		for(int i = 0; i < g.vexnum; i++) {
			if(g.nodeList[i].isVisited() == false && g.inNode[i] == 0) {
				DFS(g, i);
				count++;
				//System.out.println(count);
			}
		}
	}
}

// 图类
class Graph{
	public int[][] graph;  // 邻接矩阵
	public int vexnum;  // 顶点数
	public Node[] nodeList;  // 顶点数组
	public int flag;  // 0-有向图，1-无向图
	public int[] inNode;  // 有向图各顶点入度
	public int[] outNode;  // 有向图各顶点出度
	// 顶点以1，2，3.。。进行编号
	public Graph(int vexnum, int[][] nums, int flag) {
		this.vexnum = vexnum;
		this.flag = flag;
		graph = new int[vexnum][vexnum];
		for(int i = 0; i < nums.length; i++) {
			addEdge(nums[i][0]-1, nums[i][1]-1);
		}
		nodeList = new Node[vexnum];
		for(int i = 0; i < vexnum; i++) {
			nodeList[i] = new Node(i+1, false);
		}
	}
	
	public void addEdge(int x, int y) {
		if(x == y || x > vexnum || y > vexnum)
			return;
		else {  // 无向图
			graph[x][y] = 1;
			graph[y][x] = flag; 
		}
		
	}
	
	/*
	 * 获取有向图入度为0的顶点
	 */
	public void setInNode() {
		inNode = new int[vexnum];
		for(int i = 0; i < vexnum; i++) {
			int j;
			for(j = 0; j < vexnum; j++) {
				if(graph[j][i] == 1)
					inNode[i]++;
			}
		}
	}
	
	/*
	 * 获取有向图出度为0的顶点
	 */
	public void setOutNode() {
		outNode = new int[vexnum];
		for(int i = 0; i < vexnum; i++) {
			int j;
			for(j = 0; j < vexnum; j++) {
				if(graph[i][j] == 1)
					outNode[i]++;
			}
		}
	}
}
// 顶点类
class Node{
	public int num;  // 顶点编号
	public boolean visited;  // 是否访问过,true-已访问
	public Node(int num, boolean visited) {
		this.num = num;
		this.visited = visited;
	}
	public int getNum() {
		return num;
	}
	public void setNum(int num) {
		this.num = num;
	}
	public boolean isVisited() {
		return visited;
	}
	public void setVisited(boolean visited) {
		this.visited = visited;
	}
}

输入测试

第一行：m-图的顶点个数，n-边的条数；
后面n行：每行两个数，x，y，表示x到y有边（有向图的话方向是x->y）。
注意：不要连续搜索同一个图，因为第一次搜索已经将图顶点的标志位设为已读。
输入节点从1开始往后编号。

8 9
1 2
2 4
4 8
8 5
5 2
1 3
3 6
6 7
7 3
深度优先搜索的顺序为：1 2 4 8 5 3 6 7 

欢迎大家批评指正，求交流！！！