предисловие

В ориентированных и неориентированных графах, еслиНет весов или равные веса между узлами,Такdfs和bfsЧасто появляются в повседневных алгоритмах. Не только это,dfs, bfs могут не только решить задачу теории графов, а также по поиску других вопросовсамый простой(но策略不同)из两种经典算法.

И пять классических алгоритмов回溯算法На самом деле этоdfsтипа. Основы dfs и bfs могут решить большинство задач поиска, но поиск увеличивается нелинейно с увеличением данных, поэтому два алгоритма не подходят для больших данных.

Матрица смежности и список смежности

Матрица смежности:Матрица смежности — это массивное (двумерное) представление графа. Подробнее см. пример ниже. Конечно,Эта ситуация может легко привести к пустой трате места., поэтому многие люди оптимизируют пространство, даже используя список смежности.

Список смежности:Список смежности — это связанный список массивов. Это может сэкономить много места по сравнению с матрицей смежности, но если неориентированный графВсе еще тратит половину места, появляются перекрестные списки, появляются многосвязные списки и т.д. В то же время для правой картыПросто добавьте вес атрибута к узлу!

Поиск в глубину (dfs)

концепция:

Поиск в глубину относится к разновидности графового алгоритма, а английская аббревиатура — DFS, то есть поиск в глубину Процесс кратко описывается как углубление каждого возможного пути ветвления настолько, насколько он не может идти дальше, и каждый узел может только посетить один раз.

Проще говоря, есть предпосылки для завершения dfs.联通点. Одиночный узел dfs сломан, и он хочет найти узел, который к нему подключен. Причина, по которой dfs может быть легче начать с bfs, заключается в том, чтоБольшинство dfs использует рекурсивное направление для завершения dfs,а также很少需要标记.

мы обычно используем邻接表(一维数组套链表a[List])или邻接矩阵(二维数组a[][])Хранит информацию о графике. Иногда в целях оптимизации пространства выбирают十字链表или邻接多重表Это экономит место для хранения, но операция часто усложняется. и вообще графикБольшая потребность в оптимизации алгоритмов проектирования, поэтому в этом примере используется邻接矩阵Заканчивать!

Для процесса dfs его можно грубо рассматривать следующим образом:

Из начальной точки пройдите в одном направлении, остановитесь в этом направлении в конце, а затем идите в другом направлении, пока все операции не будут выполнены и выйдите!
Поиск в глубину выполняется как операция стека.喜新厌旧. Всегда обрабатывать последний добавленный узел, эта рекурсия просто удовлетворяет своей природе, и рекурсивный кодТакже более лаконично писать.
Процесс dfs может бытьОбратитесь к предварительному обходу двоичного дерева., который по сути является dfs.

Для dfs на изображении выше. Его можно представить следующим кодом:

package 图论;
public class dfs {
	static boolean isVisit[];
	public static void main(String[] args) {
		int map[][]=new int[7][7];
		isVisit=new boolean[7];
		map[0][1]=map[1][0]=1;
		map[0][2]=map[2][0]=1;
		map[0][3]=map[3][0]=1;
		
		map[1][4]=map[4][1]=1;
		map[1][5]=map[5][1]=1;
		map[2][6]=map[6][2]=1;
		map[3][6]=map[6][3]=1;
	
		isVisit[0]=true;
		dfs(0,map);//从0开始遍历
	}
	private static void dfs(int index,int map[][]) {
		// TODO Auto-generated method stub
		System.out.println("访问"+(index+1)+"  ");
		for(int i=0;i<map[index].length;i++)//查找联通节点
		{
			if(map[index][i]>0&&isVisit[i]==false)
			{
				isVisit[i]=true;
				dfs(i,map);
			}
		}
		System.out.println((index+1)+"访问结束 ");
	}
}

Примерно последовательный доступ

Ширина (Breadth) первого поиска (bfs)

концепция:

BFS, полное английское название — Breadth First Search. BFS не использует эмпирический алгоритм. С алгоритмической точки зрения все дочерние узлы, возникающие в результате расширения узла, добавляются в очередь в порядке поступления. В общих экспериментах узлы, чьи соседние узлы не были проверены, помещаются в контейнер, называемый открытым (такой как очередь или связанный список), а проверенные узлы помещаются в контейнер, называемый закрытой серединой. (открытый-закрытый стол)

Проще говоря, bfs — это обход очереди в порядке поступления, но в случае распределения этоХод по слоям, вы можете обратиться к обходу бинарного дереваобход по уровням!

Если вы посмотрите на путь,дфс это быстрая бешеная собака, кусается везде. Когда нет пути, обернись, а когда нет пути, беги назад, чтобы идти куда-то еще,А бфс как облако ядовитого газа, медленно расширяется!

Взяв приведенный выше граф в качестве примера, мы используем список смежности для реализации обхода.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class bfs {
	public static void main(String[] args) {
		List<Integer> map[]=new ArrayList[7];
		boolean isVisit[]=new boolean[7];
		for(int i=0;i<map.length;i++)//初始化
		{
			map[i]=new ArrayList<Integer>();
		}
		map[0].add(1);map[0].add(2);map[0].add(3);
		map[1].add(0);map[1].add(4);map[1].add(5);
		map[2].add(0);map[2].add(6);
		map[3].add(0);map[3].add(6);
		map[4].add(1);
		map[5].add(1);
		map[6].add(2);map[6].add(3);
		
		Queue<Integer>q1=new ArrayDeque<Integer>();
		q1.add(0);isVisit[0]=true;
		while (!q1.isEmpty()) {
			int va=q1.poll();
			System.out.println("访问"+(va+1));
			for(int i=0;i<map[va].size();i++)
			{
				int index=map[va].get(i);
				if(!isVisit[index])
				{
					q1.add(index);
					isVisit[index]=true;
				}
			}
		}
	}
}

Резюме и сравнение

Как упоминалось выше, dfs и bfs часто находятся вДва экстремальных спектакля по поиску пути! Конечно, в разных сценариях она может быть разной.

dfs можно использовать в поиске и сканере.Если сканер должен сначала найти разные ссылки, его можно использовать для статистики и т. д. пока в поиске напримерлабиринтМожно использовать dfs, чтобы судитьЕсть ли путь, выходи т.п.
bfs также можно использовать в алгоритмах и поисковых роботах. И bfs отдает приоритет ресурсам вокруг себя. Таким образом, сканер можно использовать для обхода веб-сайта, поиска ценной информации по всему веб-сайту и т. д. Автор использовалCrawler + bfs внедрил шаблоны для загрузки сайтов(17 веб-шаблонов материалов). А в алгоритмев лабиринте или невзвешенном графе,bfs может найти кратчайший путь.

Из вышеизложенного видно, что реализовано хранение матрицы смежности.тратить много места, но бывают ситуации, когда подходит двумерный массив —лабиринт. Мы учимся на собеседованиях, и мы часто сталкиваемся с классами лабиринтов, которые требуют, чтобы bfs нашла кратчайший путь или dfs, чтобы узнать, существует ли он. Или двойные bfs или dfs+bfs и т.д. для решения конкретных задач.

Наконец, я надеюсь, что все могут обратить внимание на мой официальный аккаунт (bigsai), давайте вместе изучать структуры данных и алгоритмы! Ничего страшного, можно пошевелить ручонками и поставить лайк!