使用 JAVA 实现的图的遍历（BFS 和 DFS）介绍

• 下载源代码 - 5.53 KB

什么是图？  

图是计算机科学中最有趣的数据结构之一。图和树在结构上有些相似。事实上，树是从图数据结构派生出来的。然而，树和图之间有两个重要的区别。 

1. 与树不同，在图中，一个节点可以有多个父节点。 
2. 节点之间的链接可能具有值或权重。

图非常适合模拟现实世界的问题，例如表示由道路连接的城市并找到城市之间的路径，模拟空中交通管制系统等。这类问题很难用简单的树结构来表示。下面的例子展示了一个非常简单的图：  

在上图中，A、B、C、D、E、F 称为节点，节点之间的连接线称为边。边可以是箭头表示的有向边；它们也可以是带有数字的加权边。因此，图可以是定向/无向和加权/无权图。本文将讨论无向和无权图。  

程序语言中的图表示 

每个图都有两个组成部分：节点和边。让我们看看这两个组成部分如何在像JAVA这样的编程语言中实现。  

1. 节点  

节点通过类、结构或链表节点来实现。例如，在JAVA中，我们将为上述图表示节点如下： 

//
Class Node
{
   Char data;
   Public Node(char c)
   {
      this.data=c;
   }
}
//  

2. 边  

边表示节点之间的连接。有两种表示边的方法。

邻接矩阵  

这是一个带有布尔标志的二维数组。例如，我们可以使用以下邻接矩阵表示上述图的边。 

在给定的图中，A 连接到 B、C 和 D 节点，因此邻接矩阵将在“A”行的“B”、“C”和“D”列中具有 1。 

使用邻接矩阵表示边的优点是： 

1. 实现简单，因为您只需要一个二维数组 
2. 创建/删除边也很容易，因为您只需要更新布尔值 

使用邻接矩阵的缺点是：  

1. 内存增加，因为您需要声明 N*N 矩阵，其中 N 是节点的总数。
2. 信息冗余，即要表示 A 到 B 和 B 到 A 之间的边，需要在邻接矩阵中设置两个布尔标志。 

在JAVA中，我们可以将邻接矩阵表示为整数/布尔值的二维数组。

邻接表  

它是一个链表节点的数组。换句话说，它就像一个列表，其元素是链表。对于给定的图示例，边将由下面的邻接表表示： 

图遍历  

广度优先搜索 (BFS) 和深度优先搜索 (DFS) 是用于遍历和搜索图中节点的两种算法。它们还可以用于确定一个节点是否可以从给定的节点到达。  

深度优先搜索 (DFS) 

DFS算法的目的是以一种方式遍历图，使其尝试远离根节点。堆用于实现深度优先搜索。让我们看看深度优先搜索如何相对于以下图工作：  

如前所述，在 DFS 中，节点是通过从起始节点遍历树的深度来访问的。如果我们对上述图进行深度优先遍历并打印访问过的节点，它将是“A B E F C D”。DFS 访问根节点，然后访问其子节点，直到到达末端节点，即 E 和 F 节点，然后向上移动到父节点。 

算法步骤  

1. 步骤 1：将根节点压入堆栈。  
2. 步骤 2：循环直到堆栈为空。 
3. 步骤 3：查看堆栈顶部的节点。  
4. 步骤 4：如果节点有未访问的子节点，则获取未访问的子节点，将其标记为已遍历，然后将其压入堆栈。   
5. 步骤 5：如果节点没有任何未访问的子节点，则从堆栈中弹出该节点。

   根据上述步骤，下面的Java代码展示了DFS算法的实现：  

   //
   public void dfs()
   {
   	//DFS uses Stack data structure
   	Stack s=new Stack();
   	s.push(this.rootNode);
   	rootNode.visited=true;
   	printNode(rootNode);
   	while(!s.isEmpty())
   	{
   		Node n=(Node)s.peek();
   		Node child=getUnvisitedChildNode(n);
   		if(child!=null)
   		{
   			child.visited=true;
   			printNode(child);
   			s.push(child);
   		}
   		else
   		{
   			s.pop();
   		}
   	}
   	//Clear visited property of nodes
   	clearNodes();
   }
   
   //   

广度优先搜索 (BFS)  

这是一种非常不同的遍历图节点的方法。BFS算法的目的是尽可能靠近根节点地遍历图。队列用于实现广度优先搜索。让我们看看BFS遍历如何相对于以下图工作

如果我们对上述图进行广度优先遍历并打印访问过的节点作为输出，它将打印以下输出。“A B C D E F”。BFS 按级别遍历节点，因此它将从第 0 级（即根节点）开始，然后移动到下一级别，即 B、C 和 D，然后是最后一级，即 E 和 F。  

算法步骤  

1. 步骤 1：将根节点压入队列。 
2. 步骤 2：循环直到队列为空。 
3. 步骤 3： 从队列中删除节点。 
4. 步骤 4：如果已删除的节点有未访问的子节点，则将其标记为已访问并将未访问的子节点插入队列。 

   根据上述步骤，下面的Java代码展示了BFS算法的实现： 

   //
   public void bfs()
   {
   	//BFS uses Queue data structure
   	Queue q=new LinkedList();
   	q.add(this.rootNode);
   	printNode(this.rootNode);
   	rootNode.visited=true;
   	while(!q.isEmpty())
   	{
   		Node n=(Node)q.remove();
   		Node child=null;
   		while((child=getUnvisitedChildNode(n))!=null)
   		{
   			child.visited=true;
   			printNode(child);
   			q.add(child);
   		}
   	}
   	//Clear visited property of nodes
   	clearNodes();
   }
   // 

完整的实现包含在附加的源代码中。

关于代码

本文的源代码是一个 JAVA 项目，您可以在 Eclipse IDE 中导入或从命令提示符运行。您需要运行Main.java文件才能看到遍历输出。

Main.java是一个Java控制台应用程序，它创建一个简单的无向图，然后调用图的DFS和BFS遍历。

历史 

• 2008年12月29日：初始版本