Java数据结构与算法：图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
程序员文章站
2022-07-13 09:50:37
...
文章目录
图
图是一种数据结构，其中节点可以具有零个或多个相邻元素。两个节点之间的连接称为边。节点也可称为顶点。
表示多对多的关系时，就会用到图。
一、图概念
1、图的名词解释
2、图的表示方法
3、代码实现
创建以下无向图：
public class GraphDemo {
public static void main(String[] args) {
String[] vertexes = {"A","B","C","D","E"};
// 构建图，存入顶点
Graph graph = new Graph(vertexes.length);
for (String vertex : vertexes) {
graph.addVertex(vertex);
}
// 创建边 A-D B-A B-D B-C D-E
graph.addEdge(0,3,1);
graph.addEdge(1,0,1);
graph.addEdge(1,3,1);
graph.addEdge(1,2,1);
graph.addEdge(3,4,1);
// 展现邻接矩阵
graph.showEdges();
// 展现所有顶点
graph.showVertexes();
// 展现有多少个边
System.out.println(graph.getEdgeCount());
}
}
class Graph{
private ArrayList<String> vertexList; // 存储顶点
private int edgeCount; // 记录边的个数
private int[][] edgesTable; // 存储边的矩阵
private int vertexNum; // 存储图顶点总个数
public Graph(int num) {
this.vertexList = new ArrayList<>(num);
this.edgesTable = new int[num][num];
this.edgeCount = 0;
this.vertexNum = num;
}
// 添加顶点
public void addVertex(String vertex){
if (vertexList.size() == vertexNum){
System.out.println("图顶点已满...");
return;
}else {
vertexList.add(vertex);
}
}
// 无向图创建边,v1是顶点对应的索引，v2是顶点对应的索引，weight是边的权重
public void addEdge(int v1, int v2, int weight){
edgesTable[v1][v2] = weight;
edgesTable[v2][v1] = weight;
edgeCount++;
}
// 返回边的数目
public int getEdgeCount(){
return edgeCount;
}
// 通过索引，返回顶点值
public String getVertex(int index){
if (index < vertexList.size()){
return vertexList.get(index);
}else {
throw new IndexOutOfBoundsException("索引超过存储顶点的长度...");
}
}
// 打印所有顶点
public void showVertexes(){
for (String vertex : vertexList) {
System.out.print(vertex+"\t");
}
System.out.println();
}
// 打印邻接矩阵表
public void showEdges(){
for (int[] ints : edgesTable) {
System.out.println(Arrays.toString(ints));
}
}
}
结果：
[0, 1, 0, 1, 0]
[1, 0, 1, 1, 0]
[0, 1, 0, 0, 0]
[1, 1, 0, 0, 1]
[0, 0, 0, 1, 0]
A B C D E
5
二、深度优先搜索 DFS (算法)
. 思路分析
深度优先遍历(Depth First Search)图的方法是，从图中某顶点v出发：
- 访问初始节点v，并标记节点v为已访问
- 查找节点v的第一个邻接节点w
- 若w存在，那执行下一步；如果w不存在，则回到第1步，将从v的下一个节点继续
- 若w未被访问，对w进行深度优先遍历递归（即把w当成新的节点v，继续从第一步开始执行）
- 查找节点v的w邻接节点的下一个邻接节点，转到步骤3
示例：
对应的邻接矩阵：
list集合中存储的顶点依次为 A B C D E
从A开始，A被标记已访问，输出A
A的第一个邻接节点是B(A这一行从头遍历第一个为1的位置，对应的是B，还需要判断是否已被访问，已被访问就找下一个)，B标记已访问，输出B
B的第一个邻接节点是C(B这一行从头遍历第一个为1的位置，对应的是C，还需要判断是否已被访问，已被访问就找下一个)，C标记已访问，输出C
C没有邻接节点，因此找到没有被访问的节点，作为新的节点
即D，D标记已访问，输出D
D的第一个邻接节点是E，E标记已访问，输出E
最终完成了深度优先搜索遍历
.代码实现
public class GraphDemo {
public static void main(String[] args) {
String[] vertexes = {"A","B","C","D","E"};
// 构建图，存入顶点
Graph graph = new Graph(vertexes.length);
for (String vertex : vertexes) {
graph.addVertex(vertex);
}
// 创建边 A-D B-A B-D B-C D-E
graph.addEdge(0,3,1);
graph.addEdge(1,0,1);
graph.addEdge(1,3,1);
graph.addEdge(1,2,1);
graph.addEdge(3,4,1);
// 深度优先遍历
graph.dfs();
}
}
class Graph{
private ArrayList<String> vertexList; // 存储顶点
private int edgeCount; // 记录边的个数
private int[][] edgesTable; // 存储边的矩阵
private int vertexNum; // 存储图顶点总个数
private boolean[] isVisited; // 记录每个顶点是否被访问
public Graph(int num) {
this.vertexList = new ArrayList<>(num);
this.edgesTable = new int[num][num];
this.edgeCount = 0;
this.vertexNum = num;
this.isVisited = new boolean[num];
}
// 添加顶点
public void addVertex(String vertex){
if (vertexList.size() == vertexNum){
System.out.println("图顶点已满...");
return;
}else {
vertexList.add(vertex);
}
}
// 无向图创建边
public void addEdge(int v1, int v2, int weight){
edgesTable[v1][v2] = weight;
edgesTable[v2][v1] = weight;
edgeCount++;
}
// 返回边的数目
public int getEdgeCount(){
return edgeCount;
}
// 通过索引，返回顶点值
public String getVertex(int index){
if (index < vertexList.size()){
return vertexList.get(index);
}else {
throw new IndexOutOfBoundsException("索引超过存储顶点的长度...");
}
}
// 打印邻接矩阵表
public void showEdges(){
for (int[] ints : edgesTable) {
System.out.println(Arrays.toString(ints));
}
}
// 从头遍历获取当前顶点的第一个邻接节点
public int getFirstNeighbor(int index){
for (int i = 0; i < vertexNum; i++) {
if (edgesTable[index][i] > 0){
return i;
}
}
return -1;
}
// 获取当前顶点的下一个邻接节点，
// 由于第一个邻接节点已经被访问过了，所以需要访问下一个邻接节点
public int getNextNeighbor(int index, int nextIndex){
for (int i = nextIndex+1; i < vertexNum; i++) {
if (edgesTable[index][i] > 0){
return i;
}
}
return -1;
}
public void dfs(boolean[] isVisited, int index){
System.out.print(vertexList.get(index)+"->");
isVisited[index] = true;
int w = getFirstNeighbor(index);
while (w != -1){
if (!isVisited[w]){
dfs(isVisited, w);
}
// 如果当前节点的第一个邻接节点已经被访问了，
// 就访问当前节点的下一个邻接节点
w = getNextNeighbor(index, w);
}
}
// 深度优先搜索遍历
public void dfs(){
for (int i = 0; i < vertexNum; i++) {
// 如果没有被访问就dfs
if (!isVisited[i]){
dfs(isVisited, i);
}
}
}
}
结果：
A->B->C->D->E->
三、广度优先搜索 BFS (算法)
广度优先搜索（Broad First Search）
. 思路分析
- 从A节点开始，A标记已访问，索引加入队列输出A；
- 从队列中取出第一个数据，即A的索引，在邻接矩阵中定位到A这一行，开始从头遍历，找到第一个邻接节点B，判断B是否被访问，没有被访问标记被访问，B索引加入队列并输出B
- 继续找A的下一个邻接节点，找到C，判断C是否被访问，没有被访问标记被访问，C索引加入队列并输出C
- 继续找A的下一格邻接节点，遍历该行，发现已没有邻接节点了
- 从队列中取出第一个数据，即B的索引，
- 从B节点开始，判断B节点是否被访问，被访问不输出，在B这一行从头遍历，找到B的每一个邻接节点，然后判断是否被访问，没有被访问就标记访问，该节点的索引加入队列并输出，已被访问就找下一个邻接节点，直到该行完成
- 如果所有节点被访问了就直接退出。
. 代码实现
public class GraphDemo {
public static void main(String[] args) {
String[] vertexes = {"A","B","C","D","E"};
// 构建图，存入顶点
Graph graph = new Graph(vertexes.length);
for (String vertex : vertexes) {
graph.addVertex(vertex);
}
// 创建边 A-B A-C B-C B-D B-E
graph.addEdge(0,1,1);
graph.addEdge(0,2,1);
graph.addEdge(1,2,1);
graph.addEdge(1,3,1);
graph.addEdge(1,4,1);
// 广度优先遍历
graph.bfs();
}
}
class Graph{
private ArrayList<String> vertexList; // 存储顶点
private int edgeCount; // 记录边的个数
private int[][] edgesTable; // 存储边的矩阵
private int vertexNum; // 存储图顶点总个数
private boolean[] isVisited; // 记录每个顶点是否被访问
public Graph(int num) {
this.vertexList = new ArrayList<>(num);
this.edgesTable = new int[num][num];
this.edgeCount = 0;
this.vertexNum = num;
this.isVisited = new boolean[num];
}
// 添加顶点
public void addVertex(String vertex){
if (vertexList.size() == vertexNum){
System.out.println("图顶点已满...");
return;
}else {
vertexList.add(vertex);
}
}
// 无向图创建边
public void addEdge(int v1, int v2, int weight){
edgesTable[v1][v2] = weight;
edgesTable[v2][v1] = weight;
edgeCount++;
}
// 返回边的数目
public int getEdgeCount(){
return edgeCount;
}
// 通过索引，返回顶点值
public String getVertex(int index){
if (index < vertexList.size()){
return vertexList.get(index);
}else {
throw new IndexOutOfBoundsException("索引超过存储顶点的长度...");
}
}
// 打印邻接矩阵表
public void showEdges(){
for (int[] ints : edgesTable) {
System.out.println(Arrays.toString(ints));
}
}
// 从头遍历获取当前顶点的第一个邻接节点
public int getFirstNeighbor(int index){
for (int i = 0; i < vertexNum; i++) {
if (edgesTable[index][i] > 0){
return i;
}
}
return -1;
}
// 获取当前顶点的下一个邻接节点，
// 由于第一个邻接节点已经被访问过了，所以需要访问下一个邻接节点
public int getNextNeighbor(int index, int nextIndex){
for (int i = nextIndex+1; i < vertexNum; i++) {
if (edgesTable[index][i] > 0){
return i;
}
}
return -1;
}
// 对一个顶点的广度优先搜索操作
public void bfs(boolean[] isVisited, int index){
int u; // 用于存储从队列中取出的索引
int w; // 用于存储索引u这一行没有被访问的顶点的索引
LinkedList<Integer> queue = new LinkedList<>(); // 队列
System.out.print(vertexList.get(index)+" -> ");
isVisited[index] = true; // 设置已被访问
queue.addLast(index); // 索引加入到队列中
while(!queue.isEmpty()){
u = queue.removeFirst(); // 从队列中取出第一个索引
w = getFirstNeighbor(u); // 通过u这一行的索引，找到这一行第一个邻接顶点
while (w != -1){
if (!isVisited[w]){
System.out.print(vertexList.get(w)+" -> ");
queue.addLast(w);
isVisited[w] = true;
}
w = getNextNeighbor(u, w); // 继续找u这一行的下一个顶点
}
}
}
// 广度优先搜索遍历
public void bfs(){
for (int i = 0; i < vertexNum; i++) {
if (!isVisited[i]){
bfs(isVisited,i);
}
}
}
}
结果：
A -> B -> C -> D -> E ->
上一篇： nginx-配置负载均衡
下一篇： RocketMq实践
推荐阅读
-
Java数据结构与算法：图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索
-
python实现图的深度优先搜索(DFS)和广度优先搜索(BFS)算法及Dijkstra最短路径应用
-
图的深度优先搜索（DFS）和广度优先搜索（BFS）及其Java实现
-
DFS深度优先搜索算法与BFS广度优先搜索算法的java实现
-
#数据结构与算法学习笔记#PTA18：图（邻接表）+DFS（深度优先搜索）+BFS（广度优先搜索）（C/C++）
-
数据结构与算法-图---介绍了广度优先搜索、深度优先搜索、路径查找等算法的实现
-
数据结构与算法 ---- 图的广度优先搜索（BFS）和深度优先搜索（DFS）
-
python实现图的深度优先搜索(DFS)和广度优先搜索(BFS)算法及Dijkstra最短路径应用
-
【数据结构】Java实现图的深度优先搜索与广度优先搜索