Преобразование матрицы смежности в представление графа в виде списка смежности
Предпосылка: График и его представления.
Дано представление графа в виде матрицы смежности. Задача состоит в том, чтобы преобразовать заданную матрицу смежности в представление списка смежности.
Примеры:
Input: arr[][] = [ [0, 0, 1], [0, 0, 1], [1, 1, 0] ]
Output: The adjacency list is:
0 -> 2
1 -> 2
2 -> 0 -> 1Input: arr[][] = [ [0, 1, 0, 0, 1], [1, 0, 1, 1, 1], [0, 1, 0, 1, 0], [0, 1, 1, 0, 1], [1, 1, 0, 1, 0] ]
Output: The adjacency list is:
0 -> 1 -> 4
1 -> 0 -> 2 -> 3 -> 4
2 -> 1 -> 3
3 -> 1 -> 2 -> 4
4 -> 0 -> 1 -> 3
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Матрица смежности : Матрица смежности - это двумерный массив размером V x V, где V - количество вершин в графе. Пусть 2D-массив имеет значение adj [] [], слот adj [i] [j] = 1 указывает, что существует ребро от вершины i до вершины j.
Список смежности: используется массив списков. Размер массива равен количеству вершин. Пусть массив будет array []. Входной массив [i] представляет собой список вершин, смежных с i-й вершиной.
Чтобы преобразовать матрицу смежности в список смежности. Создайте массив списков и просмотрите матрицу смежности. Если для какой-либо ячейки (i, j) в матрице « mat [i] [j] = 1 », это означает, что есть ребро от i до j , поэтому вставьте j в список на i-й позиции в массиве списки.
Ниже представлена реализация описанного выше подхода:
C ++
#include<bits/stdc++.h>using namespace std; // CPP program to convert Adjacency matrix// representation to Adjacency List // converts from adjacency matrix to adjacency listvector<vector< int >> convert( vector<vector< int >> a){ vector<vector< int >> adjList(a.size()); for ( int i = 0; i < a.size(); i++) { for ( int j = 0; j < a[i].size(); j++) { if (a[i][j] == 1) { adjList[i].push_back(j); } } } return adjList;} // Driver codeint main(){ vector<vector< int >> a; vector< int > p({0, 0, 1}); vector< int > q({0, 0, 1}); vector< int > r({1, 1, 0}); // adjacency matrix a.push_back(p); a.push_back(q); a.push_back(r); vector<vector< int >> AdjList = convert(a); cout<< "Adjacency List:" <<endl; // print the adjacency list for ( int i = 0; i < AdjList.size(); i++) { cout << i; for ( int j = 0; j < AdjList[i].size(); j++) { if (j == AdjList[i].size() - 1) { cout << " -> " << AdjList[i][j] << endl; break ; } else cout << " -> " << AdjList[i][j]; } }} // This code is contributed by Surendra_Gangwar |
Ява
// Java program to convert adjacency// matrix representation to// adjacency listimport java.util.*; public class GFG { // Function to convert adjacency // list to adjacency matrix static ArrayList<ArrayList<Integer>> convert( int [][] a) { // no of vertices int l = a[ 0 ].length; ArrayList<ArrayList<Integer>> adjListArray = new ArrayList<ArrayList<Integer>>(l); // Create a new list for each // vertex such that adjacent // nodes can be stored for ( int i = 0 ; i < l; i++) { adjListArray.add( new ArrayList<Integer>()); } int i, j; for (i = 0 ; i < a[ 0 ].length; i++) { for (j = 0 ; j < a.length; j++) { if (a[i][j] == 1 ) { adjListArray.get(i).add(j); } } } return adjListArray; } // Function to print the adjacency list static void printArrayList(ArrayList<ArrayList<Integer>> adjListArray) { // Print the adjacency list for ( int v = 0 ; v < adjListArray.size(); v++) { System.out.print(v); for (Integer u : adjListArray.get(v)) { System.out.print( " -> " + u); } System.out.println(); } } // Driver Code public static void main(String[] args) { // Given Adjacency Matrix int [][] a = { { 0 , 0 , 1 }, { 0 , 0 , 1 }, { 1 , 1 , 0 } }; // function to convert adjacency // list to adjacency matrix ArrayList<ArrayList<Integer>> adjListArray = convert(a); System.out.println( "Adjacency List: " ); printArrayList(adjListArray); }} |
Python
# Python program to convert Adjacency matrix# representation to Adjacency List from collections import defaultdict# converts from adjacency matrix to adjacency listdef convert(a): adjList = defaultdict( list ) for i in range ( len (a)): for j in range ( len (a[i])): if a[i][j] = = 1 : adjList[i].append(j) return adjList # driver codea = [[ 0 , 0 , 1 ], [ 0 , 0 , 1 ], [ 1 , 1 , 0 ]] # adjacency matrixAdjList = convert(a)print ( "Adjacency List:" )# print the adjacency listfor i in AdjList: print (i, end = "") for j in AdjList[i]: print ( " -> {}" . format (j), end = "") print () # This code is contributed by Muskan Kalra. |
C #
// C# program to convert adjacency// matrix representation to// adjacency listusing System;using System.Collections.Generic; class GFG{ // Function to convert adjacency // list to adjacency matrix static List<List< int >> convert( int [,] a) { // no of vertices int l = a.GetLength(0); List<List< int >> adjListArray = new List<List< int >>(l); int i, j; // Create a new list for each // vertex such that adjacent // nodes can be stored for (i = 0; i < l; i++) { adjListArray.Add( new List< int >()); } for (i = 0; i < a.GetLength(0); i++) { for (j = 0; j < a.GetLength(1); j++) { if (a[i,j] == 1) { adjListArray[i].Add(j); } } } return adjListArray; } // Function to print the adjacency list static void printList(List<List< int >> adjListArray) { // Print the adjacency list for ( int v = 0; v < adjListArray.Count; v++) { Console.Write(v); foreach ( int u in adjListArray[v]) { Console.Write( " -> " + u); } Console.WriteLine(); } } // Driver Code public static void Main(String[] args) { // Given Adjacency Matrix int [,] a = { { 0, 0, 1 }, { 0, 0, 1 }, { 1, 1, 0 } }; // function to convert adjacency // list to adjacency matrix List<List< int >> adjListArray = convert(a); Console.WriteLine( "Adjacency List: " ); printList(adjListArray); }} // This code is contributed by 29AjayKumar |
Список смежности: 0 -> 2 1 -> 2 2 -> 0 -> 1
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.