Массив указателей списков смежных вершин

@doorss · Регистрация: 19.08.2013

Студворк — интернет-сервис помощи студентам

Добрый день. Помогите пожалуйста в реализации списка смежности для графа. Знаю, в инете много примеров, но пока для своего не нашел подходящего. Вот у меня есть структура:

C++
1
2
3
4
struct list {
    int n;
    list *next;
};

для этой структуры определенны две функции, добавление элемента в конец и вывод списка.

В void main

C++
1
list* first[csize];

C++
1
2
3
4
5
6
  void listMatrix(list*&first) {
        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) add_el(first[i],j); }
    }
    }
void display(list* first) for(int i=0; i<size; i++) print_list(first[i]);

Что делается не так, у меня выдает ошибку связанную с указателями. Как грамотней все это реализовать?

@outoftime · 04.01.2014, 15:49

Сообщение от doorss

list*&first

Это немного лишнее

Весь код в студию.

@doorss · 04.01.2014, 15:56 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
struct list {
    int n;
    list *next;
};
 
list* add_el (list *first, int l) { /* функция добавляющая элемент */}
 
void print_list(list *first ) { /* функция выводящая список */}
 
class Graph {
    public:
    int size;
    int **adjacency_matrix;
 
    Graph(int csize, int**carray) {
        size=csize;
        adjacency_matrix= new int *[size];
        for (int i = 0; i < csize; i++) adjacency_matrix[i] = new int [csize];
        for(int i=0; i<size; i++) for (int j=0; j<size; j++) adjacency_matrix[i][j]=carray[i][j];
    }
   
 
    void listMatrix(list*&first) {
        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) add_el(first[i],j); }
    }
    }
    void display(list* first)
    {
        for(int i=0; i<size; i++) print_list(first[i]);
    }
};
 
 
int main()
{
   russian();
    int num=1;
 
 
ifstream iFile("input.txt", ios::in);
    int csize;
    iFile>>csize;
    int **carray = new int *[csize];
    for (int i = 0; i < csize; i++) carray[i] = new int [csize];
    for(int i=0; i<csize; i++) for (int j=0; j<csize; j++) iFile>>carray[i][j];
 
list* first[csize];
 
    return 0;
}

@outoftime · 04.01.2014, 16:15

doorss, STL можно?

@doorss · 04.01.2014, 16:26 **[ТС]**

да.

@outoftime · 04.01.2014, 16:43

doorss, матрицу смежности я бы сделал так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
#include <initializer_list>
 
class graph : public std::vector<std::vector<int>>
{
public:
    graph() : std::vector<std::vector<int>>() {}
    graph(const std::initializer_list<std::vector<int>> &list)
        : std::vector<std::vector<int>>(list) {}
};
 
int main()
{
    graph g = {
        {0,0,1},
        {1,0,0},
        {0,1,0}
    };
    for (const auto &row : g)
    {
        for (const auto &elem : row)
            std::cout << elem << " ";
        std::cout << "\n";
    }
}

Теперь вопрос зачем тебе этот список и как ты его хочешь использовать?

@doorss · 04.01.2014, 16:56 **[ТС]**

outoftime , прошу прощение. Я думал, под stl вы имеете ввиду не вектор, а стандартный list. Мне хочется через списки реализовать. Это ведь не сложно. Всего надо сделать одномерный массив, размерности кол-во вершин, и чтобы он хранил указатели на начало нескольких списков. В свою очередь каждый список из матрицы смежности заполняется. У меня проблема вышла, когда я начал создавать функцию которая возвращает такой одномерный массив. И в итоге у меня ничего не вышло.

Добавлено через 8 минут

C++
1
2
3
4
5
void listMatrix(list*&first) {
        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) add_el(first[i],j); } !!! - тут ругается первым делом!
    }
    }

||=== class-graph, Debug ===|
D:\class-graph\main.cpp||In member function 'void Graph::listMatrix(list*&)':|
D:\class-graph\main.cpp|127|error: cannot convert 'list' to 'list*' for argument '1' to 'list* add_el(list*, int)'|
D:\class-graph\main.cpp||In member function 'void Graph::display(list*)':|
D:\class-graph\main.cpp|132|error: cannot convert 'list' to 'list*' for argument '1' to 'void print_list(list*)'|
D:\class-graph\main.cpp||In function 'int main()':|
D:\class-graph\main.cpp|179|error: no matching function for call to 'Graph::display()'|
D:\class-graph\main.cpp|179|note: candidate is:|
D:\class-graph\main.cpp|130|note: void Graph::display(list*)|
D:\class-graph\main.cpp|130|note: candidate expects 1 argument, 0 provided|
D:\class-graph\main.cpp|154|warning: unused variable 'first' [-Wunused-variable]|
||=== Build finished: 3 errors, 1 warnings (0 minutes, 2 seconds) ===|

@outoftime · 04.01.2014, 17:06

doorss, написать то можно все что угодно, вопрос в том зачем оно надо.

Я пока не совсем понимаю зачем надо хранить список смежности если уже есть матрица смежности. Обычно надо одно из двух а не оба варианта сразу. Список смежности я обычно храню в std::vector<std::set<int>>, вместо std::set можете использовать std::list если по заданию оно лучше, только насколько я помню лучше использовать std::vector вместо std::list в силу того что прошлые версии STL давали низкую производительность для std::list, std::queue.

Добавлено через 5 минут

Сообщение от doorss

void listMatrix(list*&first) {
* * * * for(int i=0; i<size; i++) {
* * * * * * for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) add_el(first[i],j); } !!! - тут ругается первым делом!
* * }
* * }

Я не понимаю что выходите этим сделать, но если разименовать указатель first вы не получите указатель, это уже будет ссылка на объект, сразу вопрос если ли у first интерфейс доступа по индексу и т.д.

@doorss · 04.01.2014, 17:13 **[ТС]**

я бы хотел бы так реализовать, причем с помощью своего списка. Это в идеальном варианте.

Задумка такова: В классе мы имеем функцию, которая возвращает нам этот массив списков.

C++
1
2
3
4
5
6
7
8
9
/* Эта функция в классе*/
list* listMatrix() {
list* first[size];
 
for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) first[i]=add_el(first[i],j); }
 }
return first;
}

Но почему то не работает такая конструкция. Видимо, я не понимаю как имеено возвратить этот массив структур.

и потом следом, функция которая все это дело выводит.

@outoftime · 04.01.2014, 17:19

BTW: если вы хотите создать массив ваших структур list **array, т.е. массив указателей на структуры

@doorss · 04.01.2014, 17:54 **[ТС]**

т.е так

C++
1
2
3
4
5
6
7
8
    list** listMatrix() {
        list** first[size];
 
        for(int i=0; i<size; i++) {
                for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) first[i]=add_el(first[i],j); }
        }
    return first;
    }

D:\class-graph\main.cpp|129|error: cannot convert 'list**' to 'list*' for argument '1' to 'list* add_el(list*, int)'|

Добавлено через 6 минут

C++
1
2
3
4
5
6
7
8
list** listMatrix() {
        list** first[size];
 
        for(int i=0; i<size; i++) {
                for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) *(first[i])=add_el(*(first[i]),j); }
        }
    return *(first); //* вот тут должен возвращаться массив указателей на структуры
    }

Добавлено через 19 минут
Вобщем вот, почему то вылетает. Правильно ли у меня заполняется массив?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
list* add_el (list *first, int m) {
        if(!first) {
            first=new list;
            first->n=m;
            first->next=0;
        }
        else {
            list *p=new list;
            p=first;
            while(p->next) {
            p=p->next;
            }
            list *w=new list;
            w->n=m;
            w->next=p->next;
            p->next=w;
        }
    return first;
}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
    list** listMatrix() {
        list** first[size];
 
        for(int i=0; i<size; i++) {
                for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) *(first[i])=add_el(*(first[i]),j); }
        }
    return *(first);
    }
 
    void display()
    {
        for(int i=0; i<size; i++) print_list(listMatrix()[i]);
    }

@__General__ · 04.01.2014, 18:05

Сообщение от outoftime

Я пока не совсем понимаю зачем надо хранить список смежности если уже есть матрица смежности.

При хранении графа матрицей смежности расход памяти - O(n^2), где n - количество вершин.
При этом, если граф мало заполнен, т. е. ребер относительно немного, то в матрице смежности будет много нулей - несуществующих ребер, под которые расходуется память.
Поэтому матрицей смежности имеет смысл хранить только почти полный граф.

