Требуется перевести с языка Python на C++

Рейтинг: -6Ответов: 1Опубликовано: 31.07.2023

Алгоритм 1:

def dijkstra(graph, start):
  """
  Args:
    graph: Граф, представленный в виде списка смежности.
    start: Начальная вершина.

  """

  # Создаем словарь расстояний до вершин.
  distances = {}
  for vertex in graph:
    distances[vertex] = float("inf")
  distances[start] = 0

  # Создаем множество посещенных вершин.
  visited = set()

  # Создаем очередь приоритетов для вершин, которые еще не посещены.
  pq = [(0, start)]

  while pq:
    (distance, vertex) = heapq.heappop(pq)
    if vertex in visited:
      continue

    for to in graph[vertex]:
      if distances[to] > distances[vertex] + 1:
        distances[to] = distances[vertex] + 1
        heapq.heappush(pq, (distances[to], to))

    # Отмечаем вершину как посещенную.
    visited.add(vertex)

  return distances

Алгоритм 2:

def count_connected_components(graph):
    num_vertices = len(graph)
    visited = [False] * num_vertices
    num_components = 0

    for vertex in range(num_vertices):
        if not visited[vertex]:
            num_components += 1
            dfs(graph, vertex, visited)

    return num_components
python c#
Источник: Stack Overflow на русском

Ответы

▲ -4Принят

Алгоритм 1

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

typedef pair<int, int> pii;

vector<int> dijkstra(vector<vector<int>> graph, int start)
{
    vector<int> distances(graph.size(), -1);
    distances[start] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(make_pair(0, start));
    while (!pq.empty())
    {
        pii p = pq.top();
        pq.pop();
        int vertex = p.second;
        if (distances[vertex] != -1 && distances[vertex] < p.first)
        {
            continue;
        }
        for (size_t i = 0; i < graph[vertex].size(); i++)
        {
            int neighbor = graph[vertex][i];
            int distance = p.first + 1; // assuming all edges have weight 1
            if (distances[neighbor] == -1 || distance < distances[neighbor])
            {
                distances[neighbor] = distance;
                pq.push(make_pair(distance, neighbor));
            }
        }
    }
    return distances;
}

int main()
{
    vector<vector<int>> graph(5);
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[2].push_back(3);
    graph[3].push_back(4);
    vector<int> distances = dijkstra(graph, 0);
    for (size_t i = 0; i < distances.size(); i++)
    {
        cout << "Distance to vertex " << i << " is " << distances[i] << endl;
    }
    return 0;
}

Алгоритм 2

#include <iostream>
#include <vector>

using namespace std;

void dfs(vector<vector<int>> graph, int vertex, vector<bool> &visited)
{
    visited[vertex] = true;
    for (int i = 0; i < graph[vertex].size(); i++)
    {
        int next_vertex = graph[vertex][i];
        if (!visited[next_vertex])
        {
            dfs(graph, next_vertex, visited);
        }
    }
}

int count_connected_components(vector<vector<int>> graph)
{
    int num_components = 0;
    vector<bool> visited(graph.size(), false);
    for (int i = 0; i < graph.size(); i++)
    {
        if (!visited[i])
        {
            dfs(graph, i, visited);
            num_components++;
        }
    }
    return num_components;
}

int main()
{
    vector<vector<int>> graph = {{1, 2}, {0, 2}, {0, 1}, {3}, {4}, {6}, {5}};
    int num_components = count_connected_components(graph);
    cout << "Number of connected components: " << num_components << endl;
    return 0;
}