图片 2

 


2 解决方案

 


1 问题描述

广度优先查找(Breadth-first
Search,BFS)按照一种同心圆的方式,首先访问所有和初始顶点邻接的顶点,然后是离它两条边的所有未访问顶点,以此类推,直到所有与初始顶点同在一个连通分量中的顶点都被访问过了为止。如果仍然存在未被访问的顶点,该算法必须从图的其他连接分量中的任意顶点重新开始。

2.1 蛮力法

此处借用《算法设计与分析基础》(第3版)上一段文字介绍及其配图来讲解,下面程序中使用的图就是配图中所给的数据,在程序中,使用邻接矩阵来表示配图中图。

 图片 1

图片 2

PS:下面所给程序的运行结果和配图中图(b)顺序在fb那两个位置不一致,下面程序运行结果顺序是acdebfghji,原因是在遍历的过程中,我所写代码是按照字母顺序来进行遍历的,课本上所讲可能是使用链表来存储顶点,具体怎么实现本人也未去仔细探讨…

具体代码如下:

package com.liuzhen.chapterThree;

public class BreadthFirstSearch {
    public int count = 0;           //计算广度优先遍历总次数,初始化为0
     /*
     * adjMatrix是待遍历图的邻接矩阵
     * value是待遍历图顶点用于是否被遍历的判断依据,0代表未遍历,非0代表已被遍历,其最终具体结果代表该顶点在最终遍历顺序中的位置
     * result用于存放广度优先遍历的顶点顺序
     */
    public void bfs(int[][] adjMatrix,int[] value,char[] result){
        for(int i = 0;i < value.length;i++){
            if(value[i] == 0){                 //当该顶点未被遍历时
                char temp = (char) ('a' + i);
                result[count] = temp;
                System.out.println();
                System.out.println("出发点:"+temp+"地");
                bfsVisit(adjMatrix,value,result,i);           //使用迭代遍历该顶点周边所有邻接顶点
            }
        }
    }
     /*
     * adjMatrix是待遍历图的邻接矩阵
     * value是待遍历图顶点用于是否被遍历的判断依据,0代表未遍历,非0代表已被遍历,其最终具体结果代表该顶点在最终遍历顺序中的位置
     * result用于存放广度优先遍历的顶点顺序
     * number是当前正在遍历的顶点在邻接矩阵中的数组下标编号
     */
    public void bfsVisit(int[][] adjMatrix,int[] value,char[] result,int number){
        value[number] = ++count;           //出发顶点已被遍历,其在遍历结果中最终位置为++count
        for(int i = 0;i < value.length;i++){
            if(adjMatrix[number][i] == 1 && value[i] == 0){         //当改顶点与出发顶点相邻且未被遍历时
                char temp = (char) ('a' + i);
                result[count] = temp;
                System.out.print("到达"+temp+"地"+"\t");
                value[i] = ++count;                 //当前被遍历顶点,其在遍历结果中最终位置为++count
            }
        }
    }

    public static void main(String[] args){
        int[] value = new int[10];              //初始化后,各元素均为0
        char[] result = new char[10];
        char[] result1 = new char[10];
        int[][] adjMatrix = {{0,0,1,1,1,0,0,0,0,0},
                {0,0,0,0,1,1,0,0,0,0},
                {1,0,0,1,0,1,0,0,0,0},
                {1,0,1,0,0,0,0,0,0,0},
                {1,1,0,0,0,1,0,0,0,0},
                {0,1,1,0,1,0,0,0,0,0},
                {0,0,0,0,0,0,0,1,0,1},
                {0,0,0,0,0,0,1,0,1,0},
                {0,0,0,0,0,0,0,1,0,1},
                {0,0,0,0,0,0,1,0,1,0}};
        BreadthFirstSearch test = new BreadthFirstSearch();
        test.bfs(adjMatrix, value, result);
        System.out.println();
        System.out.println("判断节点是否被遍历结果(0代表未遍历,非0代表已被遍历):");
        for(int i = 0;i < value.length;i++)
            System.out.print("  "+value[i]);
        //依据具体顶点在遍历结果顺序中最终位置,计算其具体遍历顺序为result1数组序列
        for(int i = 0;i < value.length;i++){
            result1[value[i]-1] = (char) ('a' + i);
        }
        System.out.println();
        System.out.println("判断节点是否被遍历结果(0代表未遍历,非0代表已被遍历,其具体数字代表其原地点在被遍历结果中所处位置:):");
        for(int i = 0;i < value.length;i++)
            System.out.print("  "+result1[i]);
        System.out.println();
        System.out.println("广度优先查找遍历顺序如下:");
        for(int i = 0;i < result.length;i++)
            System.out.print("  "+result[i]);
    }
}

 

 

运行结果:

出发点:a地
到达c地    到达d地    到达e地    
出发点:b地
到达f地    
出发点:g地
到达h地    到达j地    
出发点:i地

判断节点是否被遍历结果(0代表未遍历,非0代表已被遍历):
  1  5  2  3  4  6  7  8  10  9
判断节点是否被遍历结果(0代表未遍历,非0代表已被遍历,其具体数字代表其原地点在被遍历结果中所处位置:):
  a  c  d  e  b  f  g  h  j  i
广度优先查找遍历顺序如下:
  a  c  d  e  b  f  g  h  j  i

 

目录

1 style=”font-family: 宋体;”>问题描述

2 style=”font-family: 宋体;”>解决方案

2.1 style=”font-family: 宋体;”>蛮力法

admin

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注