Список смежности

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);
    }
}
We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
AS
July 22, 2019, 4:32 p.m.
Aleksandr Spiridonov

C++ - Test 001. The first program and data types

  • Result:46points,
  • Rating points-6
AS
July 22, 2019, 4:21 p.m.
Aleksandr Spiridonov

Qt - Test 001. Signals and slots

  • Result:73points,
  • Rating points1
July 22, 2019, 10 a.m.
Pavel K.

C++ - Test 006. Enumerations

  • Result:50points,
  • Rating points-4
Last comments
July 21, 2019, 6:03 a.m.
Evgenij Legotskoj

да, наверное, 32-х разрядную поддержку уже давно поа было выкинуть. К слову, у вас много проектов под Android? Часто много где вижу вопросы о том, пишет ли кто-то вообще на Qt под мобильные сист…
July 20, 2019, 2:41 p.m.
Andrej Jankovich

Очень полезная информация, увы уже выкинул поддержку 32 битных бедняг.
July 20, 2019, 9:31 a.m.
Mihailll

Вот так qDebug()<<"position:"<<event->scenePos();
July 20, 2019, 8:49 a.m.
Mihailll

Добрый день. Как можно узнать координату на графической сцене при отпускании клавиши мыши?
Now discuss on the forum
July 22, 2019, 10:50 a.m.
Pavel K.

Благодарю.Буду пробовать.
July 22, 2019, 10:10 a.m.
Pavel K.

Скорее всего в коде не правильно потоки используются. на форуме пишут кое что интересное - https://stackoverflow.com/questions/18112027/qt-5-1-qml-property-through-threads
July 22, 2019, 3:58 a.m.
Evgenij Legotskoj

Добрый день! Нужен совет сообщества по разработке функционала проверки орфографии. Одна из идей - добавить проверку орфографии при наборе текста статей. Полагаю, что наиболее аде…
July 22, 2019, 3:01 a.m.
Evgenij Legotskoj

Возможно, если при сохранении файла установить права доступа на файл. Что-то такое должно быть у QFile
Looking for a Job?
5,000.00 руб. - 15,000.00 руб.
Дизайнер
Moskovskiy, Moscow, Russia
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

For registered users on the site there is a minimum amount of advertising

EVILEG
About
Services
Join us
© EVILEG 2015-2019
Recommend hosting TIMEWEB