图的操作
【摘要】 企业笔试过程中会涉及到数据结构的方方面面,现将有关图的深度优先搜索与广度优先搜索进行整理归纳,方便日后查阅。在已做过的笔试题目中,可用DFS解决的题目有:“地牢逃脱”–网易“遍历最短路径长度”–携程“小青蛙走迷宫”–滴滴三道题目都是DFS的经典应用,主要采用递归+回溯的方式。下面主要讲解一下DFS与BFS的具体实现。 深度优先搜索(DFS) && 广度优先搜索(BFS)package cn....
企业笔试过程中会涉及到数据结构的方方面面,现将有关图的深度优先搜索与广度优先搜索进行整理归纳,方便日后查阅。
在已做过的笔试题目中,可用DFS解决的题目有:
三道题目都是DFS的经典应用,主要采用递归+回溯的方式。
下面主要讲解一下DFS与BFS的具体实现。
深度优先搜索(DFS) && 广度优先搜索(BFS)
package cn.edu.ujn.graph;
import java.util.ArrayList;
import java.util.LinkedList;
/**
* @description 邻接矩阵模型类
* @author SHQ
* @time 2016.09.12
*/
public class DFS_BFS {
private ArrayList<Object> vertexList;// 存储点的链表
private int[][] edges; // 邻接矩阵,用来存储边
private int numOfEdges; // 边的数目
boolean[] isVisited; // 遍历标志位
public DFS_BFS(int n) {
//初始化矩阵,二维数组,和边的数目
edges = new int[n][n];
vertexList = new ArrayList<Object>(n);
numOfEdges = 0;
// 将所有节点访问标志位均置为未访问
isVisited = new boolean[n];
for(int i = 0; i < n; i++){
isVisited[i] = false;
}
}
// 得到结点的个数
public int getNumOfVertex() {
return vertexList.size();
}
// 得到边的数目
public int getNumOfEdges() {
return numOfEdges;
}
// 返回结点i的数据
public Object getValueByIndex(int i) {
return vertexList.get(i);
}
// 返回v1,v2的权值
public int getWeight(int v1,int v2) {
return edges[v1][v2];
}
//插入结点
public void insertVertex(Object vertex) {
vertexList.add(vertexList.size(),vertex);
}
//插入结点
public void insertEdge(int v1,int v2,int weight) {
edges[v1][v2]=weight;
numOfEdges++;
}
//删除结点
public void deleteEdge(int v1,int v2) {
edges[v1][v2] = 0;
numOfEdges--;
}
// 得到第一个邻接结点的下标
public int getFirstNeighbor(int index) {
for(int j = 0; j < vertexList.size(); j++) {
if (edges[index][j] > 0) {
return j;
}
}
return -1;
}
// 根据前一个邻接结点的下标来取得下一个邻接结点
public int getNextNeighbor(int v1, int v2) {
for (int j = v2+1; j < vertexList.size(); j++) {
if (edges[v1][j]>0) {
return j;
}
}
return -1;
}
// 私有函数,深度优先遍历
private void depthFirstSearch(boolean[] isVisited,int i) {
// 首先访问该结点,在控制台打印出来
System.out.print(getValueByIndex(i) + " ");
// 置该结点为已访问
isVisited[i] = true;
int w = getFirstNeighbor(i);
while (w != -1) {
if (!isVisited[w]) {
depthFirstSearch(isVisited,w);
}
w = getNextNeighbor(i, w);
}
}
// 对外公开函数,深度优先遍历,与其同名私有函数属于方法重载
public void depthFirstSearch() {
for(int i = 0; i < getNumOfVertex(); i++) {
//因为对于非连通图来说,并不是通过一个结点就一定可以遍历所有结点的。
if (!isVisited[i]) {
depthFirstSearch(isVisited,i);
}
}
}
/**
* 私有函数,广度优先遍历
* 遍历步骤:
* 1.访问初始结点v并标记结点v为已访问。
* 2.结点v入队列
* 3.当队列非空时,继续执行,否则算法结束。
* 4.出队列,取得队头结点u。
* 5.查找结点u的第一个邻接结点w。
* 6.若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:
* 1)若结点w尚未被访问,则访问结点w并标记为已访问。
* 2)结点w入队列
* 3)查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。
* @param isVisited
* @param i
*/
private void broadFirstSearch(boolean[] isVisited, int i) {
int u, w;
// 借助辅助队列,记录访问顺序
LinkedList<Object> queue = new LinkedList<Object>();
// 访问结点i
System.out.print(getValueByIndex(i) + " ");
isVisited[i] = true;
// 结点入队列
queue.addLast(i);
while (!queue.isEmpty()) {
u = ((Integer)queue.removeFirst()).intValue();
w = getFirstNeighbor(u);
while(w != -1) {
if(!isVisited[w]) {
//访问该结点
System.out.print(getValueByIndex(w)+" ");
//标记已被访问
isVisited[w] = true;
//入队列
queue.addLast(w);
}
//寻找下一个邻接结点
w = getNextNeighbor(u, w);
}
}
}
//对外公开函数,广度优先遍历
public void broadFirstSearch() {
for(int i = 0; i < getNumOfVertex(); i++) {
if(!isVisited[i]) {
broadFirstSearch(isVisited, i);
}
}
}
}
Main.java
package cn.edu.ujn.graph;
public class Main {
public static void main(String args[]) {
int n = 8, e = 9; // 分别代表结点个数和边的数目
String labels[]={"1","2","3","4","5","6","7","8"}; // 结点的标识
DFS_BFS graph = new DFS_BFS(n);
for(String label : labels) {
graph.insertVertex(label); // 插入结点
}
//插入九条边
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 4, 1);
graph.insertEdge(3, 7, 1);
graph.insertEdge(4, 7, 1);
graph.insertEdge(2, 5, 1);
graph.insertEdge(2, 6, 1);
graph.insertEdge(5, 6, 1);
graph.insertEdge(1, 0, 1);
graph.insertEdge(2, 0, 1);
graph.insertEdge(3, 1, 1);
graph.insertEdge(4, 1, 1);
graph.insertEdge(7, 3, 1);
graph.insertEdge(7, 4, 1);
graph.insertEdge(6, 2, 1);
graph.insertEdge(5, 2, 1);
graph.insertEdge(6, 5, 1);
/* System.out.println("深度优先搜索序列为:");
graph.depthFirstSearch();
System.out.println();*/
System.out.println("广度优先搜索序列为:");
graph.broadFirstSearch();
}
}
【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)