图 的分析

创建一个如图所示的图

import java.util.ArrayList;
import java.util.Arrays;

public class TuTest {
    private  int[][] tu;
    private ArrayList nodelist;
    private int bians;

    public static void main(String[] args) {
        int n = 5;
        String[] nodes = {"a", "b", "c", "d", "e"};
        TuTest tuTest = new TuTest(5);
        for (String value : nodes){
            tuTest.charunode(value);
        }
        tuTest.tianjiabian(0,1,1);
        tuTest.tianjiabian(0,2,1);
        tuTest.tianjiabian(1,2,1);
        tuTest.tianjiabian(1,3,1);
        tuTest.tianjiabian(1,4,1);
        tuTest.showtu();

    }

    public TuTest(int n) {
        tu = new int[n][n];
        nodelist = new ArrayList(n);
        bians = 0;
    }
    //插入节点
    public void charunode(String value){
        nodelist.add(value);
    }
    //添加边
    public void tianjiabian(int i, int j, int quan){
        tu[i][j] = quan;
        tu[j][i] = quan;
        bians ++;
    }
    //常用方法
    public int getBians(){
        return bians;
    }
    public int getNumOfnodes(){
        return nodelist.size();
    }
    public String getValueOfnode(int i){
        return nodelist.get(i);
    }
    public int getquan(int i, int j){
        return tu[i][j];
    }
    public void showtu(){
        for (int[] link : tu){
            System.out.println(Arrays.toString(link));
        }
    }
}

[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]

深度优先遍历

import java.util.ArrayList;
import java.util.Arrays;

public class TuTest {
    private  int[][] tu;
    private ArrayList nodelist;
    private int bians;
    private boolean[] isVis;  //判断该节点是否已经被遍历

    public static void main(String[] args) {
        int n = 5;
        String[] nodes = {"a", "b", "c", "d", "e"};
        TuTest tuTest = new TuTest(5);
        for (String value : nodes){
            tuTest.charunode(value);
        }
        tuTest.tianjiabian(0,1,1);
        tuTest.tianjiabian(0,2,1);
        tuTest.tianjiabian(1,2,1);
        tuTest.tianjiabian(1,3,1);
        tuTest.tianjiabian(1,4,1);
        tuTest.showtu();

        tuTest.dfs();

    }

    public TuTest(int n) {
        tu = new int[n][n];
        nodelist = new ArrayList(n);
        bians = 0;
        isVis = new boolean[n];
    }
    //插入节点
    public void charunode(String value){
        nodelist.add(value);
    }
    //添加边
    public void tianjiabian(int i, int j, int quan){
        tu[i][j] = quan;
        tu[j][i] = quan;
        bians ++;
    }
    //常用方法
    public int getBians(){
        return bians;
    }
    public int getNumOfnodes(){
        return nodelist.size();
    }
    public String getValueOfnode(int i){
        return nodelist.get(i);
    }
    public int getquan(int i, int j){
        return tu[i][j];
    }
    public void showtu(){
        for (int[] link : tu){
            System.out.println(Arrays.toString(link));
        }
    }
    //找到当前节点的第一个邻节点
    public int getFrist(int cur){   //假设此时的图是没有自连接节点的
        for (int j = 0; j < nodelist.size(); j++){
            if (tu[cur][j] > 0){
                return j;
            }
        }
        return -1;
    }
    //知道了当前节点的某一个邻节点, 再找到当前节点下一个邻节点, 也即是根据前一个邻节点得到下一个
    public int getNext(int cur, int pre){
        for (int j = pre+1; j < nodelist.size(); j++){
            if (tu[cur][j] > 0){
                return j;
            }
        }
        return -1;
    }
    //深度优先遍历
    public void dfs (boolean[] isVis , int cur){
        System.out.print(nodelist.get(cur)+"->");
        isVis[cur] = true;
        int w = getFrist(cur);
        while (w != -1){
            if (!isVis[w]){
                dfs(isVis, w);
            }
            w = getNext(cur, w);
        }
    }
    //将dfs方法重载, 使之能够回溯递归
    public void dfs(){
        for (int cur = 0; cur < nodelist.size(); cur++){
            if (!isVis[cur]){
                dfs(isVis, cur);
            }
        }
    }
}

