Преобразуване на представянето на граф от един вид в друг

Oт списък на ребра – в матрица на съседство:

Ще приведем реализацията на това преобразуване чрез средствата на езика С++. За представяне на матрицата на съседство е използван двумерен целочислен масив M. Списъкът от съседи се въвежда от клавиатурата по следния начин: от първия ред се прочитат целите числа n и m, съответно броя на върховете и броя на ребрата на графа. На всеки от останалите m реда се въвеждат двойка числа – стойностите на двата върха, свързани чрез съответното ребро. Ако графът е претеглен, за всяко ребро се въвеждат три числа, като третото е теглото на реброто.

int M[N][N]; //Матрицата на съседство
void Read( )/*Функция за записване на графа в матрица на съседство*/
{
    int,a,b,i;
    scanf("%d %d",&n,&m); /*n – брой върхове, m – брой ребра*/
    for(i=0;i<m;i++)
    {
        scanf("%d %d",&a,&b); //реброто (a,b)
        M[a][b]=M[b][a]=1; /*записване в матрицата на реброто (a,b)*/
    }
}

Oт списък на ребра – в списък от съседи:

За представяне на графа чрез списък на съседи се използва масив от вектори (като под вектор се има предвид стандартната структура в C++).
Следващият пример скицира използването на масив, описан чрез тип vector, от целочислени вектори за представяне на граф чрез средствата за програмиране на езика С++. Въвеждането на данните се реализира по начин, идентичен на вече описания.

#include <vector> //стандартната библиотека вектор
vector <int> M[N]; //масив от вектори
void Read ()
{
    int n,m,a,b,i;
    scanf("%d %d",&n,&m); /*n – брой върхове, m – брой ребра*/
    for(i=0;i<m;i++)
    {
        scanf("%d %d",&a,&b); //реброто (a,b)
        M[a].push_back(b); /*добавяне на върха b като съсед на върха a*/
        M[b].push_back(a); /*добавяне на върха a като съсед на върха b*/
    }
}