图 DFS BFS

图

  1. 线性表和树两类数据结构，线性表中的元素是“一对一”的关系，树中的元素是“一对多”的关系，本章所述的图结构中的元素则是“多对多”的关系。
  2. 图是一种非线性数据结构，由顶点（vertex）和边（edge）组成，每条边都连接着两个顶点。
  3. 图分为有向图和无向图。 将边带有权值的图称作带权图
  4. 图的表示方法：邻接矩阵 和 邻接表
  5. 邻接矩阵 ：
    图的邻接矩阵存储方式是用两个数组来标示图。一个一维数组存储图顶点的信息，一个二维数组存储图中边或者弧的信息。
    　　设图G有n个顶点，则邻接矩阵是一个nxn的方阵，定义为：
    　　若(vi, vj ) 属于边集， 就是两个顶点之间有邻边， 则 令 对应的二维数组的值为1， arr[i][j] = 1, 若两个顶点之间没有邻边就令其为0
  6. 邻接表：
    只关心存在的边，邻接表由数组加链表组成 ， 由一维数组来存储各个顶点，若另一个顶点与其有邻边，就将此结点所 对应的一维下标链接在此结点的后面 就是每个一维数组元素的后面或许还连接着一个链表。
  7. 完全图，连通图，与强连通图
    完全图可分为有向完全图和无向完全图两种，如果一个图的任意两个结点之间有且只有一条边，则称此图为无向完全图，若任意两个结点之间有且只有方向相反的两条边，则称为有向完全图。

那么连通图与完全图有什么区别呢？连通图是指在无向图中，若图中任意一对结点之间都有路径可达，则称这个无向图是连通图，而强连通图则是对应于有向图来说的，其特点与连通图是一样的。只不过是有向的，所以加了"强"。

连通图与完全图的区别就是，完全图要求任意两点之间有边，而连通图则是要求有路径。边和路径是有区别的。

  1. 结点的度
    对于无向图来说，没有出度入度之分，一个结点的度就是经过这个结点的边的数目(或者是与这个结点相关联的边的数目)，对于有向图来说，出度就是指以这个结点为起始的边的条数（箭头向外），入度则是以这个点为终点的边的条数（箭头向内）。

1. 代码实现无向图

package 图;

import java.util.ArrayList;
import java.util.Arrays;

/*代码实现包含顶点A B C D E的无向图结构：其中AB AC BC BD BE共五条边
 * 思路：
 * 1.使用ArrayList 来存储顶点String
 * 2.保存邻接矩阵使用二维数组 int [][] edges 表示边的关系 值为1表示两个顶点之间可以直接连接，否则为0
 * */
public class Test {
	
	private ArrayList vertexList;//存储顶点集合
	private int[][] edges; //保存邻接矩阵
	private int numEdges;  //边的数目
	

	public static void main(String[] args) {
		int n = 5;//顶点的个数
		String Vertexs[] = {"A","B","C","D","E"};//顶点的数据
		//创建图对象
		Test graph  = new Test(n);
		//循环将顶点的数据添加到 存储顶点集合中
		for(String vertex : Vertexs) {
			graph.inserVertex(vertex);
		}
		//添加边 AB AC BC BD BE共五条边
		graph.inserEdges(0, 1, 1);
		graph.inserEdges(0, 2, 1);
		graph.inserEdges(1, 2, 1);
		graph.inserEdges(1, 3, 1);
		graph.inserEdges(1, 4, 1);
		
		//显示图的邻接矩阵
		graph.showGraph();
/*输出结果：
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]*/
	}
	
	//构造器  完成初始化
	public Test(int n) {//n为顶点的个数
		
		vertexList = new ArrayList(n);
		edges = new int[n][n];
		numEdges = 0;		
	}
	
	//插入顶点
	public void inserVertex(String vertex) {
		vertexList.add(vertex);
	}
	
	//添加边
	/**
	 * @param v1   顶点1在ArrayList中所对应的下标
	 * @param v2   顶点2在ArrayList中所对应的下标
	 * @param weight    顶点1和顶点2之间的边所对应的权值
	 */
	public void inserEdges(int v1, int v2,int weight) {
		edges[v1][v2] = weight;
		edges[v2][v1] = weight;
		numEdges++;
	}
	
	//返回结点的个数
	public int getNumVertex() {
		return vertexList.size();
	}
	
	//返回边的个数
	public int getNumEdges() {
		return numEdges;
	}
	
