Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Danila777
0 / 0 / 1
Регистрация: 23.05.2013
Сообщений: 14
#1

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

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

народ помогите пожалуйста написать программу на с++ на графы
дана матрица смежности и неориентированный граф.
выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.05.2013, 21:17
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной (C++):

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

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

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

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности
Нужно задать граф списком ребер и вывести его в виде матрицы смежности. Знаю что в i строке j столбце ставят 1 если между вершинами i...

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

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

14
Kodzaev
25.05.2013, 21:35
  #2
 Комментарий модератора 
Перемещено из раздела Pascal
0
Catstail
Модератор
23540 / 11650 / 2036
Регистрация: 12.02.2012
Сообщений: 18,992
25.05.2013, 22:22 #3
Пусть n и m - номера вершин. Если для какого-либо i != n,m имеет место Matr[i,n] != 0 && Matr[i,m] != 0 - то ответ утвердительный
1
Danila777
0 / 0 / 1
Регистрация: 23.05.2013
Сообщений: 14
26.05.2013, 09:42  [ТС] #4
почему то 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
salam
174 / 155 / 28
Регистрация: 10.07.2012
Сообщений: 766
26.05.2013, 10:07 #5
можно сделать дфс из одной вершины. пометить вершины на этом пути определенным цветом. запустить дфс из второй - если попадешь в помеченную "определенным цветом" вершину, то все ок.
1
Catstail
Модератор
23540 / 11650 / 2036
Регистрация: 12.02.2012
Сообщений: 18,992
26.05.2013, 10:09 #6
А зачем ты читаешь из выходного файла (h) и пишешь во входной (g)?

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

Добавлено через 2 минуты
второй дфс, действительно, без надобности. достаточно запустить дфс из любой из двух - если вторая посещена, то все ок.
1
Catstail
Модератор
23540 / 11650 / 2036
Регистрация: 12.02.2012
Сообщений: 18,992
26.05.2013, 10:31 #8
Цитата Сообщение от salam Посмотреть сообщение
можно попросить Вас аргументировать свои комментарии?
- пожалуйста. Запускаем dfs (кстати, а чем bfs хуже?) из одной вершины, обойдем весь граф... И даст это ответ на вопрос задачи (есть ли у двух заданных вершин общая смежная, т.е. достижимая из каждой за один шаг)?
1
salam
174 / 155 / 28
Регистрация: 10.07.2012
Сообщений: 766
26.05.2013, 10:34 #9
у нас разное представление о понятии "соседствуют". автор, проясните, пожалуйста: "соседствуют" это имеют ребра в эту вершину или лежат с ней на одной компоненте связности?
1
Danila777
0 / 0 / 1
Регистрация: 23.05.2013
Сообщений: 14
26.05.2013, 10:45  [ТС] #10
да. соседствуют это тогда когда имеют ребра в одну вершину.
0
salam
174 / 155 / 28
Регистрация: 10.07.2012
Сообщений: 766
26.05.2013, 10:46 #11
Цитата Сообщение от Danila777 Посмотреть сообщение
да. соседствуют это тогда когда имеют ребра в одну вершину.
тогда вариант Catstail единственный корректный.
1
Danila777
0 / 0 / 1
Регистрация: 23.05.2013
Сообщений: 14
26.05.2013, 10:52  [ТС] #12
я понимаю. а что в моей проге нитак.
укажите пожалуйста.
и как исправить чтобы было правильно.
помогите пожалуйста.
0
salam
174 / 155 / 28
Регистрация: 10.07.2012
Сообщений: 766
26.05.2013, 11:01 #13
давайте я покажу, как написал бы сам, а Вы решите для себя, что и как менять.
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
Danila777
0 / 0 / 1
Регистрация: 23.05.2013
Сообщений: 14
26.05.2013, 11:38  [ТС] #14
спасибо.
0
Catstail
Модератор
23540 / 11650 / 2036
Регистрация: 12.02.2012
Сообщений: 18,992
26.05.2013, 12:35 #15
Вот иллюстрация. Выбираем вершины 1 и 7. И сразу по матрице смежности (1 цикл!) убеждаемся, что вершина 4 - та самая...
0
Миниатюры
Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной   Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной  
26.05.2013, 12:35
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.05.2013, 12:35
Привет! Вот еще темы с решениями:

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

Граф (Матрица смежности, список смежности)
Понятия неимею, как можно написать код по условию программы так как с графами не бум бум. Неориентированный граф представляет собой...

Задан неориентированный невзвешенный граф в виде матрицы смежности. Вывести эту матрицу в виде списка ребер
Помогите пожалуйста.задал неориентированный невзвешенный граф в виде матрицы смежности. помогите вывести эту матрицу в виде списка ребер ...

Как преобразовать неориентированный граф в ориентированный граф из матричной записи
Есть ли какой нибудь алгоритм преобразования Неориентированный графа в ориентированный граф из матричной записи?


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru