Как реализовать граф-матрицу (двумерный массив) по координатам отрезков?

@Posetitel · Регистрация: 19.03.2018

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

Товарищи, подскажите алгоритм или логику, чтобы граф из прилагаемой картинки представить в виде матрицы или двумерного массива, где по вертикали и по горизонтали отложены номера (а не координаты!) вершин от 1 до 5 соответственно, а на пересечении вершин вставлены длины отрезков между этими точками, если между точками связи нет, нужно проставить ноль.
матрица будет такая:
...1 2 3 4 5
1 010 0 0 0
210 0 7 5 0
3 0 7 0 0 9
4 0 5 0 0 0
5 0 0 9 0 0
на картинке соответственно в кружке показан номер узла, он соответствует вертикальным и горизонтальным столбцам матрицы, зеленым - длина ребра, проставляется в матрицу на пересечении соответствующих узлов, синим показано наличие ребер между узлами.
Список отрезков, соответствующих ребрам, я могу получить из внешнего источника, координаты вершин тоже получу, а вот как передать это все в массив да еще и с вершинами - не представлю. Расскажите логику или алгоритм.

@elixi · 17.12.2024, 17:37

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

Товарищи, подскажите алгоритм или логику, чтобы граф из прилагаемой картинки представить в виде матрицы или двумерного массива,

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

Список отрезков, соответствующих ребрам, я могу получить из внешнего источника, координаты вершин тоже получу, а вот как передать это все в массив да еще и с вершинами - не представлю.

Posetitel, пoкажите тoварищам как выглядят ваш списoк oтрезкoв и кooрдинаты вершин. Чтo этo? Файлы? Какие? В какoм oни фoрмате? Массивы, текстoвые данные? Как oрганизoваны? Если не смoжете, из чегo вам тoварищи лoгику и алгoтитм дoлжны слoжить? Не пoдскажете?

@Posetitel · 17.12.2024, 19:30 **[ТС]**

Получаю отрезки в наборе Entity.
Через методы Entity.StartPoint и Entity.EndPoint могу вытащить координаты начала и конца каждого отрезка
For Each Entity
StartPoint = Entity.StartPoint
EndPoint = Entity.EndPoint

@elixi · 18.12.2024, 10:25

Posetitel, слишкoм скудную инфoрмацию предoставляете. Навернo как-тo так:

Visual Basic
1
2
3
4
5
6
7
8
9
10
Sub Матрица_Запoлнение()
 
    Dim Матрица(1 To 5, 1 To 5)
    
    For Each Entity In Списoк_Oтрезкoв
        Матрица(Entity.StartPoint, Entity.EndPoint) = Вы_Навернo_Знаете_Чему_Равнo
        Матрица(Entity.EndPoint, Entity.StartPoint) = Вы_Навернo_Знаете_Чему_Равнo
    Next
    
End Sub

@Punkt5 · 18.12.2024, 10:35

Posetitel, пока вы ничего не сообщили.
Координаты отрезков какую размерность имеют: 2? 3? n?
Количество точек всегда не превышает 25? Или размер квадрата может увеличиваться?

Или имеется в виду, что точек всего 5 они же расположены и в вертикалях и в горизонталях. А задача - отобразить их горизонтальные связи в горизонталях квадрата, а вертикальные в вертикалях?

Пока ваше описание задачи = " Как вычислить фи в условиях невесомости"

@Posetitel · 18.12.2024, 11:02 **[ТС]**

Скорее всего какие-то вещи, очевидные и понятные для меня, или которые по моему мнению не влияют на задачу, совершенно непонятны людям со стороны, я просто этого не вижу, поэтому спрашивайте уточнения.
Пока отвечаю на то, что поступило.
Размерность координат двумерная, т.е. есть координата Х и есть координата У
Количество точек произвольное, ограничено пусть будет 1000.
Основная у меня проблема пока писал уточнения и сам рассуждал о реализации вот в чем:
в матрице нужно по горизонтали и вертикали откладывать номера вершин, а получить я могу только координаты отрезков,
т.е. во-первых не совпадает размерность величин, а во вторых надо как-то еще увязать номер вершины и конец отрезка, может этот отрезок и не попадает в вершину.
Это матрица смежности для поиска кратчайшего пути. И вот как перенести ее из чертежа, на котором я вижу только координаты маршрута или тропы, но не знаю, что за номер у мест стыковки тропинок, на язык программирования, в котором я уже смогу понять кратчайший путь по вершинам, а потом вернуть обратно в координаты я и пытаюсь разобраться.

shanemac51 · 18.12.2024, 11:31

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

Это матрица смежности для поиска кратчайшего пути.

видимо с этого надо было начинать

