java圖的遍歷演算法

㈠ 在java中，遍歷是幹嘛用的有什麼意義

你說的比較籠統，遍歷的話，可以遍歷數組，遍歷list，遍歷鏈表，遍歷圖，樹等等，遍歷的意義就在於檢查集合中的元素並做處理。至於什麼順序，那要根據需求嘍。
例子，比較簡單的是，遍歷一個整型數組，找出裡面最大的數。

㈡ java 實現二叉樹的層次遍歷

class TreeNode {
public TreeNode left;

public TreeNode right;

public int value;

public TreeNode(TreeNode left, TreeNode right, int value) {
this.left = left;
this.right = right;
this.value = value;
}
}
public class BinaryTree {

public static int getTreeHeight(TreeNode root) {
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 1;
return 1 + Math
.max(getTreeHeight(root.left), getTreeHeight(root.right));
}

public static void recursePreOrder(TreeNode root) {
if (root == null)
return;
System.out.println(root.value);
if (root.left != null)
recursePreOrder(root.left);
if (root.right != null)
recursePreOrder(root.right);
}

public static void stackPreOrder(TreeNode root) {
Stack stack = new Stack();
if (root == null)
return;
stack.push(root);
System.out.println(root.value);
TreeNode temp = root.left;
while (temp != null) {
stack.push(temp);
System.out.println(temp.value);
temp = temp.left;
}
temp = (TreeNode) stack.pop();
while (temp != null) {
temp = temp.right;
while (temp != null) {
stack.push(temp);
System.out.println(temp.value);
temp = temp.left;
}
if (stack.empty())
break;
temp = (TreeNode) stack.pop();
}
}

public static void recurseInOrder(TreeNode root) {
if (root == null)
return;
if (root.left != null)
recurseInOrder(root.left);
System.out.println(root.value);
if (root.right != null)
recurseInOrder(root.right);
}

public static void stackInOrder(TreeNode root) {
Stack stack = new Stack();
if (root == null)
return;
else
stack.push(root);
TreeNode temp = root.left;
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
temp = (TreeNode) stack.pop();
while (temp != null) {
System.out.println(temp.value);
temp = temp.right;
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
if (stack.empty())
break;
temp = (TreeNode) stack.pop();
}
}

public static void main(String[] args) {
TreeNode node1 = new TreeNode(null, null, 1);
TreeNode node2 = new TreeNode(null, node1, 2);
TreeNode node3 = new TreeNode(null, null, 3);
TreeNode node4 = new TreeNode(node2, node3, 4);
TreeNode node5 = new TreeNode(null, null, 5);
TreeNode root = new TreeNode(node4, node5, 0);
System.out.println("Tree Height is " + getTreeHeight(root));
System.out.println("Recurse In Order Traverse");
recurseInOrder(root);
System.out.println("Stack In Order Traverse");
stackInOrder(root);
System.out.println("Recurse Pre Order Traverse");
recursePreOrder(root);
System.out.println("Stack Pre Order Traverse");
stackPreOrder(root);
}
}
可以做個參考

㈢ java中如何遍歷最短路徑長度鄰接矩陣

packagetest;
importjava.util.ArrayList;
importjava.util.List;
/**
*java-用鄰接矩陣求圖的最短路徑、最長途徑。弗洛伊德演算法
*/
publicclassFloydInGraph{
privatestaticintINF=Integer.MAX_VALUE;
privateint[][]dist;
privateint[][]path;
privateList<Integer>result=newArrayList<Integer>();
publicFloydInGraph(intsize){
this.path=newint[size][size];
this.dist=newint[size][size];
}
publicvoidfindPath(inti,intj){
intk=path[i][j];
if(k==-1)return;
findPath(i,k);
result.add(k);
findPath(k,j);
}
publicvoidfindCheapestPath(intbegin,intend,int[][]matrix){
floyd(matrix);
result.add(begin);
findPath(begin,end);
result.add(end);
}
publicvoidfloyd(int[][]matrix){
intsize=matrix.length;
for(inti=0;i<size;i++){
for(intj=0;j<size;j++){
path[i][j]=-1;
dist[i][j]=matrix[i][j];
}
}
for(intk=0;k<size;k++){
for(inti=0;i<size;i++){
for(intj=0;j<size;j++){
if(dist[i][k]!=INF&&
dist[k][j]!=INF&&
dist[i][k]+dist[k][j]<dist[i][j]){//dist[i][k]+dist[k][j]>dist[i][j]-->longestPath
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=k;
}
}
}
}

}
publicstaticvoidmain(String[]args){
FloydInGraphgraph=newFloydInGraph(5);
int[][]matrix={
{INF,30,INF,10,50},
{INF,INF,60,INF,INF},
{INF,INF,INF,INF,INF},
{INF,INF,INF,INF,30},
{50,INF,40,INF,INF},
};
intbegin=0;
intend=4;
graph.findCheapestPath(begin,end,matrix);
List<Integer>list=graph.result;
System.out.println(begin+"to"+end+",thecheapestpathis:");
System.out.println(list.toString());
System.out.println(graph.dist[begin][end]);
}
}

