首页 > 其他 > 详细

[从今天开始修炼数据结构]图结构的五种物理存储方式、深度优先搜索的递归和非递归写法、广度优先搜索

时间:2019-12-16 20:05:24      阅读:93      评论:0      收藏:0      [点我收藏+]

我们之前介绍了线性关系的线性表,层次关系的树形结构,下面我们来介绍结点之间关系任意的结构,图。
一、相关概念

  1,图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

  2,各种图定义

   若两顶点之间的边没有方向,则称这条边为无向边Edge,用无序偶对(v1,v2)来表示。如果图中任意两个顶点之间的边都是无向边,则称该图为无向图

   若从顶点v1到v2的边有方向,则称这条边为有向边,也称为弧(Arc),表示为有序偶<v1,v2>,称v1为弧尾,v2为弧头。若图中任意两个顶点之间的边都是有向边,则称该图为有向图

  注意无向边用(),有向边用<>

  图按照边或弧的多少分为稀疏图和稠密图,但划分边界比较模糊。任意两个顶点之间都存在边叫完全图,有向的叫有向完全图。若无重复边或顶点回到自身的边的叫做简单图

  图上边或弧带则称为

  3,图的顶点与边之间的关系

  图中顶点之间有邻接点Adjacent的概念,v和v‘相邻接,边(v,v‘)依附于顶点v和v’,或者说边(v,v‘)与顶点v和v’相关联。顶点的Degree是与v相关联的边的数目,记作TD(v)。

  有向图中有入度ID(v)和出度OD(V)的概念.

  图中的顶点间存在路径则说明是连通的,如果路径最终回到起始点则成为,不重复的路径称为简单路径。顶点不重复出现的回路,叫做简单回路或简单环

  若任意两点之间都是连通的,则成为连通图,有向则是强连通图。图中有子图,若子图极大连通则称该子图为连通分量,有向的则称为强连通分量

  无向图是连通图且n个顶点有n-1条边则叫做生成树。有向图中一顶点入度为0,其他顶点入度为1的叫做有向树,一个有向图可以分解为若干有向树构成的生成森林

二、图的抽象数据类型

  技术分享图片

 

 

 三、图的存储结构

  图结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在内存中的物理位置来表示元素间的关系;而多重链表的方式又有操作的不便,因此对于图来说,它实现物理存储是个难题,下面我们来看前辈们已经提供的五种不同的存储结构

  1,邻接矩阵

  图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。若无向图中存在这条边,或有向图中存在这条弧,则矩阵中的该位置置为1,否则置0.如下

技术分享图片

 

 

 

 

 技术分享图片

 

 技术分享图片

 

   邻接矩阵是如何实现图的创建的呢? 代码如下

/*
顶点的包装类
 */
