Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
0 / 0 / 0
Регистрация: 06.03.2019
Сообщений: 20

Графы: определить, из каких вершин в данную вершину направлены ребра

06.03.2019, 21:35. Показов 2475. Ответов 5
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Всем привет, такая проблема дано задание "Дан граф смежности ( количество вершин произвольные вводятся пользователем ), определить из каких вершин в данную вершину направлены ребра ( ребра тоже вводит пользователь, я использовал в своем коде матрицу)". Все вроде понятно я создаю динамическую матрицу ввожу туда данные, затем выбираю вершину и программа должна пройтись по столбце матрицы этой вершины и вывести из каких вершин в мою выбранную направленны ребра ( это как я в голове построил задание ), но в коде у меня не получается этого добиться. Сразу говорю я учусь только, сильно не ругайте.
Вот и код:
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
#include "pch.h"
#include <iostream>
 
using namespace std;
 
int main()
{
    setlocale (LC_ALL, "Russian");
    int n;
    cout << "Введите количество вершин графа: " << endl;
    cin >> n;
    int **arr = new int*[n];
    for (int v = 0; v < n; v++)
        arr[v] = new int[n];
    int i, j, p;
    for (i = 0; i < n; i++)
    {
        for ( j = 0; j < n; j++)
        {
            cout << "Направлено ли ребро из " << i + 1 << " вершины в(во) " << j + 1 << " вершину (если да то введите 1, если нет введите 0)..." << endl;
            cin >> arr[i][j];
        }
    }
    
    cout << "Выберите вершину ";
    cin >> p;
    j = p;
    
    for (i = 0; i < n; i++)
        if (arr[i][j] = 1)
            cout << "Из " << i + 1 << " вершины направлено ребро в " << j << " вершину" << endl;
    
    return 0;
}
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
06.03.2019, 21:35
Ответы с готовыми решениями:

Определить, является ли одна из вершин дерева предком другой (Графы)
Напишите программу, которая для двух вершин дерева определяет, является ли одна из них предком другой. Входные данные Первая...

Дома в Берляндии (рёбра, графы)
Здравствуйте! Подскажите пожалуйста каким образом можно решить эту задачу? Изложите алгоритм в нескольких словах. Как известно, в...

Отсортировать ребра по весу (графы)
Тема:Базовые структуры данных Задание:Отсортируйте ребра по весу. Спасибо заранее) Вот ребра:

5
447 / 333 / 172
Регистрация: 01.07.2015
Сообщений: 1,161
07.03.2019, 14:11
Лучший ответ Сообщение было отмечено Gonerman как решение

Решение

Цитата Сообщение от Gonerman Посмотреть сообщение
граф смежности
Что за зверь такой

Граф проще вводить списком ребер:

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
#include <iostream>
 
using namespace std;
 
int main() {
  setlocale(LC_ALL, "Russian");
  int n;
  cout << "Введите количество вершин графа: " << endl;
  cin >> n;
  int m;
  cout << "Кол-во ребер: ";
  cin >> m;
  int **arr = new int *[n];
  for (int i = 0; i < n; i++)
    arr[i] = new int[n];
  for (int i = 0; i < m; i++) {
    int from;
    int to;
    cin >> from >> to;
 
    // 1-нумерация графа
    --from;
    --to;
 
    // граф ориентированный
    arr[from][to] = 1;
  }
 
  int ans;
  cout << "Выберите вершину ";
  cin >> ans;
 
  for (int i = 0; i < n; i++) {
    if (arr[i][ans - 1] == 1)
      cout << "Из " << i + 1 << " вершины направлено ребро в " << ans
           << " вершину\n";
  }
 
  return 0;
}
Для графа (см. картинку) выводит:

Code
1
2
3
4
5
6
7
8
9
10
11
12
Введите количество вершин графа: 
4
Кол-во ребер: 5
1 2
1 3
2 3
4 3
4 2
Выберите вершину 3
Из 1 вершины направлено ребро в 3 вершину
Из 2 вершины направлено ребро в 3 вершину
Из 4 вершины направлено ребро в 3 вершину
Изображения
 
1
0 / 0 / 0
Регистрация: 06.03.2019
Сообщений: 20
07.03.2019, 14:29  [ТС]
ReDoXспасибо большое а можете тему назвать или подтолкнуть на мысль того, что вы использовали для обозначения ребер (хочется изучить этот раздел)
0
447 / 333 / 172
Регистрация: 01.07.2015
Сообщений: 1,161
07.03.2019, 14:43
Gonerman, не понял вопрос. Визуализатор графов нужен? Или что в обозначениях ребер нужно?
0
0 / 0 / 0
Регистрация: 06.03.2019
Сообщений: 20
07.03.2019, 14:49  [ТС]
ReDoX, вот эта часть мне не понятна:
Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i < m; i++) {
    int from;
    int to;
    cin >> from >> to;
 
    // 1-нумерация графа
    --from;
    --to;
 
    // граф ориентированный
    arr[from][to] = 1;
  }
0
447 / 333 / 172
Регистрация: 01.07.2015
Сообщений: 1,161
07.03.2019, 14:54
Gonerman, Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер (вики). Ребро - пара значений (u, v):
u - откуда
v - куда

m - кол-во ребер в графе (кол-во стрелочек на картинке; их 5)

Можно завести n+1 матрицу, но проще потом просто выводить ответ+1 вместо увеличения размера матрицы, поэтому от введенных ребер отнимается единица.

Граф ориентированный - следовательно, стрелочка идет только из from в to, но не из to во from
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
07.03.2019, 14:54
Помогаю со студенческими работами здесь

Удалить из неориентироованного графа данную вершину
Ребят. как это реализовать на с++? Дан неориентированный граф. Удалить из графа данную вершину.

Графы. Ребра. Расстояние между ребрами
У меня такая проблема,мне нужно чтоб из одной вершины(города) в другую шли два ребра(дороги),и чтобы эти дороги друг от друга на...

Задача на графы. Удалить ребра так, чтобы степень любой вершины была равна 3 или 0
Здравствуйте. Условие задачи, собственно, в названии темы. Возникли проблемы с алгоритмом, не говоря уже про код. Ограничений на входной...

При передвижении вершин прямоугольника нужно отрисовать заново ребра
Есть класс MyButton:Button. В нем реализована потоковая обработка нажатия, перетаскивания, отпускания (возможность вручную передвигать...

Графы: заданы две вершины, начальная и конечная, требуется найти первую вершину в пути между ними
Задан граф матрицей смежности Заданы две вершины, начальная и конечная, требуется найти первую вершину в пути между ними


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru