Vérifiez s'il existe un cycle de longueur 3 dans le graphique qui satisfait la condition donnée

Vérifie dans le graphique une boucle de longueur 3 qui satisfait à la condition donnée, se préparant à parcourir à plusieurs reprises chaque sommet et à examiner ses sommets voisins. Si un sommet a deux voisins trop connectés, il existe un cycle de longueur 3. Cette condition garantit qu’il existe une arête entre deux voisins, formant ainsi un triangle. En filtrant tous les sommets et leurs sommets adjacents, nous identifierons si un tel cycle existe. Si nous constatons qu’un sommet a deux voisins liés, nous pouvons conclure que le graphique montre un cycle de longueur 3 qui satisfait la condition donnée.

Méthode à utiliser

• Méthode de la matrice de contiguïté

• Méthode de liste de contiguïté

Méthode de contiguïté

Pour vérifier s'il existe un cycle de longueur 3 dans le graphique qui satisfait une condition donnée, on peut utiliser la méthode contagieuse. Dans cette approche, nous itérons pour chaque sommet du graphique et vérifions ses sommets adjacents. Pour chaque sommet, nous vérifions si deux de ses sommets voisins sont trop étroitement liés. Si une telle correspondance est trouvée, nous vérifions si les conditions de cette correspondance sont remplies. Si la condition est remplie, cela indique une boucle de longueur 3 qui est sur le point de satisfaire la condition donnée. En examinant tous les sommets du graphique, nous pouvons déterminer si un tel cycle existe.

Algorithme

• Initialisez la variable booléenne nommée "cycleExists" à false.

• Parcourir chaque sommet du graphique :

  • Pour chaque sommet, répétez ses sommets adjacents.

  • Pour chaque sommet adjacent, mettez l'accent sur ses sommets adjacents (sauf le sommet actuel).

  • Si deux sommets adjacents sont liés, passez à l'étape suivante.

• Vérifiez si la combinaison de sommets associés trouvée à l'étape 2c satisfait à la condition.

  • Si la condition est remplie, définissez "cycleExists" sur true et sortez de la boucle.

• Après avoir terminé le cycle, vérifiez la valeur de "cycleExists".

  • Si "cycleExists" est vrai, alors il existe un cycle de longueur 3 dans le graphique qui satisfait à la condition donnée.

  • Si "cycleExists" est faux, aucun cycle de ce type n'existe.

• Résultats de sortie.

• Ce calcul répète les sommets du graphique, analyse leurs sommets adjacents et vérifie si des correspondances de sommets adjacents forment un cycle de longueur 3 qui satisfait à la condition donnée.

  李>

Exemple

#include <iostream>
#include <vector>

using namespace std;

bool checkCycle(vector<vector<int>>& graph, int v, vector<bool>& visited, int parent, int condition) {
    visited[v] = true;

    for (int u : graph[v]) {
        if (!visited[u]) {
            visited[u] = true;

            for (int w : graph[u]) {
                if (visited[w] && w != parent && condition == graph[v][u] + graph[u][w]) {
                    return true;
                }
            }

            visited[u] = false;
        }
    }

    return false;
}

bool hasCycleOfLength3(vector<vector<int>>& graph, int condition) {
    int numVertices = graph.size();
    vector<bool> visited(numVertices, false);

    for (int v = 0; v < numVertices; v++) {
        visited[v] = true;

        for (int u : graph[v]) {
            if (checkCycle(graph, u, visited, v, condition)) {
                return true;
            }
        }

        visited[v] = false;
    }

    return false;
}

int main() {
    int numVertices, numEdges;
    cout << "Enter the number of vertices and edges: ";
    cin >> numVertices >> numEdges;

    vector<vector<int>> graph(numVertices);

    cout << "Enter the connections between vertices (u, v) and their corresponding weights: " << endl;
    for (int i = 0; i < numEdges; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;

        graph[u].push_back(v);
        graph[v].push_back(u);

        // Store the weight/condition between u and v
        graph[u][v] = weight;
        graph[v][u] = weight;
    }

    int condition;
    cout << "Enter the condition to be satisfied: ";
    cin >> condition;

    if (hasCycleOfLength3(graph, condition)) {
        cout << "Cycle of length 3 satisfying the condition exists." << endl;
    } else {
        cout << "Cycle of length 3 satisfying the condition does not exist." << endl;
    }

    return 0;
}

Sortie

Enter the number of vertices and edges:  

Méthode de liste de contiguïté

Les méthodes de liste adjacente peuvent être des structures d'information utilisées pour communiquer avec le diagramme. Dans cette approche, chaque sommet du graphe est associé à une liste contenant tous ses sommets adjacents. Pour vérifier s'il existe un cycle de longueur 3 dans le graphe qui satisfait la condition donnée, nous allons parcourir chaque sommet et ses sommets voisins. Pour chaque sommet adjacent, on vérifie s'il contient un sommet adjacent en commun avec le sommet courant. Si un tel sommet commun existe, alors un anneau de longueur 3 est trouvé. Cette approche garantit une investigation efficace du graphe en stockant des données essentielles sur presque tous les sommets de la liste infectieuse et leurs associations.

Algorithme

• Créez une liste contagieuse qui parle au graphe, où chaque sommet contient une liste de ses sommets voisins.

• Parcourez chaque sommet du graphique.

• Pour chaque sommet, répétez ses sommets adjacents.

• Pour chaque sommet adjacent, mettez l'accent sur ses sommets adjacents (sauf le sommet actuel).

• Vérifiez s'il existe un sommet commun entre le sommet actuel et le sommet adjacent du sommet adjacent.

• Si un sommet commun est trouvé, un anneau de longueur 3 existe. Renvoie vrai.

• Si aucun anneau de longueur 3 n'est trouvé, retournez false.

Exemple

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

bool hasCycleOfLength3(vector<vector<int>>& graph) {
    int n = graph.size();
    
    for (int u = 0; u < n; ++u) {
        unordered_set<int> adjSet(graph[u].begin(), graph[u].end());

        for (int v : graph[u]) {
            for (int w : graph[v]) {
                if (w != u && adjSet.count(w) > 0) {
                    return true; // Cycle of length 3 found
                }
            }
        }
    }

    return false; // No cycle of length 3 found
}

int main() {
    // Create the graph as an adjacency list
    vector<vector<int>> graph = {
        {1, 2},
        {0, 2},
        {0, 1, 3},
        {2, 4},
        {3}
    };

    // Check if a cycle of length 3 exists
    bool cycleExists = hasCycleOfLength3(graph);

    // Print the result
    if (cycleExists) {
        cout << "A cycle of length 3 exists in the graph." << endl;
    } else {
        cout << "No cycle of length 3 exists in the graph." << endl;
    }

    return 0;
}

Sortie

A cycle of length 3 exists in the graph.

Conclusion

Cet article examine les moyens de vérifier s'il existe une boucle de longueur 3 dans un graphique qui satisfait une condition donnée. Il illustre deux approches, en particulier l'approche du cadre contagieux et l'approche de la liste contagieuse. Cet article retrace le processus de calcul et donne des bits de code C pour les deux méthodes. L'approche du réseau contagieux consiste à mettre l'accent sur chaque sommet et ses sommets adjacents pour identifier les cycles de longueur 3 qui satisfont à la condition. La méthode de liste contagieuse exploite les structures d'information qui communiquent avec le graphique et examine les sommets communs entre les sommets adjacents pour déterminer la proximité des cycles.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!