数据结构Java版之深度优先-图（十二）

这里用深度优先遍历存在矩阵里面的图。

　　深度优先利用的是栈的FIFO特性。为此遍历到底后，可以找到最相邻的节点继续遍历。实现深度优先，还需要在节点加上一个访问标识，来确定该节点是否已经被访问过了。

源码：

package mygraph;

import java.util.Stack;

public class DFS_Vertex {
　　 //创建一个我们需要的节点类

    class Vertex {

        private char lable;

        private int val;

        private boolean wasvisited;

        Vertex(char lable) {

            this.lable = lable;

        }

        Vertex() {

        }

    }

    private char lable; // 矩阵元素

    private Vertex[][] list = new Vertex[20][20];

    private Vertex[] vertexList = new Vertex[20];

    private int nVerts; // 当前顶点下标

    DFS_Vertex() {

        this.nVerts = 0;

        for(int i = 0; i < 20; i ++) {

            for(int j = 0; j < 20; j ++) {

                list[i][j] = new Vertex();

            }

        }

    }

    // 增加一个顶点

    public void addVertex(char lable) {

        vertexList[nVerts++] = new Vertex(lable);

    }

    // 增加一条边

    public void addEdge(int start, int end) {

        list[start][end].val = 1;

        list[end][start].val = 1;

    }

    // 打印矩阵

    public void printMatrix() {

        for (int i = 0; i < nVerts; i++) {

            for (int j = 0; j < nVerts; j++) {

                System.out.print(list[i][j].val);

            }

            System.out.println();

        }

    }

    //显示字符

    public void showVertex(int v) {

        System.out.print(vertexList[v].lable + "\t");

    }

    //获得邻接未访问节点

    public int getAdjUnvisitedVertex(int v) {

        for(int j = 0; j < nVerts; j ++) {

            if((list[v][j].val == 1) && (vertexList[j].wasvisited == false)) {

                return j;

            }

        }

        return -1;

    }

    //DFS

    public void DFS() {

        Stack<Integer> s = new Stack();

        vertexList[0].wasvisited = true;

        showVertex(0);

        s.push(0);

        int v;

        while(s.size() > 0) {

            v = getAdjUnvisitedVertex(s.peek());

            if(v == -1) {

                s.pop();

            }else {

                vertexList[v].wasvisited = true;

                showVertex(v);

                s.push(v);

            }

        }

        for(int j = 0; j < nVerts; j ++) {

            vertexList[j].wasvisited = false;

        }

    }

}

测试程序：

    public static void main(String[] args) {

        DFS_Vertex ds = new DFS_Vertex();

        ds.addVertex('A');    //

        ds.addVertex('B');    //

        ds.addVertex('C');    //2

        ds.addVertex('D');    //

        ds.addVertex('E');    //

        ds.addEdge(0, 1);    //A-B

        ds.addEdge(0, 3);    //A-D

        ds.addEdge(1, 4);    //B-E

        ds.addEdge(3, 4);    //D-E

        ds.addEdge(4, 2);    //E-C

        ds.printMatrix();

        ds.DFS();

    }

测试结果：

10001

00001

10001

01110

A    B    E    C    D

巴特西

数据结构Java版之深度优先-图（十二）

最新文章

热门文章