> For the complete documentation index, see [llms.txt](https://lewiszlw.gitbook.io/notebooks/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lewiszlw.gitbook.io/notebooks/blogs/history/shen-du-you-xian-sou-suo-he-guang-du-you-xian-sou-suo.md).

# 深度优先搜索和广度优先搜索

图是一种复杂的非线性数据结构，深度优先搜索（Depth First Search）和广度优先搜索（Breadth First Search）是遍历图的两种最常见算法。

## 图的表示与相关概念

### 图的相关概念

**图的二元组定义：** 图 G 由两个集合 V 和 E 组成，记为： G=(V, E) 。其中： V 是顶点的有穷非空集合, E 是 V 中顶点偶对(称为边)的有穷集。

通常，也将图 G 的顶点集和边集分别记为 V(G) 和 E(G) 。 E(G) 可以是空集。若 E(G) 为空，则图 G 只有顶点而没有边。

**有向图**： 若图 G 中的每条边都是有方向的，则称 G 为有向图 (Digraph) 。 **无向图**： 若图 G 中的每条边都是没有方向的，则称 G 为无向图 (Undigraph) 。 **完全图**：若无向图中的每个顶点之间存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。 **稠密图**： 当一个图接近完全图时，则称它为稠密图。 **稀疏图**：当一个图含有较少边数（即e<< n(n-1)）时，则称它为稀疏图。 **简单图**：图中每条边的顶点均不相同。

**邻接点**： 有向图：如果 \<u, v>∈ E, 则称v为u的邻接点，u为v的逆邻接点。边\<u, v>与顶点u和v相关联，从u出发的边称为u的*出边*或*邻接边*，而指向顶点u的边称为u的*入边*或*逆邻接边*。 无向图：如果(u, v)∈ E, 则称u与v互为邻接点。

**顶点的度、入度与出度**： 依附与某顶点v的边数称为**度**； 在有向图中，顶点v的**入度**： 指以顶点为终点的边的数目。**出度**：指以顶点起始点的边的数目； 无向图中**出度入度相等**。

**通路或路径**：由m+1个顶点与m条边交替构成的一个序列。 **环路**：如路径的第一个顶点和最后一个顶点相同，称之为环路。 **可达分量**：有向图中，若顶点s到v有一条通路，称v是从s可达的。对于s，从s可达的所有顶点的集合叫可达分量。 **连通图**：*无向图中*，若一个顶点到另一个顶点有路径，则称这2个顶点是连通的。如果图中任意2顶点都是连通的，则称该图是连通图。 **非连通图**：无向图中，存在两个顶点之间是不连通的，则该无向图称为非连通图。 **强连通图**：针对*有向图*而言的，如果有向图中任意两个顶点之间是连通的（注意方向问题，A—>B，成立，但B—>A不一定成立），则该有向图称为强连通图 **非强连通图**：如果有向图中存在两个顶点之间是不连通的，则该有向图称为非强连通图 **权**：与图中边有关的实数。 **带权图**或**网**：边上具有权值的图。

**最小生成树**： 从图中的不同顶点或从同一顶点按不同的优先搜素过程可以得到不同的树。而对于一个连通网（连通带权图）来说，生成的树不同，每棵树的代价（树中每条边上权值之和）也可能不同，代价最小的生成树为图的最小生成树。

常用的表示图的方法有两种：

1. 邻接矩阵
2. 邻接表

### 图的存储——邻接矩阵

采用2个数组来表示图：一个是存储所有顶点信息的一维数组，一个是存储图中顶点之间关联关系的二维数组。这个二维数组称为邻接矩阵。

![深度优先搜索和广度优先搜索1](http://ofolh8dcq.bkt.clouddn.com/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%E5%92%8C%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A21) **邻接矩阵的特性**：

1. 对于无向图a，邻接矩阵是一个对称矩阵。第i行(i列)非∞元素的个数正好是第i个顶点的度。
2. 对于有向图b，第i行非∞元素的个数是第i个顶点的出度、i列非∞元素的个数是第i个顶点的入度。

**邻接矩阵的不足**： 1、由n个顶点构成的图中最多可以有$n^2$条边，但大多数情况下，边的数目远远达不到这个量级，邻接矩阵中大多数单元都是闲置的。 2、矩阵结构是静态的，大小Ｎ需要预先估计，然后创建Ｎ\*Ｎ的矩阵，而图的规模往往是动态变化的，Ｎ估计过大会造成空间浪费，过小则造成空间不够用。

**实现源码**：

```java
public class MatrixGraph {
	
	private char[] mVexs;		//顶点集合
	private int[][] mMatrix;	//邻接矩阵

	/**
	 * 创建图
	 * @param vexs	顶点数组
	 * @param edges	边数组
	 * 示例：char[] vexs={'a','b','c','d'};
	 * char[][] edges={{'a','b'}, {'a','c'}, {'b','d'}};
	 */
	public MatrixGraph(char[] vexs, char[][] edges){
		//获取顶点数和边数
		int vlen=vexs.length;
		int elen=edges.length;
		
		//初始化顶点
		mVexs=new char[vlen];
		for(int i=0;i<vlen;i++){
			mVexs[i]=vexs[i];
		}
		
		//初始化边
		mMatrix=new int[vlen][vlen];
		for(int i=0;i<elen;i++){
			//边的起始顶点和结束顶点
			int pStart=getPosition(edges[i][0]);
			int pEnd=getPosition(edges[i][1]);
			
			//无向图
			mMatrix[pStart][pEnd]=1;
			mMatrix[pEnd][pStart]=1;

			/*有向图
			*mMatrix[pStart][pEnd]=1;
			*/
		}
	}
	
	//获取顶点顺序位置
	private int getPosition(char ch){
		for(int i=0;i<mVexs.length;i++){
			if(mVexs[i]==ch){
				return i;
			}
		}
		return -1;
	}
}
```

### 图的存储——邻接表

邻接表是图的一种动态的链式存储方法，类似于树的孩子链表表示法。

![深度优先搜索和广度优先搜索2](http://ofolh8dcq.bkt.clouddn.com/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%E5%92%8C%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A22) **邻接表的特性**：

1. 在无向图中，顶点ｖ的度为ｖ的邻接表中表表节点的个数。
2. 在有向图中，顶点ｖ的邻接表中边表的节点个数仅为ｖ的出度。入度需要遍历这个邻接表或者从逆邻接表中获取。

**邻接表的不足**： 判断2个顶点直接是否有边需要搜素2个顶点对应的邻接表。不如邻接矩阵方便。

**实现源码**：

```java
public class ListGraph {
	//邻接表中表对应的链表的顶点
	private class ENode{
		int ivex;		//该边所指向顶点的位置
		ENode nextEdge;		//指向下一条边的指针
		public ENode(int ivex){
			this.ivex=ivex;
		}
		public ENode(int ivex, ENode nextEdge){
			this.ivex=ivex;
			this.nextEdge=nextEdge;
		}
	}
	
	//邻接表中表的顶点
	private class VNode{
		char data;		//顶点信息
		ENode firstEdge;	//指向第一条依附该顶点的边
		public VNode(char data){
			this.data=data;
		}
		public VNode(char data, ENode firstEdge){
			this.data=data;
			this.firstEdge=firstEdge;
		}
	}
	
	//顶点数组
	private VNode[] mVexs;	
	
	/**
	 * 创建图
	 * @param vexs	顶点数组
	 * @param edges	边数组
	 * 示例：char[] vexs={'a','b','c','d'};
	 * char[][] edges={{'a','b'}, {'a','c'}, {'b','d'}};
	 */
	public ListGraph(char[] vexs, char[][] edges){
		//获取顶点数和边数
		int vlen=vexs.length;
		int elen=edges.length;
		
		//初始化顶点
		mVexs=new VNode[vlen];
		for(int i=0;i<mVexs.length;i++){
			mVexs[i]=new VNode(vexs[i]);
		}
		
		//初始化边
		for(int i=0;i<elen;i++){
			//边的起始顶点和结束顶点
			int pStart=getPosition(edges[i][0]);
			int pEnd=getPosition(edges[i][1]);
			
			//无向图
			ENode node1=new ENode(pEnd);
			if(mVexs[pStart].firstEdge==null){
				mVexs[pStart].firstEdge=node1;
			}else {
				linkLast(mVexs[pStart].firstEdge, node1);
			}
			ENode node2=new ENode(pStart);
			if(mVexs[pEnd].firstEdge==null){
				mVexs[pEnd].firstEdge=node2;
			}else {
				linkLast(mVexs[pEnd].firstEdge, node2);
			}
			
			/*有向图
			*ENode node=new ENode(pEnd);
			*if(mVexs[pStart].firstEdge==null){
			*	mVexs[pStart].firstEdge=node;
			*}else {
			*	linkLast(mVexs[pStart].firstEdge, node);
			*}
			*/
		}
	}
	
	//获取顶点顺序位置
	private int getPosition(char ch){
		for(int i=0;i<mVexs.length;i++){
			if(mVexs[i].data==ch){
				return i;
			}
		}
		return -1;
	}
	
	//将node结点链接到list的最后
	private void linkLast(ENode list, ENode node){
		ENode p=list;
		while(p.nextEdge!=null){
			p=p.nextEdge;
		}
		p.nextEdge=node;
	}
}
```

## 深度优先搜索

### 基本思想

假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

### 实现源码

**邻接矩阵**：

```java
public class MatrixGraph {
	
	private char[] mVexs;
	private int[][] mMatrix;

	public MatrixGraph(char[] vexs, char[][] edges){
		int vlen=vexs.length;
		int elen=edges.length;
		
		mVexs=new char[vlen];
		for(int i=0;i<vlen;i++){
			mVexs[i]=vexs[i];
		}
		
		mMatrix=new int[vlen][vlen];
		for(int i=0;i<elen;i++){
			int pStart=getPosition(edges[i][0]);
			int pEnd=getPosition(edges[i][1]);
			
			//无向图
			mMatrix[pStart][pEnd]=1;
			mMatrix[pEnd][pStart]=1;

			/*有向图
			*mMatrix[pStart][pEnd]=1;
			*/
		}
	}
	
	private int getPosition(char ch){
		for(int i=0;i<mVexs.length;i++){
			if(mVexs[i]==ch){
				return i;
			}
		}
		return -1;
	}

	//返回顶点v的第一个邻接顶点的索引
	private int firstVertex(int v){
		if(v<0||v>(mVexs.length-1)){
			return -1;
		}
		for(int i=0;i<mVexs.length;i++){
			if(mMatrix[v][i]==1){
				return i;
			}
		}
		return -1;
	}
	
	//返回顶点v相对于w的下一个邻接顶点的索引
	private int nextVertex(int v, int w){
		if(v<0||v>(mVexs.length-1)||w<0||w>(mVexs.length-1)){
			return -1;
		}
		for(int i=w+1;i<mVexs.length;i++){
			if(mMatrix[v][i]==1){
				return i;
			}
		}
		return -1;
	}
	
	public void dfs(){
		//初始化所有顶点都没有被访问
		boolean[] visited=new boolean[mVexs.length];
		for(int i=0;i<mVexs.length;i++){
			visited[i]=false;
		}
		for(int i=0;i<mVexs.length;i++){
			if(!visited[i]){
				dfs(i, visited);
			}
		}
		System.out.println();
	}
	
	private void dfs(int i, boolean[] visited){
		visited[i]=true;
		System.out.printf("%c", mVexs[i]);
		for(int w=firstVertex(i);w>=0;w=nextVertex(i, w)){
			if(!visited[w]){
				dfs(w, visited);
			}
		}
	}
}
```

**邻接表**：

```java
public class ListGraph {
	private class ENode{
		int ivex;
		ENode nextEdge;
		public ENode(int ivex){
			this.ivex=ivex;
		}
		public ENode(int ivex, ENode nextEdge){
			this.ivex=ivex;
			this.nextEdge=nextEdge;
		}
	}
	
	private class VNode{
		char data;
		ENode firstEdge;
		public VNode(char data){
			this.data=data;
		}
		public VNode(char data, ENode firstEdge){
			this.data=data;
			this.firstEdge=firstEdge;
		}
	}
	
	private VNode[] mVexs;	
	
	public ListGraph(char[] vexs, char[][] edges){
		int vlen=vexs.length;
		int elen=edges.length;
		
		mVexs=new VNode[vlen];
		for(int i=0;i<mVexs.length;i++){
			mVexs[i]=new VNode(vexs[i]);
		}
		
		for(int i=0;i<elen;i++){
			int pStart=getPosition(edges[i][0]);
			int pEnd=getPosition(edges[i][1]);
			
			//无向图
			ENode node1=new ENode(pEnd);
			if(mVexs[pStart].firstEdge==null){
				mVexs[pStart].firstEdge=node1;
			}else {
				linkLast(mVexs[pStart].firstEdge, node1);
			}
			ENode node2=new ENode(pStart);
			if(mVexs[pEnd].firstEdge==null){
				mVexs[pEnd].firstEdge=node2;
			}else {
				linkLast(mVexs[pEnd].firstEdge, node2);
			}
			
			/*有向图
			*ENode node=new ENode(pEnd);
			*if(mVexs[pStart].firstEdge==null){
			*	mVexs[pStart].firstEdge=node;
			*}else {
			*	linkLast(mVexs[pStart].firstEdge, node);
			*}
			*/
		}
	}
	
	//获取顶点顺序位置
	private int getPosition(char ch){
		for(int i=0;i<mVexs.length;i++){
			if(mVexs[i].data==ch){
				return i;
			}
		}
		return -1;
	}
	
	//将node结点链接到list的最后
	private void linkLast(ENode list, ENode node){
		ENode p=list;
		while(p.nextEdge!=null){
			p=p.nextEdge;
		}
		p.nextEdge=node;
	}
	
    /*
     * 深度优先搜索遍历图的递归实现
     */
    private void dfs(int i, boolean[] visited) {
        ENode node;

        visited[i] = true;
        System.out.printf("%c ", mVexs[i].data);
        node = mVexs[i].firstEdge;
        while (node != null) {
            if (!visited[node.ivex])
                dfs(node.ivex, visited);
            node = node.nextEdge;
        }
    }

    /*
     * 深度优先搜索遍历图
     */
    public void dfs() {
        boolean[] visited = new boolean[mVexs.length];       // 顶点访问标记

        // 初始化所有顶点都没有被访问
        for (int i = 0; i < mVexs.length; i++)
            visited[i] = false;

        for (int i = 0; i < mVexs.length; i++) {
            if (!visited[i])
                dfs(i, visited);
        }
        System.out.printf("\n");
    }
}
```

## 广度优先搜索

### 基本思想

从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2...的顶点。

### 实现源码

**邻接矩阵**：

```java
public class MatrixGraph {
	
	private char[] mVexs;
	private int[][] mMatrix;

	public MatrixGraph(char[] vexs, char[][] edges){
		int vlen=vexs.length;
		int elen=edges.length;
		
		mVexs=new char[vlen];
		for(int i=0;i<vlen;i++){
			mVexs[i]=vexs[i];
		}
		
		mMatrix=new int[vlen][vlen];
		for(int i=0;i<elen;i++){
			int pStart=getPosition(edges[i][0]);
			int pEnd=getPosition(edges[i][1]);
			
			//无向图
			mMatrix[pStart][pEnd]=1;
			mMatrix[pEnd][pStart]=1;

			/*有向图
			*mMatrix[pStart][pEnd]=1;
			*/
		}
	}
	
	//获取顶点顺序位置
	private int getPosition(char ch){
		for(int i=0;i<mVexs.length;i++){
			if(mVexs[i]==ch){
				return i;
			}
		}
		return -1;
	}

	//返回顶点v的第一个邻接顶点的索引
	private int firstVertex(int v){
		if(v<0||v>(mVexs.length-1)){
			return -1;
		}
		for(int i=0;i<mVexs.length;i++){
			if(mMatrix[v][i]==1){
				return i;
			}
		}
		return -1;
	}
	
	//返回顶点v相对于w的下一个邻接顶点的索引
	private int nextVertex(int v, int w){
		if(v<0||v>(mVexs.length-1)||w<0||w>(mVexs.length-1)){
			return -1;
		}
		for(int i=w+1;i<mVexs.length;i++){
			if(mMatrix[v][i]==1){
				return i;
			}
		}
		return -1;
	}
	
    /*
     * 广度优先搜索（类似于树的层次遍历）
     */
    public void bfs() {
        int head = 0;
        int rear = 0;
        int[] queue = new int[mVexs.length];            // 辅组队列
        boolean[] visited = new boolean[mVexs.length];  // 顶点访问标记

        for (int i = 0; i < mVexs.length; i++)
            visited[i] = false;

        for (int i = 0; i < mVexs.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                System.out.printf("%c ", mVexs[i]);
                queue[rear++] = i;  // 入队列
            }

            while (head != rear) {
                int j = queue[head++];  // 出队列
                for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) { //k是为访问的邻接顶点
                    if (!visited[k]) {
                        visited[k] = true;
                        System.out.printf("%c ", mVexs[k]);
                        queue[rear++] = k;
                    }
                }
            }
        }
        System.out.printf("\n");
    }
}
```

**邻接表**：

```java
public class ListGraph {
	private class ENode{
		int ivex;
		ENode nextEdge;
		public ENode(int ivex){
			this.ivex=ivex;
		}
		public ENode(int ivex, ENode nextEdge){
			this.ivex=ivex;
			this.nextEdge=nextEdge;
		}
	}
	
	private class VNode{
		char data;
		ENode firstEdge;
		public VNode(char data){
			this.data=data;
		}
		public VNode(char data, ENode firstEdge){
			this.data=data;
			this.firstEdge=firstEdge;
		}
	}
	

	private VNode[] mVexs;	

	public ListGraph(char[] vexs, char[][] edges){
		int vlen=vexs.length;
		int elen=edges.length;
		
		mVexs=new VNode[vlen];
		for(int i=0;i<mVexs.length;i++){
			mVexs[i]=new VNode(vexs[i]);
		}
		
		for(int i=0;i<elen;i++){
			int pStart=getPosition(edges[i][0]);
			int pEnd=getPosition(edges[i][1]);
			
			//无向图
			ENode node1=new ENode(pEnd);
			if(mVexs[pStart].firstEdge==null){
				mVexs[pStart].firstEdge=node1;
			}else {
				linkLast(mVexs[pStart].firstEdge, node1);
			}
			ENode node2=new ENode(pStart);
			if(mVexs[pEnd].firstEdge==null){
				mVexs[pEnd].firstEdge=node2;
			}else {
				linkLast(mVexs[pEnd].firstEdge, node2);
			}
			
			/*有向图
			*ENode node=new ENode(pEnd);
			*if(mVexs[pStart].firstEdge==null){
			*	mVexs[pStart].firstEdge=node;
			*}else {
			*	linkLast(mVexs[pStart].firstEdge, node);
			*}
			*/
		}
	}
	
	//获取顶点顺序位置
	private int getPosition(char ch){
		for(int i=0;i<mVexs.length;i++){
			if(mVexs[i].data==ch){
				return i;
			}
		}
		return -1;
	}
	
	//将node结点链接到list的最后
	private void linkLast(ENode list, ENode node){
		ENode p=list;
		while(p.nextEdge!=null){
			p=p.nextEdge;
		}
		p.nextEdge=node;
	}

    /*
     * 广度优先搜索（类似于树的层次遍历）
     */
    public void bfs() {
        int head = 0;
        int rear = 0;
        int[] queue = new int[mVexs.length];            // 辅组队列
        boolean[] visited = new boolean[mVexs.length];  // 顶点访问标记

        for (int i = 0; i < mVexs.length; i++)
            visited[i] = false;

        for (int i = 0; i < mVexs.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                System.out.printf("%c ", mVexs[i].data);
                queue[rear++] = i;  // 入队列
            }

            while (head != rear) {
                int j = queue[head++];  // 出队列
                ENode node = mVexs[j].firstEdge;
                while (node != null) {
                    int k = node.ivex;
                    if (!visited[k])
                    {
                        visited[k] = true;
                        System.out.printf("%c ", mVexs[k].data);
                        queue[rear++] = k;
                    }
                    node = node.nextEdge;
                }
            }
        }
        System.out.printf("\n");
    }
}
```

***

> [Java数据结构----图的基础知识](http://blog.csdn.net/oChangWen/article/details/50704130) [图的遍历之 深度优先搜索和广度优先搜索](http://www.cnblogs.com/skywang12345/p/3711483.html)