public class Vertex<T>{
    private T data;
    public Vertex(T data){
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

 

/*
邻接矩阵实现图的创建
 */


public class MGraph<T> {
    private Vertex<T>[] vertexs;
    private int[][] edges;
    private int numVertex;          //顶点的实际数量
    private int maxNumVertex;       //顶点的最大数量
    private int INFINITY = 65535;

    public MGraph(int maxNumVertex){
        this.maxNumVertex = maxNumVertex;
        this.vertexs = (Vertex<T>[]) new Vertex[maxNumVertex];
        this.edges = new int[maxNumVertex][maxNumVertex];
        for (int i = 0; i < numVertex; i++){
            for (int j = 0; j < numVertex; j++){
                edges[i][j] = INFINITY;
            }
        }
        for (int i = 0; i < numVertex; i++) {
            edges[i][i] = 0;
        }
    }

    public int getNumVertex(){
        return numVertex;
    }

    public int getMaxNumVertex(){
        return maxNumVertex;
    }

    public boolean isFull(){
        return numVertex == maxNumVertex;
    }

    public void addVertex(T data){
        if(isFull()){
            throw new RuntimeException("图满了");
        }
        Vertex<T> v = new Vertex<T>(data);
        vertexs[numVertex++] = v;
    }

    /**
     * 删除图中与data相等的顶点
     * @param data 要删除的顶点的data值
     * @return 返回删除了几个顶点
     */
    public int removeVertex(T data){
        int flag = 0;
        for (int i = 0; i < numVertex; i++){
            if (vertexs[i].getData().equals(data)){
                for (int j = i; j < numVertex - 1; j++){
                    vertexs[j] = vertexs[j + 1];
                }
                //删除矩阵的第 i 行
                for (int row = i; row < numVertex - 1; row++){
                    for (int col = 0; col < numVertex; col++){
                        edges[col][row] = edges[col][row + 1];
                    }
                }
                //删除矩阵的第 i 列
                for (int row = 0; row < numVertex; row++){
                    for (int col = i; col < numVertex - 1; col++){
                        edges[col][row] = edges[col + 1][row];
                    }
                }
                numVertex--;
                flag++;
            }
        }
        return flag;
    }

    private int getIndexOfData(T data){
        int i = 0;
        while (!vertexs[i].getData().equals(data)){
            i++;
        }
        return i;
    }

    /**
     * 若为无向图,data的顺序随意;若为有向图,则添加的边是data1指向data2
     * @param data1 弧尾
     * @param data2 弧头
     * @param weight 权值
     */
    public void addEdge(T data1, T data2, int weight){
        int index1 = getIndexOfData(data1);
        int index2 = getIndexOfData(data2);
        edges[index1][index2] = weight;
    }

    public void removeEdge(T data1, T data2){
        int index1 = getIndexOfData(data1);
        int index2 = getIndexOfData(data2);
        edges[index1][index2] = INFINITY;
    }

    public void printMatrix(){
        for (int row = 0; row < numVertex; row++){
            for (int col = 0; col < numVertex; col++){
                System.out.print(edges[row][col] + " ");
            }
            System.out.println();
        }
    }
}

  邻接矩阵可以解决图的物理存储,但我们也发现,对于边相对顶点来说较少的图,这种结构是存在对存储空间的极大浪费的。如何解决呢?看下面

  2,邻接表

  我们在前面提到过,顺序存储结构存在预先分配内存可能造成空间浪费的问题,于是引出了链式存储结构。我们用类似于前面树结构中孩子表示法的方式,数组与链表相结合的存储方法称为邻接表。

  处理方法:顶点用一维数组存储;每个顶点的所有邻接点构成一个线性表,用单链表存储。有向图称为顶点v的边表;无向图称为顶点v作为弧尾的出边表

  技术分享图片

 

 注:若是有向图,邻接表结构是类似的。由于有向图有方向,我们是以顶点为弧尾来存储边表的,这样很容易得到每个顶点的出度。但也有是为了便于确定顶点的入度,我们可以建立一个有向图的逆邻接表,即对每个顶点v1都建立一个链接为v1为弧头的表。

   若是带权值的网图,可以在边表结点的定义中再增加一个weight的数据域,存储权值信息即可。

  下面是邻接表存储图结构的代码实现

public class VertexL<T> {
    private T data;
    private EdgeL firstEdge;

    public VertexL(T data)
    {
        this.data = data;
    }

    public void setFirstEdge(EdgeL e){
        this.firstEdge = e;
    }

    public EdgeL getFirstEdge(){
        return firstEdge;
    }
    public T getData(){
        return data;
    }
}
public class EdgeL {
    private int adjvex; //存储邻接点对应的下标
    private EdgeL nextEdge;  //存储

    public EdgeL(int adjvex){
        this.adjvex = adjvex;
    }

    public EdgeL(int adjvex, EdgeL e){
        this.adjvex = adjvex;
        this.nextEdge = e;
    }

    public EdgeL getNextEdge(){
        return nextEdge;
    }

    public void setNextEdge(EdgeL e){
        this.nextEdge = e;
    }

    public int getAdjvex(){
        return adjvex;
    }
}
/*
    无向图(无权值)的邻接表存储。
 */
public class GraphAdjList <T>{
    private VertexL<T>[] vertexs;
    private int numVertex;
    private int maxNumVertex;

    public GraphAdjList(int maxNumVertex){
        this.maxNumVertex = maxNumVertex;
        this.vertexs =(VertexL<T>[]) new VertexL[maxNumVertex];
        numVertex = 0;
    }

    public boolean isFull(){
        return numVertex == maxNumVertex;
    }

    private int getNumVertex(){
        return numVertex;
    }
    /**
     * 添加顶点
     * @param data
     */
    public void addVertex(T data){
        if (isFull()){
            throw new IndexOutOfBoundsException();
        }
        VertexL<T> v = new VertexL<T>(data);
        vertexs[numVertex++] = v;
    }

    /**
     * 添加边
     * @param data1
     * @param data2
     */
    public void addEdge(T data1, T data2){
        int indexOfData1 = getIndex(data1);
        int indexOfData2 = getIndex(data2);

        if (vertexs[indexOfData1].getFirstEdge() == null){
            vertexs[indexOfData1].setFirstEdge(new EdgeL(indexOfData2));
        }else {
            vertexs[indexOfData1].getFirstEdge().setNextEdge(new EdgeL(indexOfData2, vertexs[indexOfData1].getFirstEdge().getNextEdge()));
        }

        if (vertexs[indexOfData2].getFirstEdge() == null){
            vertexs[indexOfData2].setFirstEdge(new EdgeL(indexOfData1));
        }else {
            vertexs[indexOfData2].getFirstEdge().setNextEdge(new EdgeL(indexOfData1, vertexs[indexOfData1].getFirstEdge().getNextEdge()));
        }
    }


    private int getIndex(T data){
        int i = 0;
        for (; i < numVertex; i++){
            if (data.equals(vertexs[i].getData())){
                break;
            }

        }
        if (!data.equals(vertexs[i].getData()) && i == numVertex){
            throw new NullPointerException();
        }
        return i;
    }

    /**
     * 删除边
     * @param data1
     * @param data2
     */
    public void removeEdge(T data1, T data2){
        int indexOfData1 = getIndex(data1);
        int indexOfData2 = getIndex(data2);

        VertexL v = vertexs[indexOfData1];
        EdgeL e = v.getFirstEdge();
        if (e.getAdjvex() == indexOfData2){
            if (v.getFirstEdge().getNextEdge() == null) {
                v.setFirstEdge(null);
            }else {
                v.setFirstEdge(e.getNextEdge());
            }
        }else {
            while (e.getNextEdge().getAdjvex() != indexOfData2){
                e = e.getNextEdge();
            }
            if (e.getNextEdge().getNextEdge() != null) {
                e.setNextEdge(e.getNextEdge().getNextEdge());
            }else {
                e.setNextEdge(null);
            }
        }
    }

    /**
     * 删除顶点
     * @param data
     */
    public void removeVertex(T data){
        int index = getIndex(data);
        for (int i = 0; i < numVertex; i++){
            if (i == index){
                continue;
            }
            removeEdge(vertexs[i].getData(), data);
        }
        for (int i = index; i < numVertex - 1; i++){
            vertexs[i] = vertexs[i + 1];
        }
    }

 

  3,十字链表

  对于有向图来说,邻接表只关心了出度问题,想了解入度就必须遍历整个图才能知道;反之,逆邻接表解决了入度问题,却不了解出度的情况。那么能不能把邻接表和逆邻接表结合一下呢?

  这就是下面要讲的存储方式:十字链表。

  我们既然要结合邻接表和逆邻接表,就要先把顶点域融合一下如下

 技术分享图片 firstin表示入边表表头指针,指向该顶点入边表的第一个结点;  firstout表示出边表表头指针,指向该顶点出边表的第一个结点。

  下面我们来把边表结点结构也融合一下

  技术分享图片其中tailvex是指弧起点在顶点表的下标 ; headvex是指弧终点在顶点表中的下标。   

 

 

  headlink是入边表指针域,指向同一个弧头的弧;taillink是出边表指针域,指向同一个弧尾的弧。 从新的边表结点的域可以看出来,每一个边表结点既承担了作为入边表的职责,也承担了作为出边表结点的职责。

  例如下面这个例子

技术分享图片

 

 

 图中虚线箭头的含义就是此图的逆邻接表的表示。我们可以简单的理解为,比如第一行的边结点,就是表示从0指向3的有向弧,所以它一定是由0直接指向,并且由3虚线指向的。

再如图中唯一连续指向的从V0指向边10,再指向边20,可以发现弧头为0的都在同一列,弧尾同的都在同一行;由于V0有两个入度,所以虚线连续指向两个边结点。

十字链表的好处是因为结合了邻接表和逆邻接表,既容易找到入度,也容易找到出度。除了结构复杂一点,它创建图算法的时间复杂度是和邻接表相同的。因此在有向图中,十字链表是非常好的数据结构。

代码实现如下: 

/*
    十字链表实现的图结构的弧定义
 */
public class EdgeOL {
    private int tail;
    private int head;

    public EdgeOL(int tail, int head) {
        this.tail = tail;
        this.head = head;
    }
}


/*
    十字链表实现的图结构的顶点定义
 */
public class VertexOL<T> {
    private T data;
    private EdgeOL firstIn;
    private EdgeOL firstOut;

    public VertexOL(T data) {
        this.data = data;
    }
}
/*
    图结构的十字链表实现
 */
public class GraphOrthogonalList<T> {
    private VertexOL<T>[] vertexs;
    private int numVertex;
    private int maxNumVertex;

    public GraphOrthogonalList(int maxNumVertex){
        this.maxNumVertex = maxNumVertex;
        vertexs = (VertexOL<T>[])new VertexOL[maxNumVertex];
    }

    public boolean isFull(){
        return numVertex == maxNumVertex;
    }

    /**
     * 添加新顶点
     * @param data 新顶点的数据域
     */
    public void addVertex(T data){
        if (isFull()){
            return;
        }
        VertexOL<T> v = new VertexOL<>(data);
        vertexs[numVertex++] = v;
    }

    public void addEdge(int tail, int head){
        EdgeOL e = new EdgeOL(tail, head);
        //头插法,形成十字链表
        e.setTailLink(vertexs[tail].getFirstOut());
        vertexs[tail].setFirstOut(e);
        e.setHeadLink(vertexs[head].getFirstIn());
        vertexs[head].setFirstIn(e);
    }

    /**
     * 删除一个边结点
     * @param tail
     * @param head
     */
    public void removeEdge(int tail, int head){
        removeFromTailList(tail, head);
        removeFromHeadList(tail, head);
    }

    /**
     * 从邻接表中删除一个边结点
     * @param tail
     * @param head
     */
    private void removeFromTailList(int tail, int head){
        EdgeOL e = vertexs[tail].getFirstOut();
        //从tailLink中删除它
        if (e != null && e.getHeadVex() == head){
            //如果e是第一个但不是最后一个结点,删除它
            if (e.getTailLink() != null){
                vertexs[tail].setFirstOut(e.getTailLink());
            }else {
                //如果e是第一个也是最后一个结点,删除它
                vertexs[tail].setFirstOut(null);
            }
        }else if (e != null){
            //如果e不是第一个结点,那么遍历链表找到要删除的边结点的上一个结点!!
            while (e.getTailLink() != null && e.getTailLink().getHeadVex() != head){
                e = e.getTailLink();
            }
            if (e.getHeadVex() != head){
                //throw new NullPointerException();
                //这里不能抛异常,因为后面要遍历删除边,抛异常会使程序终止
                return;
            }else {
                e.setTailLink(e.getTailLink().getTailLink());
            }
        }
    }

    /**
     * 从逆邻接表中删除一个边结点
     * @param tail
     * @param head
     */
    private void removeFromHeadList(int tail, int head){
        //从headLink中删除它
        EdgeOL e = vertexs[head].getFirstOut();
        if (e != null && e.getTailVex() == tail){
            //如果e1是第一个但不是最后一个结点,删除它
            if (e.getHeadLink() != null){
                vertexs[head].setFirstIn(e.getHeadLink());
            }else {
                //如果e1是第一个也是最后一个结点,删除它
                vertexs[head].setFirstIn(null);
            }
        }else if (e != null){
            //如果e1不是第一个结点,那么遍历链表找到要删除的边结点的上一个结点!!

            while (e.getHeadLink() != null
                    && e.getHeadLink().getTailVex() != tail){
                e = e.getHeadLink();
            }
            if (e.getTailVex() != tail){
                //throw new NullPointerException();
                return;
            }else {
                e.setHeadLink(e.getHeadLink().getHeadLink());
            }
        }
    }

    /**
     * 删除index角标的顶点
     * @param index
     */
    public void removeVertex(int index){
        if (index >= numVertex){
            throw new NullPointerException();
        }

        //删除与该顶点有关的所有边
        for (int i = numVertex - 1; i > 0; i--){
            removeEdge(index, i);
            removeEdge(i, index);
        }

        //删除该结点
        for (int i = index; i < numVertex - 1; i++){
            vertexs[i] = vertexs[i + 1];
        }
        numVertex--;
    }
}

  4,邻接多重表

  上面的三种结构看似已经解决了所有问题,但在编写代码的时候才能体会到,插入顶点,插入边时非常方便,但删除时很麻烦。如何解决呢? 有时又要对已访问的边做标记,又怎么做呢? 

  下面我们来看面向无向图的邻接多重表。

   我们把邻接表中的边表结点的结构进行改造如下

   技术分享图片

 

   其中ivex和jvex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边,jlink指向依附顶点jvex的下一条边。这就是邻接多重表。

      注意:ilink指向的结点的jvex和它本身的ivex值相同

   下面举例

技术分享图片

 

 若要删除左图(v0 , v2)这条边,仅需让6 , 9这两个链接改为^即可,删除方便了很多。

上面这种方法是《大话数据结构》中的画法,它 “貌似” 限制了ivex和jvex的顺序,使得在代码实现上难以思考。我找到了下面这个视频,是一个很好的邻接多重表的解释,(咖喱英语警告)。它没有限制ivex必须指向相同的jvex,没有限制ivex和jvex的顺序,也没有限制数组中的顶点结点只能指向一个边结点,更灵活,更好理解,代码也更容易实现。

https://www.youtube.com/watch?v=f2z1n6atBsc

  下面是视频中画法的代码实现。

/*
邻接多重表的顶点定义
 */
public class VertexAM<T> {
    private T data;
    private EdgeAM firstEdge;

    public VertexAM(T data){
        this.data = data;
    }
    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public EdgeAM getFirstEdge() {
        return firstEdge;
    }

    public void setFirstEdge(EdgeAM firstEdge) {
        this.firstEdge = firstEdge;
    }
}
/*
邻接多重表的边结点定义
 */
public class EdgeAM {
    private int ivex;
    private int jvex;
    private EdgeAM ilink;
    private EdgeAM jlink;

    public EdgeAM(int ivex, int jvex){
        this.ivex = ivex;
        this.jvex = jvex;
    }

    public int getIvex() {
        return ivex;
    }

    public void setIvex(int ivex) {
        this.ivex = ivex;
    }

    public int getJvex() {
        return jvex;
    }

    public void setJvex(int jvex) {
        this.jvex = jvex;
    }

    public EdgeAM getIlink() {
        return ilink;
    }

    public void setIlink(EdgeAM ilink) {
        this.ilink = ilink;
    }

    public EdgeAM getJlink() {
        return jlink;
    }

    public void setJlink(EdgeAM jlink) {
        this.jlink = jlink;
    }
}
/*
邻接多重表的代码实现
 */
public class GraphAM <T>{
    private VertexAM<T>[] vertexs;
    private int numVertex;
    private int maxNumVertex;

    public GraphAM(int maxNumVertex){
        this.maxNumVertex = maxNumVertex;
        this.vertexs = (VertexAM<T>[])new VertexAM[maxNumVertex];
        numVertex = 0;
    }

    public boolean isFull(){
        return numVertex == maxNumVertex;
    }

    public void addVertex(T data){
        if (isFull()){
            return;
        }
        vertexs[numVertex++] = new VertexAM<>(data);
    }

    /**
     * 将新结点连在iLink链表的链尾和jLink链表的链尾
     * @param ivex
     * @param jvex
     */
    public void addEdge(int ivex, int jvex){
        EdgeAM e = new EdgeAM(ivex, jvex);
        if (vertexs[ivex].getFirstEdge() == null) {
            vertexs[ivex].setFirstEdge(e);
        } else if (vertexs[jvex].getFirstEdge() == null){
            vertexs[jvex].setFirstEdge(e);
        } else {
            EdgeAM ptr = vertexs[ivex].getFirstEdge();
            while (ptr.getIlink() != null){
                ptr = ptr.getIlink();
            }
            ptr.setIlink(e);

            ptr = vertexs[jvex].getFirstEdge();
            while (ptr.getJlink() != null){
                ptr = ptr.getJlink();
            }
            ptr.setJlink(e);
        }
    }

    /**
     * 删除边,如果边结点直连顶点结点,则直接删除;若不直连,先找到边结点的上一个边结点,然后将上一个边结点的link域置空。
     * @param ivex
     * @param jvex
     */
    public void removeEdge(int ivex, int jvex) {
        if (vertexs[ivex].getFirstEdge() != null && vertexs[ivex].getFirstEdge().getJvex() == jvex) {
            vertexs[ivex].setFirstEdge(null);
        } else if (vertexs[jvex].getFirstEdge() != null && vertexs[jvex].getFirstEdge().getIvex() == ivex) {
            vertexs[jvex].setFirstEdge(null);
        } else {
            removeFromLink(ivex, jvex);

            removeFromLink(jvex, ivex);
        }
    }

    private void removeFromLink(int ivex, int jvex){
        EdgeAM ptr = vertexs[ivex].getFirstEdge();
        if (ptr == null){
            return;
        }
        while (ptr.getIlink() != null && ptr.getIlink().getJvex() != jvex) {
            ptr = ptr.getIlink();
        }
        if (ptr.getIlink() == null){
            return;
        }else {
            ptr.setIlink(null);
        }
    }

    /**
     * 先删除与本顶点相连的所有边,然后再删除顶点
     * @param index
     */
    public void removeVertex(int index){
        for (int i = 0; i < numVertex; i++){
            removeEdge(i, index);
            removeEdge(index, i);
        }

        for (int i = index; i < numVertex - 1; i++){
            vertexs[i] = vertexs[i + 1];
        }
        numVertex--;
    }
}

  5,边集数组

   边集数组由两个一维数组构成,一个存储顶点的信息;另一个存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成。

    边集数组的效率并不高,它适合对边依次进行处理的操作,而不适合对顶点进行相关的操作。边集数组的应用将在后面的克鲁斯卡尔(Kruskal)算法中有介绍。

技术分享图片

 

 四、图的遍历

  图的遍历是和树的遍历类似,我们希望从图中某一顶点出发仿遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traversing Graph)

  1,深度优先遍历(Depth_First_Search DFS) 

  技术分享图片

 

 我们以上图为例,假设我们从A出发,只要没碰到访问过的结点,就一直往右手边走,先到B,再到C,再到D,E,F,此时再往右走就碰到A了,所以我们往左边走,到G,往右为D,D访问过了,所以往左走到H,这时H的左右D和E都已经访问过了,到了死胡同。

但是此时图中还有I结点没有访问过,所以我们从H沿原路后退经过G,F,E,D,C,此时从C往左手边走访问了I。这就是深度优先遍历的思路:从图中某个顶点v出发,只要它存在没有被访问过的邻接点,就进入该邻接点,然后以该点进行深度优先遍历。

仔细观察大家会感受到,深度优先遍历其实很像栈/递归。所以想到用递归来实现深度优先遍历。注意实现过程中不必拘泥于上面解释图片时的一直往右走这个说法,因为图的存储只有画出图片对人的观察来说才有左和右的意义。代码如下

    /*
        对于使用邻接矩阵存储的图的深度优先遍历
    */

//标识结点是否被访问过 private boolean[] visited; //深度优先遍历操作入口 public void DFSTraverse(){ this.visited = new boolean[getNumVertex()]; for (boolean bool : visited){ bool = false; } //若该顶点没被访问过,则从该顶点为起点深度优先遍历,若为连通图,则只会执行一次DFS for (int i = 0; i < getNumVertex(); i++){ DFS(i); } } //深度优先遍历算法 private void DFS(int i) { visited[i] = true; System.out.println(vertexs[i].getData()); for (int j = 0; j < numVertex; j++){ if ( !visited[j] && (edges[i][j] != 0 || edges[i][j] != INFINITY)){ DFS(j); } } }

  

    //标识结点是否被访问过
    private boolean[] visited;
    //深度优先遍历操作入口
    public void DFSTraverse(){
        this.visited = new boolean[getNumVertex()];
        for (boolean bool : visited){
            bool = false;
        }
        //若该顶点没被访问过,则从该顶点为起点深度优先遍历,若为连通图,则只会执行一次DFS
        for (int i = 0; i < getNumVertex(); i++){
            if (!visited[i]) {
                DFS(i);
            }
        }
    }
    //深度优先遍历算法
    private void DFS(int i) {
        visited[i] = true;
        System.out.println(vertexs[i].getData());
        if (!(vertexs[i].getFirstEdge() == null)) {
            EdgeL e = vertexs[i].getFirstEdge();  //取到邻接表的第一个元素
            while (e != null) {      //邻接表不为空
                if (!visited[e.getAdjvex()]) {     //如果该元素没有被访问过,则以该元素为起点再次进行深度优先遍历;如果访问过,则取到邻接表的下一个结点(可以理解为往右走走不通,变成往左走)
                    DFS(e.getAdjvex());
                }
                e = e.getNextEdge();
            }
        }
    }

 

上面是两种存储方式的深度优先遍历的递归写法,我们可以看出邻接矩阵的DFS的时间复杂度是O(n2)而邻接表的DFS是O(n+e)所以当点多边少的稀疏图时,邻接表结构在深度优先遍历上的时间效率大大提高。

  众所周知,递归算法在数据量过大时容易引起栈溢出等问题,所以下面我们来看一下DFS的非递归写法

  如下是邻接矩阵,DFS非递归写法(ArrayStack是我在前面关于栈的博客中实现的一个简单链栈demo)

    //标识结点是否被访问过
    private boolean[] visited_2;

    /**
     * 利用栈来实现,如果该顶点被访问,则压栈;
     * 当走到死胡同,查询栈顶元素是否有其他未被访问的邻接点,如果有,则访问它,并压栈,如果没有,则将栈顶元素弹栈,直到栈为空。
     */
    public void DFSTraverse_2(){
        this.visited = new boolean[numVertex];
        for (int i = 0; i < numVertex; i++){
            visited[i] = false;
        }

        ArrayStack<Integer> s = new ArrayStack<Integer>();
        int i = 0;
        visit(i);
        s.push(i);
        while (!s.isEmpty()){
            int j = 0;
            int top = s.getTop();
            for (; j < numVertex; j++){
                if ( !visited[j] && (edges[top][j] != 0 || edges[top][j] != INFINITY)){
                    visit(j);
                    visited[j] = true;
                    s.push(j);
                    break;
                }
            }
            if (j == numVertex){
                s.pop();
            }
        }
    }

    private void visit(int i){
        System.out.println(vertexs[i].getData());
        visited[i] = true;
    }

  以下是邻接表DFS非递归写法。

   //标识结点是否被访问过
    private boolean[] visited_2;
    //深度优先遍历操作入口
    public void DFSTraverse_2(){
        this.visited = new boolean[getNumVertex()];
        for (int i = 0; i < numVertex; i++){
            visited[i] = false;
        }
        for (int i = 0; i < numVertex; i++) {
            ArrayStack<Integer> s = new ArrayStack<>();
            visit(i);
            s.push(i);
            while (!s.isEmpty()) {
                int topIndex = s.getTopData();

                EdgeL p = vertexs[topIndex].getFirstEdge();
                //遍历邻接表,直到找到邻接表中没有被访问过的结点
                while (p != null) {
                    if (!visited[p.getAdjvex()]) {
                        visit(p.getAdjvex());
                        s.push(p.getAdjvex());
                    } else if(p.getNextEdge() != null && visited[p.getNextEdge().getAdjvex()] == false){
                        p = p.getNextEdge();
                    }
                }
                if (p == null) {
                    s.pop();
                }
            }
        }
    }

    public void visit(int i){
        System.out.println(vertexs[i].getData());
        visited[i] = true;
    }

  2,广度优先遍历(Breadth_First_Search  BFS) 

  如果说图的深度优先遍历类似于树的前序遍历,那么广度优先遍历就类似于树的层序遍历

 技术分享图片

 

 我们把上左图调整一下位置,形成有层间关系的类似树的结构。然后以队列的形式,当一个元素被遍历,则将它出队的同时,将它的未被遍历的邻接结点入队,直到队列中的全部元素都被遍历。

代码如下

/*
  邻接矩阵存储的图的广度优先遍历
*/ 
    public void BFSTraverse(){
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        this.visited = new boolean[getNumVertex()];
        for (int i = 0; i < numVertex; i++){
            visited[i] = false;
        }
        for(int i = 0; i < numVertex; i++){
            if (!visited[i]) {
                queue.add(i);
            }
            while (!queue.isEmpty()){
                int row = queue.remove();
                visit(row);
                for (int j = 0; j < numVertex; j++){
                    //如果存在这条边,且这条边的邻接点没有被访问过,且邻接点不在队列中,则将该邻接点入队
                    if ((edges[row][j] != 0 && edges[row][j] != INFINITY) && !visited[j] && !queue.contains(j)){
                        queue.add(j);
                    }
                }
            }
        }
    }

    private void visit(int i){
        System.out.println(vertexs[i].getData());
        visited[i] = true;
    }
}
/*
    邻接表存储的图的广度优先遍历
*/
    public void BFSTraverse(){
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        this.visited = new boolean[getNumVertex()];
        for (int i = 0; i < getNumVertex(); i++){
            visited[i] = false;
        }

        for (int i = 0; i < getNumVertex(); i++){
            if (!visited[i]) {
                queue.add(i);
            }
            while (!queue.isEmpty()){
                int node = queue.remove();
                visit(node);
                EdgeL e = vertexs[node].getFirstEdge();
                if (e != null && !queue.contains(e.getAdjvex()) && !visited[e.getAdjvex()]) {
                    queue.add(e.getAdjvex());

                    while (e != null && e.getNextEdge() != null && !queue.contains(e.getAdjvex()) && !visited[e.getAdjvex()]) {
                        queue.add(e.getAdjvex());
                        e = e.getNextEdge();
                    }
                }
            }
        }
    }

    public void visit(int i){
        System.out.println(vertexs[i].getData());
        visited[i] = true;
    }

对比发现,DFS和BFS在时间复杂度上是一样的,仅仅是访问次序不同。深度优先更适合目标明确,以找到目标为目的的情况;广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

下面应该是最小生成树这一部分,但是研究了一天,发现大话数据结构这本书的图这部分写的实在是烂,难以下咽,所以后面将再起一篇博客,来记录后续部分,将会以Sedgewick版《算法》的风格来叙述。如果有人看到博客对后续有期待,请等我几天。

[从今天开始修炼数据结构]图结构的五种物理存储方式、深度优先搜索的递归和非递归写法、广度优先搜索

原文:https://www.cnblogs.com/Joey777210/p/12009087.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!