Soy un TA para un curso introductorio de CS, y una pregunta que se hizo a los estudiantes fue cómo usar BFS para determinar el diámetro de un gráfico no ponderado y no dirigido. Se les dijo a los estudiantes que no serían calificados por eficiencia, por lo que la respuesta esperada era un algoritmo de fuerza bruta donde ejecutaban BFS de cada nodo a cada otro nodo y devolvían la distancia máxima de estas carreras de BFS. A los estudiantes se les proporcionó un método BFS al que podían hacer referencia en su pseudocódigo que tomaba como entrada un nodo y devolvía dos asignaciones: una de cada nodo en el gráfico a su distancia desde el nodo de inicio (llamado distmap), y una de cada nodo a su 'nodo principal' a lo largo de la ruta más corta desde el nodo de entrada (llamado mapa principal).

Una estudiante escribió el siguiente algoritmo:

  1. Elija un nodo arbitrario del gráfico y ejecute BFS desde él.
  2. Cree una temperatura establecida de todos los nodos que no sean valores en el mapa principal (es decir, las hojas del árbol BFS)
  3. Inicialice max_dist a 0
  4. Para cada nodo n en Temp:
    1. Ejecute BFS desde n
    2. Para cada valor d en distmap:
      1. SI d> max_dist ENTONCES establece max_dist igual a d
  5. RETURN max_dist

Creo que esta respuesta es correcta, pero no puedo demostrarlo. ¿Alguien puede probar por qué funciona o proporcionar un contraejemplo?

2
Zach B 2 jun. 2017 a las 18:51

2 respuestas

La mejor respuesta

Quizás un contraejemplo un poco más simple:

enter image description here

Está bastante claro que la distancia máxima en este gráfico es entre los nodos verdes (4), pero si inicia su BFS desde el nodo rojo, Temp consistirá solo en los dos nodos azules, lo que da un " diámetro "de 3.

2
Vincent van der Weele 2 jun. 2017 a las 20:53

Suponiendo que no estar en un mapa principal significa ser una hoja en un árbol BFS, el algoritmo está equivocado.

Deje que el gráfico tenga 10 vértices y los siguientes bordes no dirigidos:

0 1
0 4
1 2
1 3
2 3
2 6
2 7
3 8
4 5
4 6
5 9
6 7
6 8
7 8
7 9

Uno de los árboles BFS válidos (con raíz 0) es:

0 1
1 2
1 3
2 7
3 8
0 4
4 6
4 5
5 9

Las hojas son 6, 7, 8, 9, por lo que esta solución devuelve 3. Eso está mal. La respuesta es 4 (es la distancia entre 3 y 5).

Tomar todos los nodos más lejanos tampoco funciona para esta prueba.

En lugar de pedirle a alguien que encuentre un contraejemplo, puede hacerlo generando millones de pequeños casos de prueba aleatorios y verificando si la solución produce una respuesta correcta. Aquí está el código que usé para generar este caso (no se ve muy bien, pero hace el trabajo):

pair<vector<int>, set<int>> bfs(int st, const vector<vector<int>>& g) {
    int n = g.size();
    vector<int> d(n, n);
    d[st] = 0;
    queue<int> q;
    q.push(st);
    set<int> parents;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int to : g[v])
            if (d[to] > d[v] + 1) {
                d[to] = d[v] + 1;
                q.push(to);
                parents.insert(v);
            }
    }
    return {d, parents};
}

int get_max_dist(const vector<vector<int>>& g) {
    int res = 0;
    for (int i = 0; i < (int)g.size(); i++) {
        auto cur = bfs(i, g).first;
        for (int x : cur)
            cerr << x << " ";
        cerr << endl;
        res = max(res, *max_element(cur.begin(), cur.end()));
    }
    cerr << endl;
    return res;
}

int get_max_dist_weird(const vector<vector<int>>& g) {
    auto p = bfs(0, g);
    vector<int> cand;
    int n = g.size();
    for (int i = 0; i < n; i++)
        if (!p.second.count(i))
            cand.push_back(i);
    int res = 0;
    for (int i : cand) {
        auto cur = bfs(i, g).first;
        res = max(res, *max_element(cur.begin(), cur.end()));
    }
    return res;
}

vector<vector<int>> rand_graph(int n) {
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (rand() & 1) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
    return g;
}

int main() {
    for (int i = 1;; i++) {
        int n = 10;
        auto g = rand_graph(n);
        int correct = get_max_dist(g);
        int got = get_max_dist_weird(g);
        if (correct != got) {
            cerr << correct << " " << got << endl;
            for (int v = 0; v < n; v++)
                for (int j : g[v])
                    if (v < j)
                        cerr << v << " " << j << endl;
        }
        assert (get_max_dist_weird(g) == get_max_dist(g));
        if (i % 1000 == 0)
            cerr << i << endl;
    }
}

Claro, no puede probar que el algoritmo sea correcto de esta manera, pero es muy probable que encuentre un contraejemplo si no lo es.

2
kraskevich 2 jun. 2017 a las 18:59