图的深度优先遍历与广度优先遍历
程序员文章站
2022-05-21 23:22:07
...
思路
深度优先
1:访问初始顶点v,并设置为已访问
2:获取节点v的邻接节点 w
3:如果 w存在,则向下继续执行,否则结束算法
4:如果节点w没有访问过,对w进行DFS
5:获取节点v的下一个邻接节点,回到 步骤3
private void DFS(boolean[] isVisited, int v){
int w;//用来存储顶点v的邻接节点
//访问初始顶点,并设置为已访问
System.out.print(getVertexByIndex(v)+"->");
isVisited[v] = true;
//获取第一个邻接顶点
w = getFirstNeighbor(v);
while(w != -1){ //检测顶点v的所有邻接顶点
if(!isVisited[w]){ //如果 w 未访问过
DFS(isVisited,w); //进行深度遍历
}
// 顶点 w 遍历过
w = getNextNeighbor(v,w);//对下一个邻接节点进行访问
}
}
/**
* 对整个图进行深度遍历
*/
public void DFS(){
isVisited = new boolean[getNumOfVertexes()];
for (int i = 0; i < getNumOfVertexes(); i++) {
if(!isVisited[i]){
DFS(isVisited,i);
}
}
System.out.println();
}
广度优先
需要一个队列用来保持访问的顺序
1:访问初始节点v,并将v设置为已访问
2:将v加入队列
3:如果队列不为空,向下执行,否则结束算法
4:获取队头元素u
5:获取u邻接节点w
6:如果w为空,则返回步骤3,如果不为空则进行以下操作
6.1:访问w,并将w设置为已访问
6.2:将v入队
6.3:获取v的下一个邻接节点,返回 步骤6
private void BFS(boolean[] isVisited,int v){
int u;//存放出队节点
int w;//存放u的邻接节点
LinkedList<Integer> queue = new LinkedList<>();
System.out.print(getVertexByIndex(v)+"=>\t");
isVisited[v] = true;
queue.addLast(v);
while(!queue.isEmpty()){
u = queue.removeFirst();
w = getFirstNeighbor(u);
while (w != -1){
if(!isVisited[w]){
System.out.print(getVertexByIndex(w)+"=>\t");
isVisited[w] = true;
queue.addLast(w);
w = getNextNeighbor(u,w);
}//如果已经被访问过了
w = getNextNeighbor(u,w);
}
}
}
/**
* 对整个图进行广度遍历
*/
public void BFS(){
isVisited = new boolean[getNumOfVertexes()];
for (int i = 0; i < getNumOfVertexes(); i++) {
if(!isVisited[i]){
BFS(isVisited,i);
}
}
System.out.println();
}
测试代码
class Graph{
private ArrayList<String> vertexes; //顶点集
private int[][] edges; //存储改图的邻接矩阵
private int numOfEdges; //边的数量
private boolean[] isVisited ;//标记节点是否别访问过的数组
/**
* 构造器,初始化图的节点集
*/
public Graph(int n) {
this.vertexes = new ArrayList<String>();
edges = new int[n][n];
numOfEdges = 0;
}
/**
* 添加边
* @param v1 顶点1
* @param v2 顶点2
* @param weight 边v1-v2的权值
*/
public void insertEdge(int v1,int v2, int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
/**
* 添加顶点
* @param vertex
*/
public void insertVertex(String vertex){
vertexes.add(vertex);
}
/**
* 获取顶点数
* @return 该图的顶点数目
*/
public int getNumOfVertexes(){
return vertexes.size();
}
/**
* 获取边的数目
* @return 该图的边的数目
*/
public int getNumOfEdges() {
return numOfEdges;
}
/**
* 获取节点的下标(值)
* @param index
* @return
*/
public String getVertexByIndex(int index){
return vertexes.get(index);
}
/**
* 获取边v1-v2的权值
* @param v1 顶点v1
* @param v2 顶点v2
* @return v1-v2的权值
*/
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
/**
* 打印改图的邻接矩阵
*/
public void showGraph(){
for (int[] row: edges) {
for (int edg: row) {
System.out.printf("%d\t",edg);
}
System.out.println();
}
}
/**
* 获取节点v的邻接节点
* @param v 顶点v的下标值
* @return 返回-1说明不存在邻接节点,反之为顶点v的第一个邻接节点的下标值
*/
public int getFirstNeighbor(int v){
for (int i = 0; i < numOfEdges; i++) {
if(edges[v][i] != 0){
return i;
}
}
return -1;
}
/**
* 获取顶点v1的继邻接节点v2之后的下一个邻接节点
* @param v1 顶点v1
* @param v2 顶点v1的邻接顶点v2
* @return 返回-1说明不存在下一个邻接节点,反之为连接这两个顶点的权值
*/
public int getNextNeighbor(int v1,int v2){
for (int i = v2 + 1; i < numOfEdges; i++) {
if(edges[v1][i] != 0){
return i;
}
}
return -1;
}
/**
* 针对单节点的深度优先(DFS)
* 1.访问初始顶点v,并设置为已访问
* 2.获取初始顶点v的邻接顶点w,
* 3.如果w存在,对w进行DFS,如果w不存在,将v顶点的下一个顶点设为初始节点,重新执行1,2,3步
* 4.查找节点v的继w邻接节点的下一个邻接节点,然后执行3
* @param isVisited 记录每个节点是否访问过的数组
* @param v 初始节点
*/
private void DFS(boolean[] isVisited, int v){
int w;//用来存储顶点v的邻接节点
//访问初始顶点,并设置为已访问
System.out.print(getVertexByIndex(v)+"->");
isVisited[v] = true;
//获取第一个邻接顶点
w = getFirstNeighbor(v);
while(w != -1){ //检测顶点v的所有邻接顶点
if(!isVisited[w]){ //如果 w 未访问过
DFS(isVisited,w); //进行深度遍历
}
// 顶点 w 遍历过
w = getNextNeighbor(v,w);//对下一个邻接节点进行访问
}
}
/**
* 对整个图进行深度遍历
*/
public void DFS(){
isVisited = new boolean[getNumOfVertexes()];
for (int i = 0; i < getNumOfVertexes(); i++) {
if(!isVisited[i]){
DFS(isVisited,i);
}
}
System.out.println();
}
/**
* 对单个顶点的广度优先(BFS) 需要一个队列以保持访问过的节点的顺序
* 1.访问初始顶点v,并标记为已访问
* 2.将节点v入队
* 3.当队列不为空时,取得队头节点u,并继续向下执行,反之为空时结束算法
* 4.查找u的第一个邻接节点w
* 5.判断w节点是否存在,如果w节点不存在,跳到第三步,如果w存在则执行下三个步骤
* 5.1 如果顶点w未被访问,则访问顶点w,并标记为已访问
* 5.2 节点 w入队
* 5.3 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤5。
* @param isVisited 标记各顶点是否被访问的数组
* @param v 初始顶点
*/
private void BFS(boolean[] isVisited,int v){
int u;//存放出队节点
int w;//存放u的邻接节点
LinkedList<Integer> queue = new LinkedList<>();
System.out.print(getVertexByIndex(v)+"=>\t");
isVisited[v] = true;
queue.addLast(v);
while(!queue.isEmpty()){
u = queue.removeFirst();
w = getFirstNeighbor(u);
while (w != -1){
if(!isVisited[w]){
System.out.print(getVertexByIndex(w)+"=>\t");
isVisited[w] = true;
queue.addLast(w);
w = getNextNeighbor(u,w);
}//如果已经被访问过了
w = getNextNeighbor(u,w);
}
}
}
/**
* 对整个图进行广度遍历
*/
public void BFS(){
isVisited = new boolean[getNumOfVertexes()];
for (int i = 0; i < getNumOfVertexes(); i++) {
if(!isVisited[i]){
BFS(isVisited,i);
}
}
System.out.println();
}
}
上一篇: 图的遍历,深度优先与广度优先详解
下一篇: 图的遍历(深度优先,广度优先)