数据结构_图以及深度优先遍历（DFS）和广度优先遍历（BFS）

系统管理员 2023-07-12 06:18 20阅读 0赞

### 文章目录 ###

*  图的常用概念
 *  图的表示方式
 *   *  邻接矩阵
     *  邻接表
 *  图的代码实现
 *   *  属性和构造器
     *  插入顶点
     *  插入边
     *  两点之间权值
     *  对应索引的节点
     *  边的总数
     *  邻接矩阵
     *  节点个数
 *  DFS与BFS
 *   *  辅助方法
     *   *  第一个邻接节点
         *  下一个邻接节点
     *  深度优先遍历（DFS）
     *   *  思想
         *  算法步骤
         *  代码实现
     *  广度优先遍历（BFS）
     *   *  思想
         *  算法步骤
         *  代码实现

# 图的常用概念 #

![在这里插入图片描述][20200307161827952.png]

*  顶点
 *  边
 *  路径  
    比如从 D -> C 的路径有：
    
    1.  D->B->C
    2.  D->A->B->C
 *  无向图、有向图：顶点之间有无连接方向
 *  带权图：边带权值的图  
    ![在这里插入图片描述][20200307162019406.png]

# 图的表示方式 #

## 邻接矩阵 ##

![在这里插入图片描述][20200307162235125.png]

## 邻接表 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoaWxsX0x5bg_size_16_color_FFFFFF_t_70]

# 图的代码实现 #

## 属性和构造器 ##

public class Graph {
        
    	private ArrayList<String> vertexList;;
    	private int[][] edges;
    	private int numOfEdges;
    	private boolean[] isVisited;
    
    	/**
    	 * 构造器
    	 * @param n
    	 */
    	public Graph(int n) {
        
    		edges = new int[n][n];
    		vertexList = new ArrayList<String>(n);
    		numOfEdges = 0;
    		isVisited = new boolean[n];
    	}
    }

## 插入顶点 ##

/**
     * 插入节点
     * @param vertex
     */
    public void insertVertex(String vertex) {
        
    	if (vertexList.contains(vertex)) {
        
    		System.out.println("节点已存在");
    		return;
    	}
    	vertexList.add(vertex);
    }

## 插入边 ##

/**
     * 插入边
     * @param v1
     * @param v2
     * @param weight
     */
    public void insertEdge(int v1, int v2, int weight) {
        
    	edges[v1][v2] = weight;
    	edges[v2][v1] = weight;
    	numOfEdges++;
    }

## 两点之间权值 ##

/**
     * 两点之间权值
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1, int v2) {
        
    	return edges[v1][v2];
    }

## 对应索引的节点 ##

/**
     * 获取对应索引的节点
     * @param i
     * @return
     */
    public String getValueByIndex(int i) {
        
    	return vertexList.get(i);
    }

## 边的总数 ##

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

## 邻接矩阵 ##

/**
     * 显示图对应的矩阵
     */
    public void showGraph() {
        
    	for (int[] arr : edges) {
        
    		for (int i : arr) {
        
    			System.out.print(i + " ");
    		}
    		System.out.println();
    	}
    }

## 节点个数 ##

/**
     * 返回节点个数
     * @return
     */
    public int getNumOfVertex() {
        
    	return vertexList.size();
    }

# DFS与BFS #

## 辅助方法 ##

### 第一个邻接节点 ###

/**
     * 返回第一个邻接节点
     * @param index
     * @return
     */
    public int getFirstNeighbor(int index) {
        
    	for (int i = 0; i < vertexList.size(); i++) {
        
    		if (edges[index][i] > 1) {
        
    			return i;
    		}
    	}
    	return -1;
    }

### 下一个邻接节点 ###

/**
     * 返回下一个邻接节点
     * @param index
     * @param first
     * @return
     */
    public int getNextNeighbor(int index, int first) {
        
    	for (int i = first + 1; i < vertexList.size(); i++) {
        
    		if (edges[index][i] > 1) {
        
    			return i;
    		}
    	}
    	return -1;
    }

## 深度优先遍历（DFS） ##

### 思想 ###

1.  从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
2.  访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
3.  深度优先搜索是一个递归的过程

### 算法步骤 ###