возможно исходила бы следующей посылки c проверкой на цикличность
тип1: 4-4 номера совпадают
тип2: 4-2-5 и 2-4-15 расстояния не совпадают
тип3: например точки зацикливаются, т.е. не связаны с другими точками

номер1	номер2	расстояние
4	2	5
2	3	7
2	1	10
3	5	9

@Posetitel · 18.12.2024, 11:35 **[ТС]**

Галина, извините, но я пока не улавливаю посылки.
Как сюда подтянуть координаты отрезков?

shanemac51 · 18.12.2024, 11:38

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

Как сюда подтянуть координаты отрезков?

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

Количество точек произвольное, ограничено пусть будет 1000.

я об этом пока не думала - конкретики не хватает

@Angry Old Man · 18.12.2024, 15:55

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

конкретики не хватает

Мне не понятно, откуда берется соответствие номера узла и его координаты. Как я понял, у Вас есть координаты концов отрезков, а с нумерацией узлов мне непонятно. Уточняйте задачу.
Попробую предложить алгоритм или логику. Я в массиве задал координаты концов отрезков (на чем-то мне надо было резвиться), из координат я организовал библиотеку, в которой пронумеровал узлы. Эта нумерация случайно совпала с Вашим чертежом. Далее по соответствию координат и нумерации узлов отрезков заполняю матрицу длинами отрезков. Помню, что матрица должна быть симметричной.

Visual Basic
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
Option Base 1
Sub GrafMatrix()
    Segm = Array( _
        -8.9, 2.2, 1.1, 2.2, _
        1.1, 2.2, 8.1, 2.2, _
        1.1, 2.2, -3.9, 2.2, _
        8.1, 2.2, 8.1, 11.2 _
    )
    Set D = CreateObject("Scripting.Dictionary")
    
    Out = "Координаты точек" & vbCr
    n = 0
    For i = 1 To UBound(Segm) Step 2
        xy = CStr(Segm(i)) & " " & CStr(Segm(i + 1))
        'MsgBox xy
        If Not D.Exists(xy) Then
            n = n + 1
            D.Add xy, n
            Out = Out & "(" & CStr(n) & ") " & xy & vbTab & vbTab
        End If
    Next
    
    ReDim Arr(n, n)
    For i = 1 To n
        For j = 1 To n
            Arr(i, j) = 0
        Next
    Next
    
    For i = 1 To UBound(Segm) Step 4
        xy1 = CStr(Segm(i)) & " " & CStr(Segm(i + 1))
        xy2 = CStr(Segm(i + 2)) & " " & CStr(Segm(i + 3))
        i1 = D.Item(xy1)
        i2 = D.Item(xy2)
        
        Arr(i1, i2) = Sqr((Segm(i) - Segm(i + 2)) ^ 2 + (Segm(i + 1) - Segm(i + 3)) ^ 2)
        Arr(i2, i1) = Arr(i1, i2)
    Next
    
    Out = Out & vbCr & vbCr & "Граф матрица" & vbCr
    For i = 1 To n
        Out = Out & vbCr
        For j = 1 To n
            Out = Out & CStr(Arr(i, j)) & vbTab
        Next
    Next
 
MsgBox Out
End Sub

Если соответствие координат узлов и номеров можно откуда-то взять, идея та же - делаем сразу из них библиотеку и точно так же строим матрицу по координатам концов отрезков.

shanemac51 · 18.12.2024, 16:59

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

получить я могу только координаты отрезков

что есть отрезок и его координаты

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

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

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

не понимаю - вы собираетесь координаты точки 2 водить 3 раза?

@Angry Old Man · 18.12.2024, 21:13

Posetitel,

Если можете указать координаты узлов и как они соединяются, то задача упрощается

Windows Batch file
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
Option Base 1
 
Sub GrafMatrix2()
    Apex = Array( _
        -8.9, 2.2, _
        1.1, 2.2, _
        8.1, 2.2, _
        -3.9, 2.2, _
        8.1, 11.2 _
    )
    Link = Array( _
        1, 2, _
        2, 3, _
        2, 4, _
        3, 5 _
    )
    
    n = UBound(Apex) / 2
    Out = "Координаты узлов" & vbCr
    For i = 1 To n
        Out = Out & "(" & CStr(i) & ") " & Apex(2 * i - 1) & " " & Apex(2 * i) & vbTab & vbTab
    Next
    
    ReDim Arr(n, n)
    For i = 1 To n
        For j = 1 To n
            Arr(i, j) = 0
        Next
    Next
    
    For i = 1 To UBound(Link) / 2
        i1 = Link(2 * i - 1): i2 = Link(2 * i)
        Arr(i1, i2) = Sqr((Apex(2 * i1 - 1) - Apex(2 * i2 - 1)) ^ 2 + (Apex(2 * i1) - Apex(2 * i2)) ^ 2)
        Arr(i2, i1) = Arr(i1, i2)
    Next
    
    Out = Out & vbCr & vbCr & "Граф матрица" & vbCr
    For i = 1 To n
        Out = Out & vbCr
        For j = 1 To n
            Out = Out & CStr(Arr(i, j)) & vbTab
        Next
    Next
 
