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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Pomogi
0 / 0 / 0
Регистрация: 26.12.2012
Сообщений: 14
#1

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

03.11.2013, 01:39. Просмотров 1073. Ответов 6
Метки нет (Все метки)

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.
Вот начало
#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++ K-связность неориентированного графа
Обход неориентированного графа в глубину C++
Обход неориентированного графа в ширину. В конце выдаёт путь: 1 C++
C++ Найти множество фундаментальных циклов связного неориентированного графа
C++ Поиск кратчайших путей из одного источника для неориентированного графа
Найти максимальное и среднее расстояние между центральными вершинами неориентированного графа C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Модератор
Эксперт CЭксперт С++
7162 / 4328 / 631
Регистрация: 29.11.2010
Сообщений: 11,750
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
03.11.2013, 11:41     Напишите алгоритм вывода списка ребер неориентированного графа #3
хорошее начало.
Pomogi
0 / 0 / 0
Регистрация: 26.12.2012
Сообщений: 14
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
Модератор
Эксперт CЭксперт С++
7162 / 4328 / 631
Регистрация: 29.11.2010
Сообщений: 11,750
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
_
201 / 145 / 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++
C++ Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины
C++ Реализуйте представление дерево в виде списка ребер в С++

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

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

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