课程咨询 :186 8716 1620      qq:2066486918

昆明Java培训 > 达内新闻 > java实现深度、广度优先遍历
  • 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--零基础全日制班

开班日期:12/29

Java--零基础业余班

Java--零基础业余班

开班日期:12/29

Java--周末提升班

Java--周末提升班

开班日期:12/29

Java--零基础周末班

Java--零基础周末班

开班日期:12/29

  • 网址:http://km .java.tedu.cn      地址:昆明市官渡区春城路62号证券大厦附楼6楼
  • 课程培训电话:186 8716 1620      qq:2066486918    全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56