基于Java实现的图的广度优先遍历算法

本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,具体方法如下:

用邻接矩阵存储图方法:

1.确定图的顶点个数和边的个数

2.输入顶点信息存储在一维数组vertex中

3.初始化邻接矩阵;

4.依次输入每条边存储在邻接矩阵arc中

输入边依附的两个顶点的序号i,j;
将邻接矩阵的第i行第j列的元素值置为1;
将邻接矩阵的第j行第i列的元素值置为1;

广度优先遍历实现:

1.初始化队列Q
2.访问顶点v;visited[v]=1;顶点v入队Q;
3.while(队列Q非空)

v=队列Q的队头元素出队;
w=顶点v的第一个邻接点
while(w存在)

如果w未被访问,则访问顶点w;visited[w]=1;顶点w入队列Q

w=顶点v的下一个邻接点

实现代码如下:

package com.teradata.lsw.sort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFS {

// 存储节点信息
private Object[] vertices;
// 存储边的信息数组
private int[][] arcs;
// 边的条数
private int vexnum;
// 记录第i个节点是否被访问过
private boolean[] visited;
//构建一个临时链表存已经遍历过的节点
private List<Object> temp = new ArrayList<Object>();

/**
* @param args
*
* @author TD_LSW
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

BFS g = new BFS(8);
Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
g.addVertex(vertices);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
g.addEdge(2, 6);
g.addEdge(2, 7);

System.out.println("图的广度优先遍历:");
g.bfs();
}

// 广度优先遍历实现
private void bfs() {
// TODO Auto-generated method stub
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 0; i < vexnum; i++) {
if (!visited[i]) {
visited[i] = true;
visit(i);
q.add(i);
while (!q.isEmpty()) {
int j = (Integer) q.remove().intValue();
//判断如果全部遍历完了就不需要循环了
if (temp.size() == vexnum) {
q.removeAll(q);
return;
}
for (int k = this.firstAdjVex(j); k >= 0; k = this
.nextAdjVex(j, k)) {
if (!visited[k]) {
q.add(k);
visited[k] = true;
visit(k);
}
}
}
}
}

}

// 查找下一个节点
public int firstAdjVex(int i) {
for (int j = 0; j < vexnum; j++) {
if (arcs[i][j] > 0)
return j;
}
return -1;
}

public int nextAdjVex(int i, int k) {
for (int j = k + 1; j < vexnum; j++) {
if (arcs[i][j] > 0)
return j;
}
return -1;
}

// 初始化图的边
private void addEdge(int i, int j) {
// TODO Auto-generated method stub
if (i == j)
return;
arcs[i][j] = 1;
arcs[j][i] = 1;

}

// 初始化图的节点
private void addVertex(Object[] object) {
// TODO Auto-generated method stub
this.vertices = object;
}

// 图的初始化
public BFS(int n) {
// TODO Auto-generated constructor stub
vexnum = n;
vertices = new Object[n];
arcs = new int[n][n];
visited = new boolean[n];
for (int i = 0; i < vexnum; i++) {
for (int j = 0; j < vexnum; j++) {
arcs[i][j] = 0;
}
}
}

private void visit(int i) {
// TODO Auto-generated method stub
temp.add(vertices[i]);
System.out.print(vertices[i] + " ");
}

}
时间: 2014-07-22

分享Java常用几种加密算法(四种)

对称加密算法是应用较早的加密算法,技术成熟.在对称加密算法中,数据发信方将明文(原始数据)和加密密钥(mi yue)一起经过特殊加密算法处理后,使其变成复杂的加密密文发送出去.收信方收到密文后,若想解读原文,则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密,才能使其恢复成可读明文.在对称加密算法中,使用的密钥只有一个,发收信双方都使用这个密钥对数据进行加密和解密,这就要求解密方事先必须知道加密密钥. 简单的java加密算法有: BASE 严格地说,属于编码格式,而非加密算法 MD(Mes

浅谈java实现背包算法(0-1背包问题)

0-1背包的问题 背包问题(Knapsack problem)是一种组合优化的NP完全问题.问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高.问题的名称来源于如何选择最合适的物品放置于给定背包中. 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放. 用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值.则其状态转移方程便是: f[i][v]=max{ f[i-1][v], f

使用java实现LIS算法,出操队形的问题

假设有序列:2,1,3,5,求一个最长上升子序列就是2,3,5或者1,3,5,长度都为3. LIS算法的思想是: 设存在序列a. ① 如果只有一个元素,那么最长上升子序列的长度为1: ② 如果有两个元素,那么如果a[1]>a[0],则最长上升子序列的长度为2,a[1]为该最长上升子序列的最后一个元素;若a[1]<a[0],则最长上升子序列的长度为1,a[0]和a[1]均为  其最长上升子序列的最后一个元素. ③ 如果由三个元素,那么如果a[2]>a[0],a[2]>a[1],则a[

java基于递归算法实现汉诺塔问题实例

本文实例讲述了java基于递归算法实现汉诺塔问题.分享给大家供大家参考,具体如下: package test; import java.util.List; import java.util.ArrayList; import java.util.Scanner; import sun.net.www.content.audio.x_aiff; /** * @author 年浩 * */ public class test { public static void move(char x,cha

Java递归算法经典实例(经典兔子问题)

题目:古典问题:3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 分析:首先我们要明白题目的意思指的是每个月的兔子总对数:假设将兔子分为小中大三种,兔子从出生后三个月后每个月就会生出一对兔子, 那么我们假定第一个月的兔子为小兔子,第二个月为中兔子,第三个月之后就为大兔子,那么第一个月分别有1.0.0,第二个月分别为0.1.0, 第三个月分别为1.0.1,第四个月分别为,1.1.1,第五个月分别为2.1.2,第六个月分别为3.2.3,第

Java猴子吃桃问题

题目:猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半,还不瘾,又多吃了一个 第二天早上又将剩下的桃子吃掉一半,又多吃了一个.以后每天早上都吃了前一天剩下 的一半零一个.到第10天早上想再吃时,见只剩下一个桃子了.求第一天共摘了多少. 程序分析:采取逆向思维的方法,从后往前推断. 程序设计: public class 猴子吃桃 { static int total(int day){ if(day == 10){ return 1; } else{ return (total(day+1)+

Java实现的猴子吃桃问题算法示例

本文实例讲述了Java实现的猴子吃桃问题算法.分享给大家供大家参考,具体如下: 猴子吃桃问题 概述:猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个:第二天又将剩下的桃子吃掉了一半,又多吃了一个:以后每天都吃前一天身下的一半零一个,到第n天再想吃的时候就只剩下一个桃子了,求第一天共摘了多少个桃子? 思路及演算步骤(求出共摘多少桃子的函数表达式): 离现在的天数作为变量 f(1) = 1 (剩下桃子的数目) f(2) = f(3) - (吃掉了一些) =   f(3) -(f(3)/

Java数据结构及算法实例:汉诺塔问题 Hanoi

/** * 汉诺塔大学的时候就学过,但是根本没搞明白,唯一知道的就是要用递归的方法来求解. * 问题描述: * 有三根杆子A,B,C.A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小. * 要求按下列规则将所有圆盘移至C杆: * 1.每次只能移动一个圆盘: * 2.大盘不能叠在小盘上面. * 提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆, * 但都必须尊循上述两条规则. * 问:如何移?最少要移动多少次? * 解决方法: * 假设只有2个盘子,柱子分别是A, B, C柱

Java使用递归解决算法问题的实例讲解

解释:程序调用自身的编程技巧叫做递归. 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量.递归的能力在于用有限的语句来定义对象的无限集合. 递归的三个条件: 1.边界条件 2.递归前进段 3.递归返回段 当边界条件不满足时,

Java基于循环递归回溯实现八皇后问题算法示例

本文实例讲述了Java基于循环递归回溯实现八皇后问题.分享给大家供大家参考,具体如下: 运行效果图如下: 棋盘接口 /** * 棋盘接口 * @author Administrator * */ public interface Piece { abstract boolean isRow(int line); abstract boolean isCol(int line,int col); } 棋盘类: /** * 棋盘 * @author Administrator * */ public

Java基于余弦方法实现的计算相似度算法示例

本文实例讲述了Java基于余弦方法实现的计算相似度算法.分享给大家供大家参考,具体如下: (1)余弦相似性 通过测量两个向量之间的角的余弦值来度量它们之间的相似性.0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1.从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向.所以,它通常用于文件比较. 相关介绍可参考百度百科:余弦相似性 (2)算法实现的中未使用权重(IDF ---逆文档频率),使用词项的出现次数作为向量空间的值. import java.util.H

Python基于生成器迭代实现的八皇后问题示例

本文实例讲述了Python基于生成器迭代实现的八皇后问题.分享给大家供大家参考,具体如下: 问题:有一个棋盘和8个要放到上面的皇后,唯一的要求是皇后之间不能形成威胁.也就是说,必须把他们防止成每个皇后都不能吃掉其他皇后的状态. # -*- coding: utf-8 -*- #python 2.7.13 __metaclass__ = type def confict(state, nextX): nextY = len(state) for i in range(nextY): if abs(

C语言八皇后问题解决方法示例【暴力法与回溯法】

本文实例讲述了C语言八皇后问题解决方法.分享给大家供大家参考,具体如下: 1.概述: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上. 2.暴力法求解: #include<cstdio> #include<cmath> const int maxn=11; int count=0; //P为当前排列,hashTable记录整数x是否已经在

Java基于迭代器模式实现的访问人员列表操作示例

本文实例讲述了Java基于迭代器模式实现的访问人员列表操作.分享给大家供大家参考,具体如下: 一 模式定义 迭代器模式,提供了一种模式顺序访问一个集合对象中各个元素的功能,而又不暴露其内部的表示. 二 模式举例 1 模式分析 我们借用访问人员列表这一案例来说明这一模式. 2 迭代器模式静态类图 3 代码示例 3.1 人员信息接口--IPerson package com.demo.person; /** * 人员信息 * * @author * */ public interface IPers

Java基于解释器模式实现定义一种简单的语言功能示例

本文实例讲述了Java基于解释器模式实现定义一种简单的语言功能.分享给大家供大家参考,具体如下: 一 模式定义 解释器模式:就是给定一个语言的文法表示,并且定义一个解释器,用来解释语言中的句子.解释器模式描述了怎样在有了一个简单的文法后,使用模式设计解释这些语句. 二 模式举例 1 模式分析 我们自己设计一种语言来说明这一模式 (1)该语言区分大小写 (2)该语言以PROGRAM开头,END结尾 (3)PRINTLN表示打印一行并换行 (4)使用FOR-FROM-TO-END表示循环 示例语言内

Java基于反射机制实现全部注解获取的方法示例

本文实例讲述了Java基于反射机制实现全部注解获取的方法.分享给大家供大家参考,具体如下: 一 代码 class Info{ //给mytoString方法加了2个内建Annotation @Deprecated @SuppressWarnings(value = "This is a waring!") public String mytoString(){ return "hello world"; } } class GetAnnotations{ publi

Java实现二叉树的深度优先遍历和广度优先遍历算法示例

本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1. 分析 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列. 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树. 中序遍历:对任一子树,先遍历其左子树,然

Java求10到100000之间的水仙花数算法示例

本文实例讲述了Java求10到100000之间的水仙花数算法.分享给大家供大家参考,具体如下: 水仙花数: 概念:水仙花数是指一个 n 位数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身.(例如:1^3 + 5^3+ 3^3 = 153) 算法思路分析:这个算法我们分两个步骤来进行:第一:我们做一个求一个数的位数的函数:第二:我们通过调用此函数来进行10到100000之间素数的计算! 下面给出具体的代码(仅供参考): package javastudy; public class

Java获得一个数组的指定长度排列组合算法示例

本文实例讲述了Java获得一个数组的指定长度排列组合算法.分享给大家供大家参考,具体如下: package demo; import java.util.Stack; /** * JAVA获得一个数组的指定长度的排列组合.<br> * * @author JAVA世纪网(java2000.net, laozizhu.com) */ public class TestSequenceAll { public static void main(String[] args) { TestSequen