	//返回结点i(下标）所对应的数据（存放的对应于下标的顶点的值）
	public String getValue(int i) {
		return vertexList.get(i);
	}
	
	//返回下标v1 v2所对应的顶点邻边的权值
	public int getWeight(int v1, int v2) {
		return edges[v1][v2];
	}
	
	//显示图的邻接矩阵
	public void showGraph() {
		for(int[] link : edges) {//对于二维数组的组成元素 是一维数组
			System.out.println(Arrays.toString(link));
//使用System.out.println(数组命名称)得到的结果是地址。
//如果想直接把数组中的内容打印出来,直接调用Arrays类中的toString()方法就可以完成。Arrays.toString(参数)
/*Arrays是一个工具类，toString()是方法。
基本都是静态方法，不用使用new创建对象调用，直接使用类名.方法名即可调用即可*/
		}
	}
}

2. 图的遍历(所谓遍历，即是对结点的访问)

1. 深度优先 dfs 优先往纵向挖掘深入

深度优先遍历，从初始访问结点出发，我们知道初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点。总结起来可以这样说：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。

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

具体算法表述如下：
访问初始结点v，并标记结点v为已访问。
查找结点v的第一个邻接结点w。
若w存在，则继续执行4，否则算法结束。
若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
查找结点v的w邻接结点的下一个邻接结点，转到步骤3。

package 图;

import java.util.ArrayList;
import java.util.Arrays;

/*代码实现包含顶点A B C D E的无向图结构：其中AB AC BC BD BE共五条边
 * 思路：
 * 1.使用ArrayList 来存储顶点String
 * 2.保存邻接矩阵使用二维数组 int [][] edges 表示边的关系 值为1表示两个顶点之间可以直接连接，否则为0
 * 3.
 * */
public class Test {
	
	private ArrayList vertexList;//存储顶点集合
	private int[][] edges; //保存邻接矩阵
	private int numEdges;  //边的数目	
	private boolean[] isVisited;//定义数组boolean[],记录某个结点是否被访问
	
	
	public static void main(String[] args) {
		int n = 5;//顶点的个数
		String Vertexs[] = {"A","B","C","D","E"};//顶点的数据
		//创建图对象
		Test graph  = new Test(n);
		//循环将顶点的数据添加到 存储顶点集合中
		for(String vertex : Vertexs) {
			graph.inserVertex(vertex);
		}
		//添加边 AB AC BC BD BE共五条边
		graph.inserEdges(0, 1, 1);
		graph.inserEdges(0, 2, 1);
		graph.inserEdges(1, 2, 1);
		graph.inserEdges(1, 3, 1);
		graph.inserEdges(1, 4, 1);
		
		//显示图的邻接矩阵
		graph.showGraph();
		
		//深度优先遍历
		System.out.println("深度优先遍历:");
		graph.dfs();
/*输出结果：
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
深度优先遍历:
ABCDE*/
	}
	
