数据结构-图,图的深度优先遍历和广度优先遍历(Java实现)
程序员文章站
2022-05-22 20:01:40
...
线性表和树都能处理单对多的关系,想要处理多对多的关系时我们可以使用图
图的使用最常见在地图
package datastructure.graph;
/*
@CreateTime 2021/9/20 22:02
@CreateBy cfk
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
public class Graph {
public static void main(String[] args) {
/*
数据量少时发现两种遍历完全一样
Graph graph = new Graph(5);
String[] vertex = {"A","B","C","D","E"};
for (String node : vertex) {
graph.addVertex(node);
}
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 graph = new Graph(8);
String[] vertex = {"1","2","3","4","5","6","7","8"};
for (String node : vertex) {
graph.addVertex(node);
}
//更新边的关系
graph.addEdge(0, 1, 1);
graph.addEdge(0, 2, 1);
graph.addEdge(1, 3, 1);
graph.addEdge(1, 4, 1);
graph.addEdge(3, 7, 1);
graph.addEdge(4, 7, 1);
graph.addEdge(2, 5, 1);
graph.addEdge(2, 6, 1);
graph.addEdge(5, 6, 1);
//显示矩阵
graph.showEdges();
//测试深度遍历 是否成功
System.out.println("深度优先遍历");
graph.dfs();
System.out.println();
//测试广度遍历
System.out.println("广度优先遍历");
graph.bfs();
}
private ArrayList<String> vertexList; //存储顶点元素
private int[][] edges; //存储图对应的邻接矩阵
private int numOfEdges; //存储图的边数
private boolean[] isVisited; //记录节点是否被访问
public Graph(int n) {
vertexList = new ArrayList<String>(); //创建一个集合来存储顶点
edges = new int[n][n]; //初始化一个二维数组 长宽都为元素个数
numOfEdges = 0; //默认边数为0
isVisited = new boolean[n];
}
/* =====================bfs(广度优先遍历算法)====================================
1)访问初始结点v并标记结点v为已访问。
2)结点v入队列
3)当队列非空时,继续执行,否则算法结束。
4)出队列,取得队头结点u。
5)查找结点u的第一个邻接结点w。
6)若结点u的邻接结点w不存在,则转到步骤3;
否则循环执行以下三个步骤:
6.1若结点w尚未被访问,则访问结点w并标记为已访问。
6.2结点w入队列
6.3查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。
*/
public void bfs() {
for (int i = 0; i < getVertex(); i++) {
bfs(isVisited,i);
}
}
public void bfs(boolean[] isVisited, int v) {
//队列的头节点
int u;
//邻接结点
int w;
//创建一个队列记录 位置
LinkedList<Integer> queue = new LinkedList<>();
System.out.print(getValueByIndex(v)+"=>");
//记录表示已经被访问
isVisited[v] = true;
//结点v入列
queue.addLast(v);
while (!queue.isEmpty()){
//获取队列的头结点
u = queue.removeFirst();
//查询邻接结点
w = getFirstNeighbor(u);
while (w != -1){
if (!isVisited[w]){
System.out.print(getValueByIndex(w) + "=>");
isVisited[w] = true; //标记为已访问
queue.addLast(w);
}
w = getNextNeighbor(w,u);
}
}
}
//============================================================================
/* =====================dfs(深度优先遍历算法)====================================
*/
//由于下面的算法仅仅只对了一个元素进行操作 所以这里重载一个方法依次对所有的元素进行遍历
public void dfs(){
for (int i = 0; i < getVertex(); i++) {
if (!isVisited[i]){
dfs(isVisited,i);
}
}
}
//深度优先遍历算法
/*
深度优先遍历算法步骤
1)访问初始结点v,并标记结点v为已访问。
2)查找结点v的第一个邻接结点w。
3)若w存在,则继续执行4,如果w不存在,则回到第1步,将从v的下一个结点继续。
4)若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。
5)查找结点v的w邻接结点的下一个邻接结点,转到步骤3。
*/
public void dfs(boolean[] isVisited, int v){
//首先访问初始结点
System.out.print(getValueByIndex(v)+"=>");
//标记结点被访问
isVisited[v] = true;
//查找结点v的第一个邻接结点w
int w = getFirstNeighbor(v);
while (w != -1) {
if (!isVisited[w]){
dfs(isVisited,w);
}
//从当前结点下一行开始循环,因为前面就算能找到也没用
/*
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0] 比如第一次找到(0,1)后去到(1,1)继续查找
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
*/
w = getNextNeighbor(w, v);
}
}
//找到某一个初始结点的第一个邻接结点并且返回
public int getFirstNeighbor(int index) {
for (int i = 0; i < vertexList.size(); i++) {
//因为当此点为1时说明为邻接结点 所以大于0说明已经找到了
if (edges[index][i] > 0){
return i;
}
}
//如果没有找到返回-1
return -1;
}
//根据前一个结点获取下一个邻接结点
public int getNextNeighbor(int v1, int v2) {
for (int i = v1 + 1; i < vertexList.size(); i++) {
if (edges[v2][i] > 0){
return i;
}
}
return -1;
}
//=========================================================
//通过数组下标获取数组
public String getValueByIndex(int i){
return vertexList.get(i);
}
//展示矩阵
public void showEdges(){
for (int[] edge : edges) {
System.out.println(Arrays.toString(edge));//打印二维数组
}
}
//返回m和n的状态 1代表相连 0代表不相连
public int getStatue(int m, int n) {
return edges[m][n];
}
//添加顶点
public void addVertex(String node) {
vertexList.add(node);
}
//获取数组顶点个数
public int getVertex(){
return vertexList.size();
}
//获取数组的边数
public int getEdges(){
return numOfEdges;
}
//添加边元素
public void addEdge(int m, int n, int status){
edges[m][n] = status;
edges[n][m] = status;
numOfEdges++;
}
}