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

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

程序员文章站 2022-05-20 19:31:51
...

图的常用概念

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

  • 顶点
  • 路径
    比如从 D -> C 的路径有:
    1. D->B->C
    2. D->A->B->C
  • 无向图、有向图:顶点之间有无连接方向
  • 带权图:边带权值的图
    数据结构_图以及深度优先遍历(DFS)和广度优先遍历(BFS)

图的表示方式

邻接矩阵

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

邻接表

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

图的代码实现

属性和构造器

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);
		}
	}
}
相关标签: 数据结构与算法