	//得到第一个邻接结点的下标
	public int getFistIndex(int index) {
		for(int j=0; j0) { //edges[index][j]>0 说明下标为index的下一个邻接结点是存在的 若存在，就返回下一个邻接结点对应的下标
				return j;
			}
		}
		return -1;
		
	}
	
	//根据前一个邻接结点的下标来获取下一个邻接结点
	public int getNext(int v1,int v2) {
		for(int j=v2+1;j0) {
				return j;
			}
		}
		return -1;
	}
	
	
	//深度优先遍历算法
	 
	/**
	 * @param isVisited   判断结点v是否已经访问
	 * @param i         访问初始结点v的下标，第一次就是0
	 */
	public void dfs(boolean[] isVisited,int i) {
		//首先访问该结点，输出
		System.out.print(getValue(i));//返回结点i(下标）所对应的数据
		//将该结点设置为已经访问过
		isVisited[i] = true;
		//就应该以当前被访问过的结点作为初始结点，找它的第一个邻接点
		int w = getFistIndex(i);
		//若w存在，就去访问w结点，先判断是否已经访问，若已经访问过，就回溯；若没有就将w再作为初始结点，找它的第一个邻接点，依次往下寻找，因此此处使用递归
		
		while(w!=-1) {//w存在
			if(!isVisited[w]) {//未被访问过
				dfs(isVisited, w);
			}
			else {//若已经访问过,就应该回溯，去找结点v的邻接结点的下一个邻接结点，注意：是结点v的另一个的下一个邻接结点，算是与w同层
				w = getNext(i, w);
			}
		}
	}
	
	
	//对dfs进行重载：遍历所有的结点，并进行dfs 比如初始结点是下标为0的结点，从它开始dfs,一直纵向走到没有邻接结点； 那还有另外与下标为0的结点同层的结点，还会有另一个纵向分支
	public void dfs() {
		//遍历所有的结点，并进行dfs(回溯)
		for(int i=0;i(n);
		edges = new int[n][n];
		numEdges = 0;	
		isVisited = new boolean[n];
	}
	
	//插入顶点
	public void inserVertex(String vertex) {
		vertexList.add(vertex);
	}
	
	//添加边
	/**
	 * @param v1   顶点1在ArrayList中所对应的下标
	 * @param v2   顶点2在ArrayList中所对应的下标
	 * @param weight    顶点1和顶点2之间的边所对应的权值
	 */
	public void inserEdges(int v1, int v2,int weight) {
		edges[v1][v2] = weight;
		edges[v2][v1] = weight;
		numEdges++;
	}
	
	//返回结点的个数
	public int getNumVertex() {
		return vertexList.size();
	}
	
	//返回边的个数
	public int getNumEdges() {
		return numEdges;
	}
	
	//返回结点i(下标）所对应的数据（存放的对应于下标的顶点的值）
	public String getValue(int i) {
		return vertexList.get(i);
	}
	
	//返回下标v1 v2所对应的顶点邻边的权值
	public int getWeight(int v1, int v2) {
		return edges[v1][v2];
	}
	
	//显示图的邻接矩阵
	public void showGraph() {
		for(int[] link : edges) {//对于二维数组的组成元素 是一维数组
			System.out.println(Arrays.toString(link));
//使用System.out.println(数组命名称)得到的结果是地址。
//如果想直接把数组中的内容打印出来,直接调用Arrays类中的toString()方法就可以完成。Arrays.toString(参数)
/*Arrays是一个工具类，toString()是方法。
基本都是静态方法，不用使用new创建对象调用，直接使用类名.方法名即可调用即可*/
		}
	}
}

2. 广度优先搜索遍历 bfs 对一个结点的所有邻接结点进行横向访问(分层访问)

广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。

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

需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。（先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问）

算法：

  1. 访问初始结点v并标记结点v已经访问
  2. 结点v入队列
  3. 当队列非空时，继续执行，否则算法结束（指的是对结点v的访问结束）
  4. 出队列。取得头结点u
  5. 查找结点u的第一个邻接结点w
  6. 若结点u的邻接结点w不存在，则转到3继续执行，否则循环执行以下三个步骤
    （1）若结点w尚未被访问，则访问结点w并标记为已访问
    （2）结点w入队列
    （3）查找结点u的继邻接结点w后的下一个邻接结点w，转到步骤6
package 图;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/* 算法：
1. 访问初始结点v并标记结点v已经访问
2. 结点v入队列
3. 当队列非空时，继续执行，否则算法结束（指的是对结点v的访问结束）
4. 出队列。取得头结点u
5. 查找结点u的第一个邻接结点w
6. 若结点u的邻接结点w不存在，则转到3继续执行，否则循环执行以下三个步骤
 （1）若结点w尚未被访问，则访问结点w并标记为已访问
 （2）结点w入队列
 （3）查找结点u的继邻接结点w后的下一个邻接结点w，转到步骤6
 * 
 * 总思路：先将一个结点的bfs遍历完，然后再用for循环，把所有结点进行bfs*/
public class BFS {

	private ArrayList vertexList;// 存储顶点集合
	private int[][] edges; // 保存邻接矩阵
	private int numEdges; // 边的数目
	private boolean[] isVisited;// 定义数组boolean[],记录某个结点是否被访问

	public static void main(String[] args) {
		int n = 5;// 顶点的个数
		String Vertexs[] = { "A", "B", "C", "D", "E" };// 顶点的数据
		// 创建图对象
		BFS graph = new BFS(n);
		// 循环将顶点的数据添加到 存储顶点集合中
		for (String vertex : Vertexs) {
			graph.inserVertex(vertex);
		}
		// 添加边 AB AC BC BD BE共五条边
		graph.inserEdges(0, 1, 1);
		graph.inserEdges(0, 2, 1);
		graph.inserEdges(1, 2, 1);
		graph.inserEdges(1, 3, 1);
		graph.inserEdges(1, 4, 1);

		// 显示图的邻接矩阵
		graph.showGraph();
		System.out.println("广度优先搜索：");
		graph.bfs();
	}
/*
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
广度优先搜索：
ABCDE*/
	// 得到第一个邻接结点的下标
	public int getFistIndex(int index) {
		for (int j = 0; j < vertexList.size(); j++) {
			if (edges[index][j] > 0) { // edges[index][j]>0 说明下标为index的下一个邻接结点是存在的 若存在，就返回下一个邻接结点对应的下标
				return j;
			}
		}
		return -1;

	}