MsgBox Out
End Sub

@Posetitel · 19.12.2024, 11:04 **[ТС]**

Спасибо всем ответившим, именно то, что нужно.

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

@Posetitel 0 / 0 / 0 Регистрация: 19.03.2018 Сообщений: 15

	Как реализовать граф-матрицу (двумерный массив) по координатам отрезков? 17.12.2024, 16:39. Показов 1016. Ответов 12 Метки нет (Все метки) Товарищи, подскажите алгоритм или логику, чтобы граф из прилагаемой картинки представить в виде матрицы или двумерного массива, где по вертикали и по горизонтали отложены номера (а не координаты!) вершин от 1 до 5 соответственно, а на пересечении вершин вставлены длины отрезков между этими точками, если между точками связи нет, нужно проставить ноль. матрица будет такая: ...1 2 3 4 5 1 010 0 0 0 210 0 7 5 0 3 0 7 0 0 9 4 0 5 0 0 0 5 0 0 9 0 0 на картинке соответственно в кружке показан номер узла, он соответствует вертикальным и горизонтальным столбцам матрицы, зеленым - длина ребра, проставляется в матрицу на пересечении соответствующих узлов, синим показано наличие ребер между узлами. Список отрезков, соответствующих ребрам, я могу получить из внешнего источника, координаты вершин тоже получу, а вот как передать это все в массив да еще и с вершинами - не представлю. Расскажите логику или алгоритм. Миниатюры 0

@Posetitel 0 / 0 / 0 Регистрация: 19.03.2018 Сообщений: 15
	17.12.2024, 19:30 [ТС]
	Получаю отрезки в наборе Entity. Через методы Entity.StartPoint и Entity.EndPoint могу вытащить координаты начала и конца каждого отрезка For Each Entity StartPoint = Entity.StartPoint EndPoint = Entity.EndPoint 0

@Punkt5 малоболт 1328 / 510 / 213 Регистрация: 30.01.2020 Сообщений: 1,243
	18.12.2024, 10:35
	Posetitel, пока вы ничего не сообщили. Координаты отрезков какую размерность имеют: 2? 3? n? Количество точек всегда не превышает 25? Или размер квадрата может увеличиваться? Или имеется в виду, что точек всего 5 они же расположены и в вертикалях и в горизонталях. А задача - отобразить их горизонтальные связи в горизонталях квадрата, а вертикальные в вертикалях? Пока ваше описание задачи = " Как вычислить фи в условиях невесомости" 0

@Posetitel 0 / 0 / 0 Регистрация: 19.03.2018 Сообщений: 15
	18.12.2024, 11:02 [ТС]
	Скорее всего какие-то вещи, очевидные и понятные для меня, или которые по моему мнению не влияют на задачу, совершенно непонятны людям со стороны, я просто этого не вижу, поэтому спрашивайте уточнения. Пока отвечаю на то, что поступило. Размерность координат двумерная, т.е. есть координата Х и есть координата У Количество точек произвольное, ограничено пусть будет 1000. Основная у меня проблема пока писал уточнения и сам рассуждал о реализации вот в чем: в матрице нужно по горизонтали и вертикали откладывать номера вершин, а получить я могу только координаты отрезков, т.е. во-первых не совпадает размерность величин, а во вторых надо как-то еще увязать номер вершины и конец отрезка, может этот отрезок и не попадает в вершину. Это матрица смежности для поиска кратчайшего пути. И вот как перенести ее из чертежа, на котором я вижу только координаты маршрута или тропы, но не знаю, что за номер у мест стыковки тропинок, на язык программирования, в котором я уже смогу понять кратчайший путь по вершинам, а потом вернуть обратно в координаты я и пытаюсь разобраться. 0

@Posetitel 0 / 0 / 0 Регистрация: 19.03.2018 Сообщений: 15
	18.12.2024, 11:35 [ТС]
	Галина, извините, но я пока не улавливаю посылки. Как сюда подтянуть координаты отрезков? 0

@Posetitel 0 / 0 / 0 Регистрация: 19.03.2018 Сообщений: 15
	19.12.2024, 11:04 [ТС]
	Спасибо всем ответившим, именно то, что нужно. 0