изменяет ли DFS и BFS в O (n + m)?

Question

Мы знаем, что есть O(n+m)‌ решение (DFS или BFS) для проверки, если существует путь от s к t в неориентированный граф G с n Вершины и m края ..., которые будут реализованы с помощью списка смежности.

Если я реализую свою программу с помощью Матрицы смещения, будет ли затронута среда выполнения? Это хороший или плохой выбор?

Редактировать: Мне нужно рассчитать сложность времени, таким образом, любую идею?

Answer 1

Предполагая, что вход в код будет n и m (число узлов и число ребер) с последующим m линий типа a b означающий существует ребро между вершиной и вершиной ab. Теперь вы берете матрицу смежности M[][], такую, что M[i][j]=1, если есть ребро между i и j иначе M[i][j]=0 (так как график неориентирован, матрица будет симметричной, поэтому вы можете хранить только половину матрицы, уменьшающей половину матрицы). Теперь вам нужно будет взять матрицу и инициализировать ее до 0 (все ячейки) и при сканировании краев отметьте M[a][b]=M[b][a]=1. Теперь инициализирующая часть - O(n^2). Сканирование и маркировка краев - O(m). Теперь рассмотрим процедуру BFS/DFS. Когда вы находитесь на узле, вы пытаетесь увидеть все его невидимые вершины. Теперь скажите, что мы хотим знать соседей вершин a, вам нужно будет сделать for(int i=0;i<n;i++) if (M[a][i]==1) (при условии индексации на основе 0). Теперь это нужно сделать для каждой вершины, и, следовательно, сложность процедуры становится O(n^2), даже если m < (n*(n-1))/2 (при условии, что простой граф без краев и петель m может не превышать (n*(n-1))/2). Таким образом, общая ваша сложность становится O(n^2). Тогда, каково использование матрицы смежности? хорошо, что DFS/BFS может быть просто частью большого алгоритма, ваш алгоритм может также потребовать, чтобы один из них указывал, существует ли край между узлами a и b, на которых матрица смежности принимает значение O(1) времени. Таким образом, независимо от того, следует ли выбирать список смежности или матрицу смежности, зависит от вашего алгоритма (например, максимальной памяти, которую вы можете взять, сложности времени для таких вещей, как процедура DFS/BFS или ответы на запросы, связаны ли две вершины и т. Д.). Надеюсь, я ответил на ваш запрос.