1.  访问初始结点，并标记结点为已访问。
2.  查找初始结点的第一个邻接结点。
3.  若邻接结点存在，则继续执行4，否则回到第1步，将从初始节点的下一个结点继续。
4.  若邻接结点未被访问，对邻接结点进行深度优先遍历递归（即把邻接结点当做另一个初始节点，然后进行步骤123）。
5.  查找初始结点的邻接结点的下一个邻接结点，转到步骤3。

### 代码实现 ###

/**
     * 深度优先遍历
     */
    public void dfs() {
        
    	for (int i = 0; i < getNumOfVertex(); i++) {
        
    		if (!isVisited[i]) {
        
    			dfs(isVisited, i);
    		}
    	}
    }
    
    /**
     * 一个节点的深度优先遍历
     * @param isVisited
     * @param index
     */
    private void dfs(boolean[] isVisited, int index) {
        
    	//1. 访问初始结点，并标记结点为已访问。
    	System.out.println(getValueByIndex(index));
    	isVisited[index] = true;
    	//2. 查找初始结点的第一个邻接结点。
    	int neighborVertex = getFirstNeighbor(index);
    	//3. 若邻接结点存在，则继续执行4，
    	//否则回到第1步，将从初始节点的下一个结点继续。
    	while (neighborVertex != -1) {
        
    		//4.若邻接结点未被访问，对邻接结点进行深度优先遍历递归
    		if (!isVisited[neighborVertex ]) {
        
    			dfs(isVisited, neighborVertex );
    		}
    		//5.查找初始结点的邻接结点的下一个邻接结点，转到步骤3。
    		neighborVertex = getNextNeighbor(index, neighborVertex );
    	}
    	//回到第1步，将从初始节点的下一个结点继续。
    	//return;
    }

## 广度优先遍历（BFS） ##

### 思想 ###

类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点

### 算法步骤 ###

1.  访问初始结点并标记结点为已访问。
2.  初始结点入队列
3.  当队列非空时，继续执行，否则算法结束。
4.  出队列，取得队头结点。
5.  查找头结点的第一个邻接结点。
6.  若头结点的邻接结点不存在，则转到步骤3；否则循环执行以下789：
7.  若邻接结点尚未被访问，则访问邻接结点并标记为已访问。
8.  邻接结点入队列
9.  查找头结点的继邻接结点后的下一个邻接结点，转到步骤6。

### 代码实现 ###

/**
     * 广度优先遍历
     */
    public void bfs() {
        
    	for (int i = 0; i < getNumOfVertex(); i++) {
        
    		if (!isVisited[i]) {
        
    			bfs(isVisited, i);
    		}
    	}
    }
    
    /**
     * 一个节点的广度遍历
     * @param isVisited
     * @param i
     */
    private void bfs(boolean[] isVisited, int i) {
        
    	int first;
    	int neighborVertex;
    	LinkedList<Integer> queue = new LinkedList<Integer>();
    	//1. 访问初始结点并标记结点为已访问。
    	System.out.println(getValueByIndex(i));
    	isVisited[i] = true;
    	//2. 初始结点入队列
    	queue.addLast(i);
    	//3. 当队列非空时，继续执行，否则算法结束。
    	while (!queue.isEmpty()) {
        
    		//4. 出队列，取得队头结点。
    		first = queue.removeFirst();
    		//5. 查找头结点的第一个邻接结点。
    		neighborVertex = getFirstNeighbor(first);
    		//6. 若头结点的邻接结点不存在，则转到步骤3；否则循环执行以下789：
    		while (neighborVertex != -1) {
        
    			//7. 若邻接结点尚未被访问，则访问邻接结点并标记为已访问。
    			if (!isVisited[neighborVertex]) {
        
    				System.out.println(getValueByIndex(neighborVertex));
    				isVisited[neighborVertex] = true;
    				//8. 邻接结点入队列 
    				queue.addLast(neighborVertex);
    			}
    			//9. 查找头结点的继邻接结点后的下一个邻接结点，转到步骤6。
    			neighborVertex = getNextNeighbor(i, neighborVertex);
    		}
    	}
    }

[20200307161827952.png]: https://img-blog.csdnimg.cn/20200307161827952.png
[20200307162019406.png]: https://img-blog.csdnimg.cn/20200307162019406.png
[20200307162235125.png]: https://img-blog.csdnimg.cn/20200307162235125.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoaWxsX0x5bg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200307162256553.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoaWxsX0x5bg==,size_16,color_FFFFFF,t_70