Задача С++. ПОМОЩ!

+1 глас
23 прегледа
попитан 16 май в .NET от weaddams9 (130 точки)
17
Report PostQuote Post



Група: Потребител
Ранг: Новопостъпил

Мнения: 5
Регистриран на: 16.05.18

Статус: (0%) -----

Здравейте хора. Много спешно ми трябва каквато и да е програма на с++, която да сортира граф по метода обхождане в ширина( bfs) . Много ви моля ако можете да помогнете, защото пробвах всичко и не се получава.

1 отговор

+1 глас
отговорени 5 юни от Павката (2,810 точки)
// Program to print BFS traversal from a given

// source vertex. BFS(int s) traverses vertices

// reachable from s.

#include<iostream>

#include <list>

using namespace std;

// This class represents a directed graph using

// adjacency list representation

class Graph

{

    int V;    // No. of vertices

    // Pointer to an array containing adjacency

    // lists

    list<int> *adj;  

public:

    Graph(int V);  // Constructor

    // function to add an edge to graph

    void addEdge(int v, int w);

    // prints BFS traversal from a given source s

    void BFS(int s);

};

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Add w to v’s list.

}

void Graph::BFS(int s)

{

    // Mark all the vertices as not visited

    bool *visited = new bool[V];

    for(int i = 0; i < V; i++)

        visited[i] = false;

    // Create a queue for BFS

    list<int> queue;

    // Mark the current node as visited and enqueue it

    visited[s] = true;

    queue.push_back(s);

    // 'i' will be used to get all adjacent

    // vertices of a vertex

    list<int>::iterator i;

    while(!queue.empty())

    {

        // Dequeue a vertex from queue and print it

        s = queue.front();

        cout << s << " ";

        queue.pop_front();

        // Get all adjacent vertices of the dequeued

        // vertex s. If a adjacent has not been visited,

        // then mark it visited and enqueue it

        for (i = adj[s].begin(); i != adj[s].end(); ++i)

        {

            if (!visited[*i])

            {

                visited[*i] = true;

                queue.push_back(*i);

            }

        }

    }

}

// Driver program to test methods of graph class

int main()

{

    // Create a graph given in the above diagram

    Graph g(4);

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(1, 2);

    g.addEdge(2, 0);

    g.addEdge(2, 3);

    g.addEdge(3, 3);

    cout << "Following is Breadth First Traversal "

         << "(starting from vertex 2) \n";

    g.BFS(2);

    return 0;

}
...