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

Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной

25.05.2013, 21:17. Показов 3715. Ответов 14
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
народ помогите пожалуйста написать программу на с++ на графы
дана матрица смежности и неориентированный граф.
выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
25.05.2013, 21:17
Ответы с готовыми решениями:

Неориентированный невзвешенный граф: найти количество вершин, лежащих в одной компоненте связности с данной вершиной
Дан неориентированный невзвешенный граф. Для него вам необходимо найти количество вершин, лежащих в одной компоненте связности с данной...

Дан неориентированный граф. В нём необходимо найти расстояние от одной заданной вершины до другой
Формат Ввода В первой строке входного файла содержится три натуральных числа N, S, F (1 <= S, F <= N <= 100) - количество вершин...

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

14
25.05.2013, 21:35
 Комментарий модератора 
Перемещено из раздела Pascal
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38178 / 21113 / 4307
Регистрация: 12.02.2012
Сообщений: 34,716
Записей в блоге: 14
25.05.2013, 22:22
Пусть n и m - номера вершин. Если для какого-либо i != n,m имеет место Matr[i,n] != 0 && Matr[i,m] != 0 - то ответ утвердительный
1
0 / 0 / 1
Регистрация: 23.05.2013
Сообщений: 14
26.05.2013, 09:42  [ТС]
почему то input1 и input2 я заполняю и программа компилируется но ничего в output не выдаёт. в чём ошибка?
подскажить пожалуйста может кто знает.


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
#include "stdafx.h"
#include "iostream"
#include "stdlib.h"
#include "fstream"
#include "stdio.h"
using namespace std;
 
FILE *f=fopen("input1.txt", "r");
FILE *g=fopen("input2.txt","r");
FILE *h=fopen("output.txt", "w");
int **gr;// указатель на матрицу смежности
int n;//колличество вершин в графе
 
void main()
{
    int i, j,v1, v2;
    fscanf(f, "%d", &n);
    gr=new int*[n];
    for (i=0; i<n; i++)
    {
        gr[i]=new int[n];
        for (j=0; j<n; j++);
        fscanf (f, "%d", &gr[i][j]);
    }
    fscanf(h, "%d", &v1, &v2);
    
    for (i=0; i<n; i++)
    if ((i!=v1) && (i!=v2))
    { (gr[i,v1]!=0 && gr[i,v2]!=0);
    fprintf(g, "%d", "DA");
    }
    else
        fprintf(g, "%d", "NET");
    
}
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
26.05.2013, 10:07
можно сделать дфс из одной вершины. пометить вершины на этом пути определенным цветом. запустить дфс из второй - если попадешь в помеченную "определенным цветом" вершину, то все ок.
1
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38178 / 21113 / 4307
Регистрация: 12.02.2012
Сообщений: 34,716
Записей в блоге: 14
26.05.2013, 10:09
А зачем ты читаешь из выходного файла (h) и пишешь во входной (g)?

Добавлено через 2 минуты
Цитата Сообщение от salam Посмотреть сообщение
можно сделать дфс
- это лишнее...
1
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
26.05.2013, 10:13
Цитата Сообщение от Catstail Посмотреть сообщение
- это лишнее...
можно попросить Вас аргументировать свои комментарии?

Добавлено через 2 минуты
второй дфс, действительно, без надобности. достаточно запустить дфс из любой из двух - если вторая посещена, то все ок.
1
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38178 / 21113 / 4307
Регистрация: 12.02.2012
Сообщений: 34,716
Записей в блоге: 14
26.05.2013, 10:31
Цитата Сообщение от salam Посмотреть сообщение
можно попросить Вас аргументировать свои комментарии?
- пожалуйста. Запускаем dfs (кстати, а чем bfs хуже?) из одной вершины, обойдем весь граф... И даст это ответ на вопрос задачи (есть ли у двух заданных вершин общая смежная, т.е. достижимая из каждой за один шаг)?
1
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
26.05.2013, 10:34
у нас разное представление о понятии "соседствуют". автор, проясните, пожалуйста: "соседствуют" это имеют ребра в эту вершину или лежат с ней на одной компоненте связности?
1
0 / 0 / 1
Регистрация: 23.05.2013
Сообщений: 14
26.05.2013, 10:45  [ТС]
да. соседствуют это тогда когда имеют ребра в одну вершину.
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
26.05.2013, 10:46
Цитата Сообщение от Danila777 Посмотреть сообщение
да. соседствуют это тогда когда имеют ребра в одну вершину.
тогда вариант Catstail единственный корректный.
1
0 / 0 / 1
Регистрация: 23.05.2013
Сообщений: 14
26.05.2013, 10:52  [ТС]
я понимаю. а что в моей проге нитак.
укажите пожалуйста.
и как исправить чтобы было правильно.
помогите пожалуйста.
0
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
26.05.2013, 11:01
давайте я покажу, как написал бы сам, а Вы решите для себя, что и как менять.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include...
 
int main() 
{
   const int msize = ...;
   int g[msize][msize];
   int n, u, v; // количество вершин и номера двух рассматриваемых вершин u, v
   cin >> n;
   for(int i=0; i < n; i++)
      for(int j=0; j < n; j++)
         cin >> g[i][j];
   for(int i=0; i < n; i++)
      if(g[u][i] != ... && g[v][i] != ...) // вместо ... нечто, обозначающее отсутствие ребра
         OK
   if(!OK)
      Bad
   return 0;
}
1
0 / 0 / 1
Регистрация: 23.05.2013
Сообщений: 14
26.05.2013, 11:38  [ТС]
спасибо.
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38178 / 21113 / 4307
Регистрация: 12.02.2012
Сообщений: 34,716
Записей в блоге: 14
26.05.2013, 12:35
Вот иллюстрация. Выбираем вершины 1 и 7. И сразу по матрице смежности (1 цикл!) убеждаемся, что вершина 4 - та самая...
Миниатюры
Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной   Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной  
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
26.05.2013, 12:35
Помогаю со студенческими работами здесь

Дан неориентированный граф. Удалить ребро, соединяющее вершины А и B
Дан неориентированный граф. Удалить ребро, соединяющее вершины А и B. Никак не могу догадаться как это реализовать через список смежности...

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

Неориентированный граф задан матрицей смежности, найти степени всех вершин графа
Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа. Входные данные Сначала вводится число n...

Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа
Работа с графами. Совсем не шарю в них. Может кто то поможет написать программу. Только с комментариями пожалуйста. Постановка задачи: ...

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер
Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер. Формат входных данных ...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Новые блоги и статьи
Модульный подход на примере 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
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru