Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Danila777
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 14
25.05.2013, 21:17     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной #1
народ помогите пожалуйста написать программу на с++ на графы
дана матрица смежности и неориентированный граф.
выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.05.2013, 21:17     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной
Посмотрите здесь:

C++ Неориентированный граф!!!
C++ Дана целочисленная матрица А(М,N) и натуральное число К<М. Выяснить, все ли элементы К-го столбца матрицы А четные
Дана матрица размера MxN. Вывести ее элементы, расположенные в столбцах с нечетными номерами C++
Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности C++
Дана квадратная матрица. Посчитать сумму элементов с четными номерами C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kodzaev
25.05.2013, 21:35
  #2
 Комментарий модератора 
Перемещено из раздела Pascal
Catstail
Модератор
 Аватар для Catstail
21434 / 10219 / 1666
Регистрация: 12.02.2012
Сообщений: 17,092
25.05.2013, 22:22     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной #3
Пусть n и m - номера вершин. Если для какого-либо i != n,m имеет место Matr[i,n] != 0 && Matr[i,m] != 0 - то ответ утвердительный
Danila777
0 / 0 / 0
Регистрация: 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");
    
}
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
26.05.2013, 10:07     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной #5
можно сделать дфс из одной вершины. пометить вершины на этом пути определенным цветом. запустить дфс из второй - если попадешь в помеченную "определенным цветом" вершину, то все ок.
Catstail
Модератор
 Аватар для Catstail
21434 / 10219 / 1666
Регистрация: 12.02.2012
Сообщений: 17,092
26.05.2013, 10:09     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной #6
А зачем ты читаешь из выходного файла (h) и пишешь во входной (g)?

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

Добавлено через 2 минуты
второй дфс, действительно, без надобности. достаточно запустить дфс из любой из двух - если вторая посещена, то все ок.
Catstail
Модератор
 Аватар для Catstail
21434 / 10219 / 1666
Регистрация: 12.02.2012
Сообщений: 17,092
26.05.2013, 10:31     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной #8
Цитата Сообщение от salam Посмотреть сообщение
можно попросить Вас аргументировать свои комментарии?
- пожалуйста. Запускаем dfs (кстати, а чем bfs хуже?) из одной вершины, обойдем весь граф... И даст это ответ на вопрос задачи (есть ли у двух заданных вершин общая смежная, т.е. достижимая из каждой за один шаг)?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
26.05.2013, 10:34     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной #9
у нас разное представление о понятии "соседствуют". автор, проясните, пожалуйста: "соседствуют" это имеют ребра в эту вершину или лежат с ней на одной компоненте связности?
Danila777
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 14
26.05.2013, 10:45  [ТС]     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной #10
да. соседствуют это тогда когда имеют ребра в одну вершину.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
26.05.2013, 10:46     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной #11
Цитата Сообщение от Danila777 Посмотреть сообщение
да. соседствуют это тогда когда имеют ребра в одну вершину.
тогда вариант Catstail единственный корректный.
Danila777
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 14
26.05.2013, 10:52  [ТС]     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной #12
я понимаю. а что в моей проге нитак.
укажите пожалуйста.
и как исправить чтобы было правильно.
помогите пожалуйста.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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;
}
Danila777
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 14
26.05.2013, 11:38  [ТС]     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной #14
спасибо.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.05.2013, 12:35     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной
Еще ссылки по теме:

Проверить, содержит ли заданный неориентированный граф хотя бы один цикл C++
C++ Ввести из файла неориентированный нагруженный граф в список смежности, используя вектор векторов
Неориентированный граф, вывести порядки вершин графа C++

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

Или воспользуйтесь поиском по форуму:
Catstail
Модератор
 Аватар для Catstail
21434 / 10219 / 1666
Регистрация: 12.02.2012
Сообщений: 17,092
26.05.2013, 12:35     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной #15
Вот иллюстрация. Выбираем вершины 1 и 7. И сразу по матрице смежности (1 цикл!) убеждаемся, что вершина 4 - та самая...
Миниатюры
Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной   Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной  
Yandex
Объявления
26.05.2013, 12:35     Дана матрица смежности и неориентированный граф. Выяснить соседствуют ли две вершины с данными номерами с одной общей вершиной
Ответ Создать тему
Опции темы

Текущее время: 22:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru