昆明java培训
达内昆明广州春城路

18487146383

热门课程

java实现深度、广度优先遍历

  • 时间:2015-10-26
  • 发布:达内科技
  • 来源:达内昆明

题目:二叉树为下图结构,请写出深度、广度优先遍历算法代码。

作为代码分享,那么昆明java培训机构就把已经调式成功的代码与大家分享,如有更好的想法,记得大家一起交流学习。

昆明java培训机构

深度优先遍历算法代码:

import java.util.ArrayList;

import java.util.LinkedList;

/**

* @description 邻接矩阵模型类

* @author beanlam

* @time 2015.4.17

*/

public class AMWGraph {

private ArrayList vertexList;//存储点的链表

private int[][] edges;//邻接矩阵,用来存储边

private int numOfEdges;//边的数目

public AMWGraph(int n) {

//初始化矩阵,一维数组,和边的数目

edges=new int[n][n];

vertexList=new ArrayList(n);

numOfEdges=0;

}

//得到结点的个数

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

if (edges[index][j]>0) {

return j;

}

}

return -1;

}

//根据前一个邻接结点的下标来取得下一个邻接结点

public int getNextNeighbor(int v1,int v2) {

for (int j=v2+1;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() {

boolean[] isVisited=new boolean[getNumOfVertex()];

//记录结点是否已经被访问的数组

for (int i=0;i

isVisited[i]=false;//把所有节点设置为未访问

}

for(int i=0;i

//因为对于非连通图来说,并不是通过一个结点就一定可以遍历所有结点的。

if (!isVisited[i]) {

depthFirstSearch(isVisited,i);

}

}

}

//私有函数,广度优先遍历

private void broadFirstSearch(boolean[] isVisited,int i) {

int u,w;

LinkedList queue=new LinkedList();

//访问结点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() {

boolean[] isVisited=new boolean[getNumOfVertex()];

for (int i=0;i

isVisited[i]=false;

}

for(int i=0;i

if(!isVisited[i]) {

broadFirstSearch(isVisited, i);

}

}

}

}

广度优先遍历算法代码:

public class TestSearch {

public static void main(String args[]) {

int n=8,e=9;//分别代表结点个数和边的数目

String labels[]={"1","2","3","4","5","6","7","8"};//结点的标识

AMWGraph graph=new AMWGraph(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(4, 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();

}

}

运行结果如下图:

昆明java培训机构

如需算法详细逻辑解析请点击:算法试题——树的深度、广度优先遍历算法及非递归。

上一篇:昆明Java培训分享:Java递归与非递归算法详解
下一篇:学习Java,还需要学好哪些知识?

昆明java培训机构:java未来的发展走向

昆明java培训机构:java学完可以干什么!

昆明java培训机构:如何搞定BAT和华为offer?有这份攻略就够了!

昆明java培训机构:学Java别担心枯燥和无聊

选择城市和中心
贵州省

广西省

海南省

扫一扫

了解更多干货