图的操作

举报
SHQ5785 发表于 2024/06/11 13:43:41 2024/06/11
【摘要】 企业笔试过程中会涉及到数据结构的方方面面,现将有关图的深度优先搜索与广度优先搜索进行整理归纳,方便日后查阅。在已做过的笔试题目中,可用DFS解决的题目有:“地牢逃脱”–网易“遍历最短路径长度”–携程“小青蛙走迷宫”–滴滴三道题目都是DFS的经典应用,主要采用递归+回溯的方式。下面主要讲解一下DFS与BFS的具体实现。 深度优先搜索(DFS) && 广度优先搜索(BFS)package cn....

企业笔试过程中会涉及到数据结构的方方面面,现将有关图的深度优先搜索与广度优先搜索进行整理归纳,方便日后查阅。

在已做过的笔试题目中,可用DFS解决的题目有:

  1. 地牢逃脱”–网易
  2. 遍历最短路径长度”–携程
  3. 小青蛙走迷宫”–滴滴

三道题目都是DFS的经典应用,主要采用递归+回溯的方式。

下面主要讲解一下DFS与BFS的具体实现。

深度优先搜索(DFS) && 广度优先搜索(BFS)

package cn.edu.ujn.graph;
import java.util.ArrayList;
import java.util.LinkedList;
/**
 * @description 邻接矩阵模型类
 * @author SHQ
 * @time 2016.09.12 
 */
public class DFS_BFS {
    private ArrayList<Object> vertexList;// 存储点的链表
    private int[][] edges;		 // 邻接矩阵,用来存储边
    private int numOfEdges;		 // 边的数目
    boolean[] isVisited;		 // 遍历标志位

    public DFS_BFS(int n) {
        //初始化矩阵,二维数组,和边的数目
        edges = new int[n][n];
        vertexList = new ArrayList<Object>(n);
        numOfEdges = 0;
        // 将所有节点访问标志位均置为未访问
        isVisited = new boolean[n];
        for(int i = 0; i < n; i++){
        	isVisited[i] = false;
        }
    }

    // 得到结点的个数
    public int getNumOfVertex() {
        return vertexList.size();
    }

    // 得到边的数目
    public int getNumOfEdges() {
        return numOfEdges;
    }

    // 返回结点i的数据
    public Object getValueByIndex(int i) {
        return vertexList.get(i);
    }

    // 返回v1,v2的权值
    public int getWeight(int v1,int v2) {
        return edges[v1][v2];
    }

    //插入结点
    public void insertVertex(Object vertex) {
        vertexList.add(vertexList.size(),vertex);
    }

    //插入结点
    public void insertEdge(int v1,int v2,int weight) {
        edges[v1][v2]=weight;
        numOfEdges++;
    }

    //删除结点
    public void deleteEdge(int v1,int v2) {
        edges[v1][v2] = 0;
        numOfEdges--;
    }

    // 得到第一个邻接结点的下标
    public int getFirstNeighbor(int index) {
        for(int j = 0; j < vertexList.size(); j++) {
            if (edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    // 根据前一个邻接结点的下标来取得下一个邻接结点
    public int getNextNeighbor(int v1, int v2) {
        for (int j = v2+1; j < vertexList.size(); j++) {
            if (edges[v1][j]>0) {
                return j;
            }
        }
        return -1;
}
    // 私有函数,深度优先遍历
    private void depthFirstSearch(boolean[] isVisited,int  i) {
        // 首先访问该结点,在控制台打印出来
        System.out.print(getValueByIndex(i) + "  ");
        // 置该结点为已访问
        isVisited[i] = true;
        
        int w = getFirstNeighbor(i);
        while (w != -1) {
            if (!isVisited[w]) {
                depthFirstSearch(isVisited,w);
            }
            w = getNextNeighbor(i, w);
        }
    }
    
    // 对外公开函数,深度优先遍历,与其同名私有函数属于方法重载
    public void depthFirstSearch() {
        for(int i = 0; i < getNumOfVertex(); i++) {
            //因为对于非连通图来说,并不是通过一个结点就一定可以遍历所有结点的。
            if (!isVisited[i]) {
                depthFirstSearch(isVisited,i);
            }
        }
}
    /**
     * 私有函数,广度优先遍历
     * 遍历步骤:
     * 	1.访问初始结点v并标记结点v为已访问。
     * 	2.结点v入队列
     * 	3.当队列非空时,继续执行,否则算法结束。
     * 	4.出队列,取得队头结点u。
     * 	5.查找结点u的第一个邻接结点w。
     * 	6.若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:
     * 		1)若结点w尚未被访问,则访问结点w并标记为已访问。
     * 		2)结点w入队列
     * 		3)查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。
     * @param isVisited
     * @param i
     */
    private void broadFirstSearch(boolean[] isVisited, int i) {
        int u, w;
        // 借助辅助队列,记录访问顺序
        LinkedList<Object> queue = new LinkedList<Object>();
        // 访问结点i
        System.out.print(getValueByIndex(i) + "  ");
        isVisited[i] = true;
        // 结点入队列
        queue.addLast(i);
        while (!queue.isEmpty()) {
            u = ((Integer)queue.removeFirst()).intValue();
            w = getFirstNeighbor(u);
            while(w != -1) {
                if(!isVisited[w]) {
                        //访问该结点
                        System.out.print(getValueByIndex(w)+"  ");
                        //标记已被访问
                        isVisited[w] = true;
                        //入队列
                        queue.addLast(w);
                }
                //寻找下一个邻接结点
                w = getNextNeighbor(u, w);
            }
        }
    }
    
    //对外公开函数,广度优先遍历
    public void broadFirstSearch() {
        for(int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]) {
                broadFirstSearch(isVisited, i);
            }
        }
    }
}

Main.java

package cn.edu.ujn.graph;

public class Main {
    public static void main(String args[]) {
        int n = 8, e = 9; 	// 分别代表结点个数和边的数目
        String labels[]={"1","2","3","4","5","6","7","8"};	// 结点的标识
        DFS_BFS graph = new DFS_BFS(n);
        for(String label : labels) {
            graph.insertVertex(label);	// 插入结点
        }
        //插入九条边
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);
        graph.insertEdge(1, 0, 1);
        graph.insertEdge(2, 0, 1);
        graph.insertEdge(3, 1, 1);
        graph.insertEdge(4, 1, 1);
        graph.insertEdge(7, 3, 1);
        graph.insertEdge(7, 4, 1);
        graph.insertEdge(6, 2, 1);
        graph.insertEdge(5, 2, 1);
        graph.insertEdge(6, 5, 1);
        
/*        System.out.println("深度优先搜索序列为:");
        graph.depthFirstSearch();
        System.out.println();*/
        System.out.println("广度优先搜索序列为:");
        graph.broadFirstSearch();
    }
}
【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。