Блог

При обходе неориентированного графа с использованием поиска в ширину, который не имеет параллельных ребер и самоциклов, существует вершина x со смежной вершиной y. При обработке вершины «x» он видит, что y уже обнаружен / посещен и имеет родителя / первооткрывателя, который не является x и

• случай 1) y обрабатывается
• случай 2) y не обрабатывается

Каковы примеры ситуаций для каждого из них? и говорит ли это что-нибудь о взаимосвязи между x и y?

где обработанная вершина означает, что мы уже обошли все ее смежные вершины, обнаруженный узел означает, что y был обнаружен по крайней мере одним из его родителей. Родительский означает вершину, которая первой обнаружила данную вершину.

Вот мое мышление. Очевидно, что y имеет по крайней мере 2 родительские вершины. «x» и, по крайней мере, еще один родитель «a».

  a    x
    /
    y
 

и поскольку y уже обнаружен в обоих случаях (1) и (2)

• (случай 1) возможно, потому что «a» и «x» (родители y) не имеют общих предков или x должно быть обработано до y . Правильно??? или нет?
• (случай 2) «a» и «x» должны иметь общего предка, поэтому x обрабатывается перед y. Правильно???? или нет?

Просто для справки, вот реализация bfs (см. Функцию traverse() ), включая main(), основанную на книге Стивена Скиена «Руководство по разработке алгоритмов»

 #include <iostream>
#include <queue>




class edgeNode {
private:
    int y{ -1 };
    edgeNode* next{ nullptr };
public:
    edgeNode(int _y, edgeNode* _node) : y{ _y }, next{ _node }{}
    edgeNode(int _y) : y{ _y }, next(nullptr){}
    edgeNode() : y(0), next(nullptr) {}
    int getY() const { return y; }
    edgeNode* getNext() const { return next; }
    void print() { std::cout << y; }
};



class bGraph {
static  const int MAX_VERTICES = 100;
    edgeNode* edges[MAX_VERTICES];
    bool discovered[MAX_VERTICES];
    bool processed[MAX_VERTICES];
    int parents[MAX_VERTICES];

public:
    bGraph() {
        for (int i = 0; i < MAX_VERTICES; i  ) {
            edges[i] = nullptr;
            discovered[i] = false;
            processed[i] = false;
            parents[i] = -1;    
        }
    }
    edgeNode* getEdge(int v) { return edges[v]; }
    void addEdge(int x, int y, bool directed) {
        edgeNode* node = new edgeNode(y, edges[x]);
        edges[x] = node;        
        if (!directed) {
            addEdge(y, x, true);
        }
    }

void traverse(int v) {
            int x, y;           
            std::queue<int> fifo;
            fifo.push(v);
            while (!fifo.empty()) {             
                x = fifo.front();
                fifo.pop();
                edgeNode* node = getEdge(x);
                if (node == nullptr)
                    continue;
                discovered[x] = true;
                std::cout << "nStart Processing Vertex: " << x << std::endl; 
                while (node != nullptr) {
                    y = node->getY();
                    if (!processed[y] ) {
                        //process edge 
                        std::cout << "(" << x << "," << y << ") ";
                    }
                    if (!discovered[y]) {
                        fifo.push(y);
                        parents[y] = x;
                        discovered[y] = true;
                    }                   
                    node = node->getNext();
                }
                processed[x] = true;
            std::cout << "nDone Processing Vertex: " << x << std::endl; 
            }
        }

};
int main()
{
bGraph g;
g.addEdge(1,2, false);
g.addEdge(3,1, false);
g.traverse(1);
    return 0;
}
 

Это BFS. Тот, который ближе, замечается первым.

Случай 1: y обрабатывается: если кратчайший путь от начального узла до x проходит через y .

Отношение: y является предком x .

Случай 2: y не обрабатывается: если кратчайший путь от начального узла до x не проходит y .

Отношение: y не является предком x .

Случай 3: зависит от вашей реализации y , обрабатывается ли она раньше x .

Связь: y может быть или не быть предком x .