Реализация списками смежности лучше тем, что при в этом случае мы не заказываем памяти под несуществующие ребра, и память здорово экономится.
(Расход памяти - O(n+m), где n - количество вершин в графе, m - кол-во ребер)

Добавлено через 9 минут
Нашел у себя реализацию:

ХЕДР:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#ifndef GRAPH_H
#define GRAPH_H
 
#include <string>
 
using namespace std;
 
class edge;
class vertex;
class graph;
 
class edge
{
public:
    int price;
    edge *next_edge;
    vertex *neighbour;
 
    edge();
    edge(vertex*, vertex*, int);
    ~edge();
};
 
class vertex
{
public:
    string name;
    edge *edge_list;
    vertex *next_vert;
 
    vertex(string, vertex*);
    ~vertex();
};
 
class graph
{
public:
    vertex *vert_list;
    
    graph();
    ~graph();
 
    void add_edge(string, string, int);
    void del_edge(string, string);
    bool add_vert(string);
    bool del_vert(string);
private:
    int num_vert;
    int num_edge;
 
    vertex* SearchByName(string);
};
 
#endif

CPP:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <iostream>
 
#include "Graph.h"
 
edge::edge()
{
    price = 0;
    next_edge = NULL;   
    neighbour = NULL;
}
 
edge::edge(vertex *vert_1, vertex *vert_2, int Price)
{
    price = Price;
    next_edge = vert_1->edge_list->next_edge;
    neighbour = vert_2;
}
 
edge::~edge()
{
}
 
 
vertex::vertex(string Name, vertex *NextVert)
{
    name = Name;
    priority = 0;
 
    edge_list = new edge;
    next_vert = NextVert;
 
    pred_vert = NULL;
}
 
vertex::~vertex()
{
}
 
int vertex::get_prior(vertex *pr_vert)
{
    if (pr_vert) {
        edge *cur_r = edge_list->next_edge;
        while (cur_r->neighbour != pr_vert) {
            cur_r = cur_r->next_edge;
        }
        return pr_vert->priority+cur_r->price;
    }
    else {
        return 0;
    }
}
 
 
graph::graph()
{
    vert_list = new vertex("0", NULL);
    Q = new queue;
 
    num_vert = 0;
    num_edge = 0;
}
 
graph::~graph()
{
    vertex *del_v = vert_list->next_vert, *cur_v = del_v->next_vert;
    while (del_v) {
        del_vert(del_v->name);
        del_v = cur_v;
        if (cur_v) {
            cur_v = cur_v->next_vert;
        }
    }
    delete vert_list;
 
    delete Q;
}
 
void graph::add_edge(string Name_1, string Name_2, int Price)
{
    vertex *vert_1 = SearchByName(Name_1);
    vertex *vert_2 = SearchByName(Name_2);
 
    vert_1->edge_list->next_edge = new edge(vert_1, vert_2, Price);
    vert_2->edge_list->next_edge = new edge(vert_2, vert_1, Price);
 
    num_edge++;
}
 
void graph::del_edge(string Name_1, string Name_2)
{
    vertex *vert_1 = SearchByName(Name_1);
    vertex *vert_2 = SearchByName(Name_2);
 
    edge *prev_r = vert_1->edge_list, *cur_r = vert_1->edge_list->next_edge;
    while (cur_r->neighbour != vert_2) {     //удаляем ребро из списка вершины vert_1. 
        prev_r = cur_r;
        cur_r = cur_r->next_edge;
    }
    prev_r->next_edge = cur_r->next_edge;
    delete cur_r;
 
    prev_r = vert_2->edge_list, cur_r = vert_2->edge_list->next_edge;
    while (cur_r->neighbour != vert_1) {     //удаляем ребро из списка вершины vert_2.
        prev_r = cur_r;
        cur_r = cur_r->next_edge;
    }
    prev_r->next_edge = cur_r->next_edge;
    delete cur_r;
 
    num_edge--;
}
 
bool graph::add_vert(string Name)
{
    vertex *check_v = SearchByName(Name);
 
    if (!check_v) {
        vert_list->next_vert = new vertex(Name, vert_list->next_vert);
        num_vert++;
 
        return true;
    }
    else {
        return false;
    }
}
 
