Как определить смежность двух вершин неориентированного графа

@dakosha · Регистрация: 13.02.2021

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

Здравствуйте,

Помогите пожалуйста. Дано задание определить смежность двух вершин неориентированного графа. Я знаю как это сделать используя матрицу смежности, но мне нужно использовать список смежности.

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  public class Graph {
    private ArrayList<Vertex> vertices = new ArrayList<Vertex>();
    private ArrayList<Edge> edges = new ArrayList<Edge>();
    public Graph(ArrayList<Vertex> vertices, ArrayList<Edge> edges) {
        
        this.vertices = vertices;
        this.edges = edges;      
 
 
    }
    public boolean adjacent(Vertex v, Vertex w) {
    
    return true; 
    }
}

Заранее благодарю

@alhaos · 19.04.2021, 12:47

PowerShell
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
. {
 
    $graph = @"
{
    "nodes":[
       {
          "id": "a",
          "adjacentNodes":["b"]
       },
       {
          "id": "b", 
          "adjacentNodes":["a", "c", "d"]
       },
       {
          "id": "c", 
          "adjacentNodes":["b", "d" ,"e"]
       },
       {
          "id": "d", 
          "adjacentNodes":["d", "c"]
       },
       {
          "id": "e", 
          "adjacentNodes":["c"]
       },
    
    ]
 }
"@ | ConvertFrom-Json
    ($graph.where{$_.nodes.id -eq 'b'}).nodes.adjacentNodes -contains 'd'
}

...as is... для ознакомительных целей.

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

Кликните здесь для просмотра всего текста

PowerShell
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
PS C:\Users\semenoval> . {
>>
>>     $graph = @"
>> {
>>     "nodes":[
>>        {
>>           "id": "a",
>>           "adjacentNodes":["b"]
>>        },
>>        {
>>           "id": "b",
>>           "adjacentNodes":["a", "c", "d"]
>>        },
>>        {
>>           "id": "c",
>>           "adjacentNodes":["b", "d" ,"e"]
>>        },
>>        {
>>           "id": "d",
>>           "adjacentNodes":["d", "c"]
>>        },
>>        {
>>           "id": "e",
>>           "adjacentNodes":["c"]
>>        },
>>
>>     ]
>>  }
>> "@ | ConvertFrom-Json
>>     ($graph.where{$_.nodes.id -eq 'b'}).nodes.adjacentNodes -contains 'd'
>>
>>     foreach ($node1 in $graph.nodes){
>>         "Node {0} adjacent: " -f $node1.id
>>         foreach ($node2 in $graph.nodes){
>>             "`tnode: {0} {1} " -f $node2.id, ($node1.adjacentNodes -contains $node2.id)
>>         }
>>     }
>> }
True
Node a adjacent:
        node: a False
        node: b True
        node: c False
        node: d False
        node: e False
Node b adjacent:
        node: a True
        node: b False
        node: c True
        node: d True
        node: e False
Node c adjacent:
        node: a False
        node: b True
        node: c False
        node: d True
        node: e True
Node d adjacent:
        node: a False
        node: b False
        node: c True
        node: d True
        node: e False
Node e adjacent:
        node: a False
        node: b False
        node: c True
        node: d False
        node: e False
PS C:\Users\semenoval>
PS C:\Users\semenoval>

@Shamil1 · 19.04.2021, 17:53

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

определить смежность двух вершин неориентированного графа

Посмотреть, если нужное ребро в списке?

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/