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

Напишите алгоритм вывода списка ребер неориентированного графа - C++

Восстановить пароль Регистрация
 
Pomogi
0 / 0 / 0
Регистрация: 26.12.2012
Сообщений: 13
03.11.2013, 01:39     Напишите алгоритм вывода списка ребер неориентированного графа #1
Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.
Вот начало
#include <iostream>

using namespace std;

int main()
{
int k[100][100],n,i,j;
cin>>n;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
cin>>k[i][j];}}
Миниатюры
Напишите алгоритм вывода списка ребер неориентированного графа  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2013, 01:39     Напишите алгоритм вывода списка ребер неориентированного графа
Посмотрите здесь:

C++ Поиск кратчайших путей из одного источника для неориентированного графа
C++ Представление графа в виде списка вершин.
Найти максимальное и среднее расстояние между центральными вершинами неориентированного графа C++
C++ По заданной квадратной матрице из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа
Обход неориентированного графа в ширину. В конце выдаёт путь: 1 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
03.11.2013, 09:46     Напишите алгоритм вывода списка ребер неориентированного графа #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
int main()
{
    int N;
    std::cin >> N;
    bool **A = new bool*[N];
    for (int i=0; i < N; i++)
    {
        A[i] = new bool[N];
        for (int j=0; j < N; j++)
            std::cin >> A[i][j];
    }
    for (int i=0; i < N; i++)
    {
        for (int j=i+1; j < N; j++)
            if (A[i][j])
                std::cout << i+1 << " " << j+1 << std::endl;
        delete[] A[i];
    }
    delete[] A;
}
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
03.11.2013, 11:41     Напишите алгоритм вывода списка ребер неориентированного графа #3
хорошее начало.
Pomogi
0 / 0 / 0
Регистрация: 26.12.2012
Сообщений: 13
03.11.2013, 14:44  [ТС]     Напишите алгоритм вывода списка ребер неориентированного графа #4
Цитата Сообщение от MrGluck Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
int main()
{
    int N;
    std::cin >> N;
    bool **A = new bool*[N];
    for (int i=0; i < N; i++)
    {
        A[i] = new bool[N];
        for (int j=0; j < N; j++)
            std::cin >> A[i][j];
    }
    for (int i=0; i < N; i++)
    {
        for (int j=i+1; j < N; j++)
            if (A[i][j])
                std::cout << i+1 << " " << j+1 << std::endl;
        delete[] A[i];
    }
    delete[] A;
}
спасибо, а чтобы изменилось если это будет ориентированый граф?
а заданая матрица например
0 1 0
0 0 1
1 1 0
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
03.11.2013, 14:51     Напишите алгоритм вывода списка ребер неориентированного графа #5
Цитата Сообщение от Pomogi Посмотреть сообщение
спасибо, а чтобы изменилось если это будет ориентированый граф?
надо было бы сначала считывать дуги куда-нибудь, а потом удалять из них дубликаты. Внутренний цикл был бы
C++
1
2
for (int j=1; j < N; j++)
    if (A[i][j]  && i != j) // при i == j мы допускаем петли
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
03.11.2013, 16:12     Напишите алгоритм вывода списка ребер неориентированного графа #6
Цитата Сообщение от Pomogi Посмотреть сообщение
спасибо, а чтобы изменилось если это будет ориентированый граф
так программа же его и считывает
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2013, 22:00     Напишите алгоритм вывода списка ребер неориентированного графа
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
03.11.2013, 22:00     Напишите алгоритм вывода списка ребер неориентированного графа #7
Цитата Сообщение от ya_noob Посмотреть сообщение
так программа же его и считывает
вначале был неориентированный граф. У него дуги двунаправленные.
Yandex
Объявления
03.11.2013, 22:00     Напишите алгоритм вывода списка ребер неориентированного графа
Ответ Создать тему
Опции темы

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