bool graph::del_vert(string Name)
{
    vertex *del_v = SearchByName(Name);
 
    if (del_v) {
        if (del_v->edge_list->next_edge) {
            edge *del_r = del_v->edge_list->next_edge, *cur_r = del_r->next_edge;
            while (del_r) {
                del_edge(del_v->name, del_r->neighbour->name);  //удаляем инцидентные ребра.
                del_r = cur_r;
                if (cur_r) {
                    cur_r = cur_r->next_edge;
                }
            }
        }
 
        vertex *prev_v = vert_list, *cur_v = vert_list->next_vert;
        while (cur_v != del_v) { 
            prev_v = cur_v; 
            cur_v = cur_v->next_vert;
        }
        prev_v->next_vert = cur_v->next_vert;
        delete cur_v;     //удаляем саму вершину.
 
        num_vert--;
 
        return true;
    }
    else {
        return false;
    }
}

Я, как видите, храню граф списком вершин, в каждой из которых - список выходящих из нее ребер.

@doorss · 04.01.2014, 21:40 **[ТС]**

__General__, спасибо за код, но мне бы хотелось услышать, где выше приведенном в моем коде ошибка, чтобы понять, что я не так делаю. Реализаций много, у меня по другому чуть сделано.

Добавлено через 3 часа 22 минуты
Помогите, я уже запутался, вылетает. Ошибка сегментации, возможно, я не правильно заполняю списки.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
list* add_el (list *first, int m) {
        if(!first) {
            first=new list;
            first->n=m;
            first->next=0;
        }
        else {
            list *p=new list;
            p=first;
            while(p->next) {
            p=p->next;
            }
            list *w=new list;
            w->n=m;
            w->next=p->next;
            p->next=w;
        }
    return first;
}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
list** listMatrix() {
        list** first[size];
 
        for(int i=0; i<size; i++) {
                for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) *(first[i])=add_el(*(first[i]),j); }
        }
    return *(first);
    }
 
    void display()
    {
        for(int i=0; i<size; i++) print_list(listMatrix()[i]);
    }

@__General__ · 05.01.2014, 04:05

Ну в add_el(...) я ошибок не нашел.
Единственное что - если вы хотите добавлять элементы в хвост списка, то было бы рационально помнить в самой структуре его хвост, чтобы не идти до последнего элемента каждый раз в цикле.
(В вашем случае добавление осуществляется за O(n), хотя можно за O(1)).
Ну или можно добавлять новые элементы в голову.

Теперь по поводу listMatrix().
Прежде всего, сразу бросается в глаза то, что тип возвращаемого значения не совпадает с объявленным типом функции: функция у вас имеет тип list**, а возвращаете вы *(first), то есть list*;
Потом, у вас ошибка при вызове add_el:

Сообщение от doorss

*(first[i])=add_el(*(first[i]),j);

first имеет тип list**, значит first[i] - list*, *(first[i]) - list. В то время как add_el - функция типа list*.
Собственно, у вас и в качестве аргумента add_elвыступает *(first[i]) вместо должного first[i].

Добавлено через 32 минуты
Ааа, я похоже неправильно понял. first у вас - массив указателей на указатель...
Короче, массив переменных типа list**, а не list*, как показалось мне сначала.
В таком случае, код, вроде, должен компилироваться.

Правда, я не совсем понимаю, зачем вы объявили такой массив... Вы, я так понял, хотите ,чтобы функция listMatrix() возвращала массив указателей на списки (то есть указатель на первый элемент массива, он же - его имя).
Однако, вы возвращаете первый(нулевой) элемент массива указателей на указатели на ваши списки, который не является указателем на первый элемент нужного массива.

PS
Сделайте first просто массивом указателей (list*).
Дальше подправьте все ,что нужно подправить (в конце тогда должно стоять просто

C++
1
return first

и тд).

ну как-то так...

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	04.01.2014, 16:15
	doorss, STL можно? 0

@doorss 0 / 0 / 0 Регистрация: 19.08.2013 Сообщений: 14
	04.01.2014, 16:26 [ТС]
	да. 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	04.01.2014, 17:19
	BTW: если вы хотите создать массив ваших структур list **array, т.е. массив указателей на структуры 0