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

数据结构之图的广度、深度优先搜索

程序员文章站 2022-05-20 19:07:09
...

数据结构:图的遍历

1.图的搜索方式分为两种:
深度优先搜索(dfs):
     类似于树的先根遍历,每次访问完当前结点后首先访问当前结点的第一个
     邻接点,是一个递归的过程
广度优先搜索(bfs):
	 类似于树的按层次遍历,每次访问完当前结点后继续访问当前结点的所有
	 邻接点,通常与队列配合使用
2.注意事项:
  因 图结构 结点间的关系是多对多的,所以可能存在 回路,所以在遍历时需要
  用数组visited[]记录所访问过的结点,防出现死循环
3.图的遍历(邻接矩阵存储)
    private String[] vexs=new String[] {"A","B","C","D","E"};
	private int[][] g=new int[][] {
		{0,1,0,1,0},{1,0,1,0,1},{0,1,0,1,1},
		{1,0,1,0,0},{0,1,1,0,0}
	};
    private boolean[] visited=new boolean[vexs.length];
    //输出结点并将对应标志设置为已访问
    public void visit(int v) {
		visited[v]=true;
		System.out.println(vexs[v]);
	}
	//深度优先搜索
	public void dfs(int v) {
		visit(v);
		for(int i=0;i<g[v].length;i++) {
			if(g[v][i]==1&&!visited[i])
				dfs(i);
		}
	}
	//广度优先搜索
	public void bfs(int v) {
		Queue<Integer> q=new LinkedList<Integer>();
		visit(v);
		q.add(v);
		while(!q.isEmpty()) {
			int head=q.poll();
			for(int j=0;j<g[head].length;j++) {
				if(g[head][j]==1&&!visited[j]) {
					visit(j);
					q.add(j);
				}
			}
		}
	}
4.小结

邻接矩阵的存储结构:顶点数组+关系矩阵
在遍历过程中,需记录结点访问记录
广度优先搜索时队列中存放的是已访问过的结点
若需经过多次的深度或广度搜索才能访问完所有的顶点,则图是一个非连通图