Распечатать список смежности двунаправленного графа

Дан список смежности двунаправленного графа. Задача состоит в том, чтобы скопировать/клонировать список смежности для каждой вершины и вернуть новый список для двунаправленного графа.

An Adjacency List is used for representing graphs. Here, for every vertex in the graph, we have a list of all the other vertices to which the particular vertex has an edge.

Примеры:

Input: N = 5
adj[] = adj[0] = {1, 2}; adj[2] = {0, 3, 4}; adj[3] = {1, 2}; adj[4] = {2};

Output: Node 0 is connected to 1 and 2
Node 1 is connected to 0 and 3
Node 2 is connected to 0,3 and 4
Node 3 is connected to 1 and 2
Node 4 is connected to 2

The example graph

Подход:

The basic Idea to clone adjacency list for each vertex is to create a cloned vector and a visited array and check whether the node is visited or not.

• Сначала создайте вектор (скажем, clone ) размера N и массив посещений [] размера N , чтобы проверить, посещается ли конкретный элемент или нет.
• Проверьте, посещен ли узел или нет:
  • Если нет, то вызовите функцию, чтобы пометить непосещенный узел как присутствующий.
• Создайте два вектора adj[] и clone[] , где в adj[] хранится список, а в clone[] будут храниться непомеченные узлы.
• Пометить каждый узел как посещенный с помощью Visit[node] = 1.
• Затем просмотрите список смежности и проверьте непосещенные узлы, чтобы добавить ребра в двунаправленный граф.
  • Вставьте узлы и ребра в список клонов

Ниже приведена реализация вышеупомянутой идеи:

Временная сложность: O ( V + E ), где V — количество вершин, а E — количество ребер графа.
Вспомогательное пространство: O (V + E)

Статьи по Теме:

• Введение в графики — учебные пособия по структуре данных и алгоритмам
• Граф и его представления