㈣ java中的遍歷是什麼意思

遍歷就是把每個元素都訪問一次.比如一個二叉樹,遍歷二叉樹意思就是把二叉樹中的每個元素都訪問一次

㈤ java 二叉樹前序遍歷

//類Node定義二叉樹結點的數據結構;
//一個結點應包含結點值，左子結點的引用和右子結點的引用
class Node{
public Node left; //左子結點
public Node right; //右子結點
public int value; //結點值
public Node(int val){
value = val;
}
}

public class Traversal
{
//read()方法將按照前序遍歷的方式遍歷輸出二叉樹的結點值
//此處採用遞歸演算法會比較簡單，也容易理解，當然也可以用
//循環的方法遍歷，但會比較復雜，也比較難懂。二叉樹遍歷
//用遞歸演算法最為簡單，因為每個結點的遍歷方式都是，根，
//左，右，遞歸的調用可以讓每個結點以這種方式遍歷
public static void read(Node node){
if(node != null){
System.out.println(node.value);//輸出當前結點的值
if(node.left != null)
read(node.left); //遞歸調用 先讀左結點
if(node.right != null)
read(node.right); //遞歸調用 後讀右結點
}
}

public static void main(String[] args){
//初始化5個結點，分別初始值為1，2，3，4，5
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);

//構建二叉樹，以n1為根結點
n1.left = n2;
n1.right = n5;
n2.left = n3;
n2.right = n4;

read(n1);
}
}
注釋和代碼都是我自己寫的，如果樓主覺得有的注釋多餘可以自己刪除一些！代碼我都編譯通過，並且運行結果如你提的要求一樣！你只要把代碼復制編譯就可以了，注意要以文件名Traversal.java來保存，否則編譯不通過，因為main函數所在的類是public類型的！

㈥ 圖的遍歷演算法java解決方案

二叉樹具有以下重要性質：
性質1 二叉樹第i層上的結點數目最多為2i-1(i≥1)。
證明：用數學歸納法證明：
歸納基礎：i=1時，有2i-1=20=1。因為第1層上只有一個根結點，所以命題成立。
歸納假設：假設對所有的j(1≤j<i)命題成立，即第j層上至多有2j-1個結點，證明j=i時命題亦成立。
歸納步驟：根據歸納假設，第i-1層上至多有2i-2個結點。由於二叉樹的每個結點至多有兩個孩子，故第i層上的結點數至多是第i-1層上的最大結點數的2倍。即j=i時，該層上至多有2×2i-2=2i-1個結點，故命題成立。

性質2 深度為k的二叉樹至多有2k-1個結點(k≥1)。
證明：在具有相同深度的二叉樹中，僅當每一層都含有最大結點數時，其樹中結點數最多。因此利用性質1可得，深度為k的二叉樹的結點數至多為：
20+21+…+2k-1=2k-1
故命題正確。

性質3 在任意-棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則no=n2+1。
證明：因為二叉樹中所有結點的度數均不大於2，所以結點總數(記為n)應等於0度結點數、1度結點(記為n1)和2度結點數之和：
n=no+n1+n2 (式子1)
另一方面，1度結點有一個孩子，2度結點有兩個孩子，故二叉樹中孩子結點總數是：
nl+2n2
樹中只有根結點不是任何結點的孩子，故二叉樹中的結點總數又可表示為：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
no=n2+1

滿二叉樹和完全二叉樹是二叉樹的兩種特殊情形。
1、滿二叉樹(FullBinaryTree)
一棵深度為k且有2k-1個結點的二又樹稱為滿二叉樹。
滿二叉樹的特點：
（1） 每一層上的結點數都達到最大值。即對給定的高度，它是具有最多結點數的二叉樹。
（2） 滿二叉樹中不存在度數為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層上。
【例】圖(a)是一個深度為4的滿二叉樹。

