Список суміжності

Tree, Дерево, Алгоритм

Список суміжності представляє граф як масиву пов'язаного списку.

Індекс масиву представляє вершину і кожен елемент у його зв'язаному списку, а також репрезентує інші вершини, які утворюють ребро з вершиною.

Представлення списку суміжності

Граф та його еквівалентне подання списку суміжності показані нижче.

Список суміжності ефективний з точки зору зберігання, тому що нам потрібно зберігати лише значення для ребер. Для розрідженого графа з мільйонами вершин та ребер це може означати багато заощадженого простору.

Структура списку суміжності

Найпростішому списку суміжності потрібна структура даних вузла зберігання вершини і структура даних графа в організацію вузлів.

Ми наближаємося до основного визначення графа - сукупності вершин та ребер {V, E}. Для простоти ми використовуємо немаркований граф, а чи не позначений, тобто вершини ідентифікуються з їхньої індексам 0,1,2,3.

Давайте розглянемо структуру даних нижче.

struct node
{
    int vertex;
    struct node* next;
};
struct Graph
{
    int numVertices;
    struct node** adjLists;
};

Не дозволяйте struct node* adjLists приголомшити вас.
Нам потрібно зберегти покажчик struct node . Тому, як ми не знаємо, скільки вершин буде у графі, тож не можемо створити масив пов'язаних списків під час компіляції.

Список суміжності C++

Це та сама структура, але за допомогою вбудованого списку структур даних STL в C ++ ми робимо структуру трохи чистіше. Ми також можемо абстрагувати деталі реалізації.

class Graph
{
    int numVertices;
    list<int> *adjLists;

public:
    Graph(int V);
    void addEdge(int src, int dest);
};

Список суміжності Java

Ми використовуємо Java Collections для зберігання масиву пов'язаних списків.

class Graph
{
    private int numVertices;
    private LinkedList<integer> adjLists[];
}

Тип LinkedList визначає, які дані ви хочете зберегти у ньому. Для позначеного графа ви можете зберігати словник замість цілого значення.

Список суміжності Python

Є причина, через яку Python отримує так багато "кохання". Простий словник вершин та його ребер є достатнім уявленням графа. Ви можете зробити вершину настільки складною, як захочете.

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

Код списку суміжності в C

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int vertex;
    struct node* next;
};
struct node* createNode(int);
struct Graph
{
    int numVertices;
    struct node** adjLists;
};
struct Graph* createGraph(int vertices);
void addEdge(struct Graph* graph, int src, int dest);
void printGraph(struct Graph* graph);
int main()
{
    struct Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 4);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 6);
    addEdge(graph, 5, 1);
    addEdge(graph, 5, 6);

    printGraph(graph);

    return 0;
}


struct node* createNode(int v)
{
    struct node* newNode = malloc(sizeof(struct node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int vertices)
{
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(struct node*));

    int i;
    for (i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest)
{
    // Add edge from src to dest
    struct node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // Add edge from dest to src
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->numVertices; v++)
    {
        struct node* temp = graph->adjLists[v];
        printf("\n Adjacency list of vertex %d\n ", v);
        while (temp)
        {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

Код списку суміжності C++

#include <iostream>
#include <list>
using namespace std;

class Graph
{
    int numVertices;
    list *adjLists;

public:
    Graph(int V);
    void addEdge(int src, int dest);
};

Graph::Graph(int vertices)
{
    numVertices = vertices;
    adjLists = new list[vertices];
}

void Graph::addEdge(int src, int dest)
{
    adjLists[src].push_front(dest);
}


int main()
{
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);

    return 0;
}

Код списку суміжності Java

import java.io.*;
import java.util.*;
class Graph
{
    private int numVertices;
    private LinkedList<Integer> adjLists[];

    Graph(int vertices)
    {
        numVertices = vertices;
        adjLists = new LinkedList[vertices];

        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList();
    }

    void addEdge(int src, int dest)
    {
        adjLists[src].add(dest);
    }

    public static void main(String args[])
    {
        Graph g = new Graph(4);

         g.addEdge(0, 1);
         g.addEdge(0, 2);
         g.addEdge(1, 2);
         g.addEdge(2, 3);
    }
}