Java图搜索算法之图的对象化描述示例详解

什么是图？

图是一种非线性数据结构，由节点和边组成，节点表示图中对象，边表示节点间相互关系。图分为有向图和无向图，有向边和无向边。

图的对象化描述

Java中可以使用对象化的方式来描述一个图，主要有两个类：

Vertex（节点类）

节点类表示图中的节点，主要有两个属性：

• label：节点标签，用于区分不同节点。
• wasVisited：该节点是否被访问过的标记。

节点类包含以下方法：

• 构造函数：Vertex(String label)
• addNeighbor(Vertex v)：添加节点v为该节点的邻居。
• toString()：返回节点的标签。

Graph（图类）

图类由Vertex类型的数组和邻接矩阵组成，主要有以下属性：

• MAX_VERTS：最大节点数。
• verts：节点数组。
• adjMat：邻接矩阵。

图类包含以下方法：

• 构造函数：Graph()
• addVertex(String label)：添加一个新节点。
• addEdge(int start, int end)：添加一个有向边（start -> end）。
• displayVertex(int v)：展示节点v的信息。
• dfs()：深度优先搜索算法。
• bfs()：广度优先搜索算法。

图的搜索算法

深度优先搜索算法

深度优先搜索算法（DFS）是一种用于遍历或搜索树或图的算法。从初始访问节点出发，递归地访问所在节点的各个未被访问的邻居节点，直到所有节点都被访问为止。

示例1：

Graph g = new Graph();
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(0, 3);
g.addEdge(3, 4);
g.dfs();

上述代码创建了一个图，包含5个节点和4条边，首先访问节点0（A），然后递归地访问与节点0相邻的未被访问过的节点1（B），再递归地访问与节点1相邻的未被访问过的节点2（C），节点1的所有邻居都被访问过了，回到节点0，递归地访问与节点0相邻的未被访问过的节点3（D），再递归地访问与节点3相邻的未被访问过的节点4（E），节点3的所有邻居都被访问过了，回到节点0，所有节点都被访问过了，结束搜索。

广度优先搜索算法

广度优先搜索算法（BFS）是一种用于遍历或搜索树或图的算法。从初始访问节点出发，依次访问该节点的邻居节点，再依次访问邻居的邻居节点，直到所有节点都被访问为止。

示例2：

Graph g = new Graph();
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(0, 3);
g.addEdge(3, 4);
g.bfs();

上述代码创建了一个图，包含5个节点和4条边，首先访问节点0（A），依次访问节点0相邻的节点1（B）和节点3（D），然后依次访问节点1的邻居节点2（C）和节点3的邻居节点4（E），所有节点都被访问过了，结束搜索。

以上就是Java图搜索算法之图的对象化描述示例的详解及两个示例说明。