数据结构_图以及深度优先遍历(DFS)和广度优先遍历(BFS)
程序员文章站
2022-05-20 19:31:51
...
文章目录
图的常用概念
- 顶点
- 边
- 路径
比如从 D -> C 的路径有:- D->B->C
- D->A->B->C
- 无向图、有向图:顶点之间有无连接方向
- 带权图:边带权值的图
图的表示方式
邻接矩阵
邻接表
图的代码实现
属性和构造器
public class Graph {
private ArrayList<String> vertexList;;
private int[][] edges;
private int numOfEdges;
private boolean[] isVisited;
/**
* 构造器
* @param n
*/
public Graph(int n) {
edges = new int[n][n];
vertexList = new ArrayList<String>(n);
numOfEdges = 0;
isVisited = new boolean[n];
}
}
插入顶点
/**
* 插入节点
* @param vertex
*/
public void insertVertex(String vertex) {
if (vertexList.contains(vertex)) {
System.out.println("节点已存在");
return;
}
vertexList.add(vertex);
}
插入边
/**
* 插入边
* @param v1
* @param v2
* @param weight
*/
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
两点之间权值
/**
* 两点之间权值
* @param v1
* @param v2
* @return
*/
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}
对应索引的节点
/**
* 获取对应索引的节点
* @param i
* @return
*/
public String getValueByIndex(int i) {
return vertexList.get(i);
}
边的总数
/**
* 得到边的总数
* @return
*/
public int getNumOfEdges() {
return numOfEdges;
}
邻接矩阵
/**
* 显示图对应的矩阵
*/
public void showGraph() {
for (int[] arr : edges) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}
节点个数
/**
* 返回节点个数
* @return
*/
public int getNumOfVertex() {
return vertexList.size();
}
DFS与BFS
辅助方法
第一个邻接节点
/**
* 返回第一个邻接节点
* @param index
* @return
*/
public int getFirstNeighbor(int index) {
for (int i = 0; i < vertexList.size(); i++) {
if (edges[index][i] > 1) {
return i;
}
}
return -1;
}
下一个邻接节点
/**
* 返回下一个邻接节点
* @param index
* @param first
* @return
*/
public int getNextNeighbor(int index, int first) {
for (int i = first + 1; i < vertexList.size(); i++) {
if (edges[index][i] > 1) {
return i;
}
}
return -1;
}
深度优先遍历(DFS)
思想
- 从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点, 可以这样理解:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
- 访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。
- 深度优先搜索是一个递归的过程
算法步骤
- 访问初始结点,并标记结点为已访问。
- 查找初始结点的第一个邻接结点。
- 若邻接结点存在,则继续执行4,否则回到第1步,将从初始节点的下一个结点继续。
- 若邻接结点未被访问,对邻接结点进行深度优先遍历递归(即把邻接结点当做另一个初始节点,然后进行步骤123)。
- 查找初始结点的邻接结点的下一个邻接结点,转到步骤3。
代码实现
/**
* 深度优先遍历
*/
public void dfs() {
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
dfs(isVisited, i);
}
}
}
/**
* 一个节点的深度优先遍历
* @param isVisited
* @param index
*/
private void dfs(boolean[] isVisited, int index) {
//1. 访问初始结点,并标记结点为已访问。
System.out.println(getValueByIndex(index));
isVisited[index] = true;
//2. 查找初始结点的第一个邻接结点。
int neighborVertex = getFirstNeighbor(index);
//3. 若邻接结点存在,则继续执行4,
//否则回到第1步,将从初始节点的下一个结点继续。
while (neighborVertex != -1) {
//4.若邻接结点未被访问,对邻接结点进行深度优先遍历递归
if (!isVisited[neighborVertex ]) {
dfs(isVisited, neighborVertex );
}
//5.查找初始结点的邻接结点的下一个邻接结点,转到步骤3。
neighborVertex = getNextNeighbor(index, neighborVertex );
}
//回到第1步,将从初始节点的下一个结点继续。
//return;
}
广度优先遍历(BFS)
思想
类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点
算法步骤
- 访问初始结点并标记结点为已访问。
- 初始结点入队列
- 当队列非空时,继续执行,否则算法结束。
- 出队列,取得队头结点。
- 查找头结点的第一个邻接结点。
- 若头结点的邻接结点不存在,则转到步骤3;否则循环执行以下789:
- 若邻接结点尚未被访问,则访问邻接结点并标记为已访问。
- 邻接结点入队列
- 查找头结点的继邻接结点后的下一个邻接结点,转到步骤6。
代码实现
/**
* 广度优先遍历
*/
public void bfs() {
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
bfs(isVisited, i);
}
}
}
/**
* 一个节点的广度遍历
* @param isVisited
* @param i
*/
private void bfs(boolean[] isVisited, int i) {
int first;
int neighborVertex;
LinkedList<Integer> queue = new LinkedList<Integer>();
//1. 访问初始结点并标记结点为已访问。
System.out.println(getValueByIndex(i));
isVisited[i] = true;
//2. 初始结点入队列
queue.addLast(i);
//3. 当队列非空时,继续执行,否则算法结束。
while (!queue.isEmpty()) {
//4. 出队列,取得队头结点。
first = queue.removeFirst();
//5. 查找头结点的第一个邻接结点。
neighborVertex = getFirstNeighbor(first);
//6. 若头结点的邻接结点不存在,则转到步骤3;否则循环执行以下789:
while (neighborVertex != -1) {
//7. 若邻接结点尚未被访问,则访问邻接结点并标记为已访问。
if (!isVisited[neighborVertex]) {
System.out.println(getValueByIndex(neighborVertex));
isVisited[neighborVertex] = true;
//8. 邻接结点入队列
queue.addLast(neighborVertex);
}
//9. 查找头结点的继邻接结点后的下一个邻接结点,转到步骤6。
neighborVertex = getNextNeighbor(i, neighborVertex);
}
}
}
推荐阅读
-
Java实现二叉树的深度优先遍历和广度优先遍历算法示例
-
python数据结构之图深度优先和广度优先实例详解
-
Java实现二叉树的深度优先遍历和广度优先遍历算法示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
python数据结构之图深度优先和广度优先实例详解
-
可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析
-
数据结构与算法-----BFS与DFS(广度优先搜索与深度优先搜索)
-
数据结构与算法_深度优先搜索(DFS)与广度优先搜索(BFS)详解
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
【数据结构】图的遍历——深度优先搜索DFS、广度优先搜索BFS