	// 根据前一个邻接结点的下标来获取下一个邻接结点
	public int getNext(int v1, int v2) {
		for (int j = v2 + 1; j < vertexList.size(); j++) {
			if (edges[v1][j] > 0) {
				return j;
			}
		}
		return -1;
	}

	// 对一个结点进行bfs遍历

	/**
	 * @param isVisited 判断此结点是否被访问
	 * @param i         此结点对应的下标
	 */
	private void bfs(boolean[] isVisited, int i) {
		int u; // 表述队列的头结点对应 的下标u
		int w; // 表述邻接结点对应的下标w
		// 队列 使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
		LinkedList linkedList = new LinkedList<>();
		// 访问此结点
		System.out.print(getValue(i));
		// 标记为已经访问
		isVisited[i] = true;
		// 将此结点加入队列 队列:加的时候从尾部加 取时从头部取
		linkedList.addLast(i);
		// 当队列非空时， 出队列。取得头结点u的下标
		while (!linkedList.isEmpty()) {
			u = (Integer) linkedList.removeFirst();// 自动拆箱
			// 查找结点u的第一个邻接结点w
			w = getFistIndex(u);
//			 若结点u的邻接结点w存在
			while (w != -1) {
//				 （1）若结点w尚未被访问，则访问结点w并标记为已访问  （2）结点w入队列
				if (!isVisited[w]) {
					System.out.print(getValue(w));
					isVisited[w] = true;
					linkedList.addLast(w);
				}
				// 若结点w已经被访问，查找结点u的继邻接结点w后的下一个邻接结点w，以u为前驱点找
				w = getNext(u, w);

			}
		}
	}

	// 遍历所有的结点，都bfs
	public void bfs() {
		for (int i = 0; i < getNumVertex(); i++) {
			if (!isVisited[i]) {
				bfs(isVisited, i);
			}
		}
	}

	// 构造器 完成初始化
	public BFS(int n) {// n为顶点的个数

		vertexList = new ArrayList(n);
		edges = new int[n][n];
		numEdges = 0;
		isVisited = new boolean[n];
	}

	// 插入顶点
	public void inserVertex(String vertex) {
		vertexList.add(vertex);
	}

	// 添加边
	/**
	 * @param v1     顶点1在ArrayList中所对应的下标
	 * @param v2     顶点2在ArrayList中所对应的下标
	 * @param weight 顶点1和顶点2之间的边所对应的权值
	 */
	public void inserEdges(int v1, int v2, int weight) {
		edges[v1][v2] = weight;
		edges[v2][v1] = weight;
		numEdges++;
	}

	// 返回结点的个数
	public int getNumVertex() {
		return vertexList.size();
	}

	// 返回边的个数
	public int getNumEdges() {
		return numEdges;
	}

	// 返回结点i(下标）所对应的数据（存放的对应于下标的顶点的值）
	public String getValue(int i) {
		return vertexList.get(i);
	}

	// 返回下标v1 v2所对应的顶点邻边的权值
	public int getWeight(int v1, int v2) {
		return edges[v1][v2];
	}

	// 显示图的邻接矩阵
	public void showGraph() {
		for (int[] link : edges) {// 对于二维数组的组成元素 是一维数组
			System.out.println(Arrays.toString(link));
//使用System.out.println(数组命名称)得到的结果是地址。
//如果想直接把数组中的内容打印出来,直接调用Arrays类中的toString()方法就可以完成。Arrays.toString(参数)
			/*
			 * Arrays是一个工具类，toString()是方法。 基本都是静态方法，不用使用new创建对象调用，直接使用类名.方法名即可调用即可
			 */
		}
	}

}

						  
					  
						
							


						

							
							
			java数据结构							
						



						

						
						


						

						
					
					

					
					

						
相关

						

				
						
			

																
								

										
再谈Java数据结构—分析底层实现与应用注意事项

									
									

								 

        

								

							
							
            
            
            
                                    
           
  			
						

					

					
				

				

														
					
					

					
									

					
									   
标签

										

										
    
										

									

										
										

									

					

					
				


			
		
		
		
			


						





	

	
一品网 冀ICP备14022925号-6