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

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
Looking for a Job?
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

e
Oct. 14, 2019, 2:59 p.m.
erina_m

C++ - Тест 003. Условия и циклы

  • Result:78points,
  • Rating points2
S
Oct. 14, 2019, 4:09 a.m.
Sergey1985

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

  • Result:80points,
  • Rating points4
AM
Oct. 12, 2019, 5:24 p.m.
Arshak Martirosyan

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

  • Result:66points,
  • Rating points-1
Last comments
Oct. 14, 2019, 7:48 a.m.
Evgenij Legotskoj

Добрый день. Нет, если сами по себе координаты при ресайзе все подсчитываются правильно, то это уже проблема графической подсистемы в ОС и работы с X11, если вы конечно под Linux собирали проект…
m
Oct. 13, 2019, 9:17 a.m.
magrif

Здравствуйте. Сделал подобным образом ресайз и в Qt Widgets, и в QML. Везде получаю, что при изменении размера через левую или верхннюю границы проихсодит мерцание подобно как на этом виде…
Oct. 6, 2019, 1:44 p.m.
Evgenij Legotskoj

Может база не открылась в прошлый раз. Либо пересобрали проект. хз, если честно ))
s
Oct. 6, 2019, 11:27 a.m.
sander-007

Добрый день Евгений. Спасибо за пример, все понятно. Попытался сделать по аналогии сохранение в базе MySQL заготовок отчетов excel, но MySQL ругается на нарушение в строке запроса. Я подозреваю,…
Sept. 30, 2019, 3:33 a.m.
Evgenij Legotskoj

Если честно то с авторизацией в мобильном приложении я не работал. Знаю, что для таких вещей используют батарейку Django Rest Framework, с помощью которого можно получить токена для самого сайта…
Now discuss on the forum
Oct. 14, 2019, 2:51 p.m.
Evgenij Legotskoj

Добрый день. Первое, что приходит на ум, то можно подружить это дело через веб сокеты. Со стороны Django - это использование батарейки django-channels, а со стороны это QtWebSockets. …
Oct. 11, 2019, 3:11 a.m.
Evgenij Legotskoj

Понятно. Мне нужен пример вашего кода с проблемой. Если сможете накидать вырезку из вашего проекта, которую можно будет скомпилировать и посмотреть, что там происходит, то попробую помочь. Но бы…
t
Oct. 10, 2019, 10:58 a.m.
tantrido

Вот ответ на мой вопрос: https://doc.qt.io/qt-5/qtvirtualkeyboard-deployment-guide.html#creating-inputpanel The input panel must be a sibling element next to the application conta…
Oct. 9, 2019, 3:45 p.m.
Evgenij Legotskoj

Добрый день. Нет, я таким не сталкивался, но вот таким образом вы можете разбить тот тег, на ноды, и забрать текст в нормально порядке, а потом вам уже не составит труда, как я думаю, запи…
Oct. 9, 2019, 12:04 p.m.
Vadim Polshkov

Здравствуйте. Все получилось, только редирект сделал по другому redirect(price.file.url) Спасибо вам за помощь!
EVILEG
About
Services
© EVILEG 2015-2019
Recommend hosting TIMEWEB