[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
a->b->c->d->e->

广度优先

import java.util.ArrayList;
import java.util.Arrays;
import java.util.linkedList;

public class TuTest {
    private  int[][] tu;
    private ArrayList nodelist;
    private int bians;
    private boolean[] isVis;  //判断该节点是否已经被遍历

    public static void main(String[] args) {
        int n = 5;
        String[] nodes = {"a", "b", "c", "d", "e"};
        TuTest tuTest = new TuTest(5);
        for (String value : nodes){
            tuTest.charunode(value);
        }
        tuTest.tianjiabian(0,1,1);
        tuTest.tianjiabian(0,2,1);
        tuTest.tianjiabian(1,2,1);
        tuTest.tianjiabian(1,3,1);
        tuTest.tianjiabian(1,4,1);
        tuTest.showtu();

        System.out.println("深度优先遍历");
        tuTest.dfs();
        System.out.println("广度优先遍历");
        tuTest.bfs();

    }

    public TuTest(int n) {
        tu = new int[n][n];
        nodelist = new ArrayList(n);
        bians = 0;
        //isVis = new boolean[n];
    }
    //插入节点
    public void charunode(String value){
        nodelist.add(value);
    }
    //添加边
    public void tianjiabian(int i, int j, int quan){
        tu[i][j] = quan;
        tu[j][i] = quan;
        bians ++;
    }
    //常用方法
    public int getBians(){
        return bians;
    }
    public int getNumOfnodes(){
        return nodelist.size();
    }
    public String getValueOfnode(int i){
        return nodelist.get(i);
    }
    public int getquan(int i, int j){
        return tu[i][j];
    }
    public void showtu(){
        for (int[] link : tu){
            System.out.println(Arrays.toString(link));
        }
    }
    //找到当前节点的第一个邻节点
    public int getFrist(int cur){   //假设此时的图是没有自连接节点的
        for (int j = 0; j < nodelist.size(); j++){
            if (tu[cur][j] > 0){
                return j;
            }
        }
        return -1;
    }
    //知道了当前节点的某一个邻节点, 再找到当前节点下一个邻节点, 也即是根据前一个邻节点得到下一个
    public int getNext(int cur, int pre){
        for (int j = pre+1; j < nodelist.size(); j++){
            if (tu[cur][j] > 0){
                return j;
            }
        }
        return -1;
    }
    //深度优先遍历
    public void dfs (boolean[] isVis , int cur){
        System.out.print(nodelist.get(cur)+"->");
        isVis[cur] = true;
        int w = getFrist(cur);
        while (w != -1){
            if (!isVis[w]){
                dfs(isVis, w);
            }
            w = getNext(cur, w);
        }
    }
    //将dfs方法重载, 使之能够回溯递归
    public void dfs(){
        isVis = new boolean[nodelist.size()];
        for (int cur = 0; cur < nodelist.size(); cur++){
            if (!isVis[cur]){
                dfs(isVis, cur);
            }
        }
        System.out.println();
    }
    //广度优先遍历
    public void bfs(boolean[] isVis, int cur){
        int u; //表示队列中的第一个节点的下标
        int w;
        linkedList queue = new linkedList();
        queue.addLast(cur);
        System.out.print(nodelist.get(cur)+"->");
        isVis[cur] = true;
        while (!queue.isEmpty()){
            u = (Integer) queue.removeFirst();
            w = getFrist(u);
            while (w != -1){
                if (!isVis[w]){
                    //bfs(isVis, w);//这样还是深度, 应该是直接打印
                    System.out.print(nodelist.get(w)+"->");
                    isVis[w] = true;
                    queue.addLast(w);
                }
                w = getNext(u, w);
            }
        }
    }
    public void bfs(){
        //isVis = null;
        isVis = new boolean[nodelist.size()];
        for (int cur = 0; cur < nodelist.size(); cur++){
            if (!isVis[cur]){
                bfs(isVis, cur);
            }
        }
        System.out.println();
    }
}

[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
深度优先遍历
a->b->c->d->e->
广度优先遍历
a->b->c->d->e->

以上这个图不能直观的看出深度和广度遍历的区别
我们可以换一个图, 以上代码不变