欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的遍历,深度优先与广度优先详解

程序员文章站 2022-05-21 23:21:43
...

图的遍历,深度优先与广度优先详解

图采用邻接矩阵实现,深度优先搜索采用栈来实现,广度优先遍历采用队列来实现.附上代码详解.


图的实现

1.邻接矩阵实现

简单来说就是用一个二维数组来存储图之间的联通情况,比如有5个点,就可以用一个 5*5的 矩阵来存储 两点间是否联通.
图的遍历,深度优先与广度优先详解
比如上图 false 表示不连通, true表示连通.

public class Graph {
    private boolean[][] map ;
    private int length;
    public Graph(int length)//生成图
    {
        this.length = length;
        map = new boolean[length][length];
    }
    public void addEdge(int i,int j)//加边
    {
        if (map == null)
        {
            if (i>j)
            {
                map = new boolean[i][i];
                length = i;
            }
            else
            {
                map = new boolean[j][j];
                length = j;
            }
        }
        map[i][j]  = true;
        map[j][i]  = true;
    }

    public void removeEdge(int i,int j)//去边
    {
        if (map == null || j>=length||i>=length)
            return;
        else {
            map[i][j] = false;
            map[j][i] = false;
        }
    }
    public boolean isEdge(int i,int j)//判断是否联通
    {
        if (map==null||i>=length||j>=length)
            return false;
        else
            return true;
    }
}

这个为无向图,若为有向图,则生成的边只有一个就好,即只有A到B.

2.邻接链表实现

采用一个一维链表数组用来存储每个点.若这个节点与其他节点有联通,则与它相连通的子节点构成一个链表.

import java.util.ArrayList;

/**
 * Created by max on 17-5-9.
 */
public class ListGraph {
    ListNode[] listNodes;
    int length ;
    ArrayList<Integer> vertices;

    public ListGraph(int lenght)
    {
        this.length = lenght;
        listNodes = new ListNode[length];
        vertices = new ArrayList<>();
        for (int i=0;i<length;i++)
        {
            listNodes[i] = new ListNode();
            vertices.add(i);
        }
    }
    public void addEdge(int start,int end)
    {
        int i = vertices.indexOf(start);
        int j = vertices.indexOf(end);
        if (j!=-1&&i!=-1)
        {
            listNodes[i].insertAtBeginning(j);
            listNodes[j].insertAtBeginning(i);
        }
    }

}

DFS深度优先搜索

思路是采用栈的用来存储访问的节点,而先进后出的机制刚好满足深度搜索的需求.给每个节点添加一个boolean属性,用于判断是否被访问过.


import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by max on 17-5-9.
 */
public class DFS {
    private class Vertics
    {
        public char label;
        public boolean visited;
        public Vertics(char label)
        {
            this.label  = label;
            visited = false;
        }
    }
    private class Graph
    {
        private boolean[][] map;
        private ArrayList<Vertics> vertices;
        private  int countVertices;
        private Stack<Integer> stack;
        public Graph(int length)
        {
            stack = new Stack<>();
            countVertices = 0;
            vertices = new ArrayList<>();
            map = new boolean[length][length];
        }
        public Graph()
        {
            stack = new Stack<>();
            int length =20;
            countVertices = 0;
            vertices = new ArrayList<>();
            map = new boolean[length][length];
        }

        public void addVertice(char label)
        {
            vertices.add(new Vertics(label));
            countVertices++;
        }

        public void addEdge(int i,int j)
        {
            map[i][j] = true;
            map[j][i] = true;
        }
        public void removeEdge(int i ,int j)
        {
            map[i][j] = false;
            map[j][i] = false;
        }

        public void showLabel(int i)
        {
            System.out.print(" "+vertices.get(i).label);
        }
        public void dfs()
        {
            showLabel(0);
            vertices.get(0).visited = true;
            stack.push(0);
            while(!stack.isEmpty())
            {
                int v =getNextNode(stack.peek());
                if (v==-1)
                {
                    stack.pop();
                }
                else
                {
                    vertices.get(v).visited=true;
                    showLabel(v);
                    stack.push(v);
                }
            }
            for (int i = 0 ;i<countVertices;i++)
                vertices.get(i).visited=false;
        }
        private int getNextNode(int peek) {
            for (int i = 0; i < countVertices; i++)
            {
                if (map[peek][i]==true&&vertices.get(i).visited==false)
                    return i;
            }
            return -1;

        }
    }
}

BFS广度优先搜索

广度优先搜索主要是通过队列的先进先出的机制来实现. 以JAVA中的ArrayQueue实现.

       public void bfs()
        {
            showLabel(0);
            vertices.get(0).visited = false;
            queue.add(0);
            int ans;
            int deal;
            while(!queue.isEmpty())
            {
                deal = (int) queue.remove();
                while ((ans = getNextNode(deal))!=-1)
                {
                    vertices.get(ans).visited=true;
                    showLabel(ans);
                    queue.add(ans);
                }
            }
            for (int i = 0 ;i<countVertices;i++)
                vertices.get(i).visited=false;
        }

以上是笔主自己对 深搜广搜的理解与笔记,欢迎交流撕逼.