2、完全二叉樹(Complete BinaryTree)
若一棵二叉樹至多隻有最下面的兩層上結點的度數可以小於2，並且最下一層上的結點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。
特點：
（1） 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。
（2） 在滿二叉樹的最下一層上，從最右邊開始連續刪去若干結點後得到的二叉樹仍然是一棵完全二叉樹。
（3） 在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該結點必是葉結點。
【例】如圖(c)中，結點F沒有左孩子而有右孩子L，故它不是一棵完全二叉樹。
【例】圖(b)是一棵完全二叉樹。

性質4 具有n個結點的完全二叉樹的深度為

證明：設所求完全二叉樹的深度為k。由完全二叉樹定義可得：
深度為k得完全二叉樹的前k-1層是深度為k-1的滿二叉樹，一共有2k-1-1個結點。
由於完全二叉樹深度為k，故第k層上還有若干個結點，因此該完全二叉樹的結點個數：
n>2k-1-1。
另一方面，由性質2可得：
n≤2k-1，
即：2k-1-l<n≤2k-1
由此可推出：2k-1≤n<2k，取對數後有：
k-1≤lgn<k
又因k-1和k是相鄰的兩個整數，故有
,
由此即得：

㈦ java層次遍歷演算法思路

找個例子看一下就有了。比如遞歸前序遍歷二叉樹，即先根遍歷。先遍歷根節點，之後向下又是一個跟節點，在遍歷做節點，在遍歷右節點，依次下去，知道沒有右節點結束。在遍歷右邊的部分，根節點，左節點，右節點，知道沒有右節點是為止。至此遍歷結束。書上有圖一看就知道了。其他的遍歷按照遍歷演算法一樣。建議看下數據結構的遍歷，講的很詳細。

㈧ java中」遍歷「，」迭代「是什麼意思

首先解釋迭代。
迭代簡單的理解，重文字上可以才分為 迭(疊)加，代入(數)
是利用計算機高速、可從重復性高的特點進行計算的模式
迭代的最簡單應用就是，把四維整型數組，中的內容全部輸出。那就用四層循環慢慢取吧。
每次循環做的事情基本上是一件事，無外乎就是角標自增，然後取數。

再說遍歷。
遍歷很好理解，通過某種方式，不論是重頭到尾，還是用Hash演算法，
反正是從頭到尾把數據結構（鏈表、數組、樹、圖）所有的節點都訪問一遍，就叫遍歷。
像剛才，四維數組取數，就是一個遍歷的過程，
簡單的使用迭代的方式，從第一個元素一直遍歷（取）到最後一個元素。
稍微復雜的還有遍歷二叉樹，遍歷歐拉圖等。都用相應的演算法。

㈨ 在不知道任何條件的情況下如何實現java遍歷文件夾下的所有圖片

/**
* 在dir目錄及其子目錄中
* 查找符合給定格式的文件
* @param dir 查找的文件夾
* @param regex 文件格式正則表達式
* @return 找到的文件對象數組
*/
public static File[] search(File dir,final String regex){
Deque<File> stack = new LinkedList<File>();
Deque<File> allDir = new LinkedList<File>();
stack.push(dir);

//獲得所有文件夾，包括深層目錄
while(!stack.isEmpty()){
dir = stack.poll();
allDir.push(dir);
File[] dirs = dir.listFiles(new FileFilter(){
public boolean accept(File f){
return f.isDirectory();//只列出子目錄
}
});
for(File f:dirs){
stack.push(f);
}
}

//allDir中所有的目錄中匹配的文件
//放入List
ArrayList<File> list = new ArrayList<File>();
while(!allDir.isEmpty()){
File d = allDir.pop();
File[] files = d.listFiles(new FileFilter(){
public boolean accept(File f) {
//目錄不要
if(f.isDirectory()) {return false;}
//只要匹配的文件
return f.getName().matches(regex);
}

});
for(File f:files){
list.add(f);
}
}
File[] arr = new File[list.size()];
return list.toArray(arr);
}

第一個參數是路徑，第二個匹配文件類型。

㈩ 圖的深度優先遍歷Java演算法

圖的深度優先搜索的非遞歸版本演算法的兩種實現，很詳細
http://blog.csdn.net/EmilMatthew/archive/2006/01/17/582381.aspx