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

Вывести все возможные комбинации цепочек в матрице смежности - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Tedorius
 Аватар для Tedorius
7 / 7 / 0
Регистрация: 12.06.2012
Сообщений: 59
07.12.2012, 17:20     Вывести все возможные комбинации цепочек в матрице смежности #1
Есть матрица смежности вида:
AB0
BCD
DD0
CKN
NE0
KB0
Т.е. если в конце строки 0, то из одного узла есть связь только к одному узлу, иначе - к двум.
Задача: вывести все возможные комбинации цепочек.
Результат:
ABDD
ABCKB
ABCNE
Возможно есть очень простой алгоритм решения этой задачи, но вот как я думаю надо делать:
Кроме матрицы смежности, надо создать дополнительную матрицу(для удобства) куда будут записываться те узлы, у которых есть два выхода и создать рекурсивную функцию для нахождения всех цепочек. Цепочки можно записывать в еще одну матрицу.
Код реализации нахождения цепочки выкладывать не буду, ибо он не правильный...выложу оболочку:
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include "stdafx.h"
#include <iostream> 
#include <fstream>
#include <time.h> 
#include <iomanip>
#include <string>
 
using namespace std;
 
int main()
{
    char arr[1000][4];
    char arrPred[1000][4];
    char temp[10];
    char temparr[1000][1000];
    int i=1,j=0,n,m,l=0;
    int k=0,p=0;
    
    system("cls");
    setlocale(LC_ALL,"Rus") ;
    fstream file("data.txt") ;  
    //////////////////////////////
    cout<<"Матрица смежности: \n";
    while(!file.eof())
    {
        
        j++;
        file >> arr[i][j] ; 
 
        if(file.eof())
        {
            break;
        }
        cout << setw(4)<< arr[i][j];
 
        if(j%3==0)
        {           
            j=0;
            i++;    
            cout<<"\n";
        }
                
    }
    ////////////////////////////
    n=i;
    m=3;
    i=0;
    int a=0;
    int b=2;
    temparr[0][0]=arr[1][1];
    temparr[0][1]=arr[1][2];
    temp[0]=temparr[0][1];
    //////////////////////////////////////////////////////
    
    /////////////////////////////////////
    for(int i=1;i<n;i++)// нахождение предикатных узлов
    {
        
        if(arr[i][m]!='0')
        {
            for(int z=0;z<m;z++)
            {
            arrPred[k][z]=arr[i][z+1];
            }
            k++;    
        }
    }
    /////////////////////////////////////
    for(int i=1;i<n;i++)//нахождение цепочек
    {//реализация
                //Примерный алгоритм:
        //если в конце строки 0 то присвоить в матрицу ответов 1 и 2 элемент первой строки матрицы смежности
        //присвоить temp 2й элемент первой строки
        //////1-если temp=первому элементу одной из следующих строк и в этой строке в конце 0
        //присвоить второй элемент строки в матрицу ответов
        //присвоить temp=второй элемент строки
        //////2-если равен и в конце не 0 //рекурсивная функция
        //проверить не является ли 2 и 3 элемент строки предикатным узлом(по дополнительну массиву предикатных узлов)
        //если является то проверить не являются ли в свою очередь выходящие из этого узла элементы предикатными//рекурсия
        //как-то запомнить все цепочки
        //и вывести
        //////3- если не равен - конец цепочки
        }
        ///////////////////////////////////////////////////////
    cout <<"\n\n\n"<< endl ; 
    //////////////////////////////
    system ("pause");
    return 0;
}
Также прикрепляю файл с данными(матрицей смежности).
Вложения
Тип файла: txt data.txt (40 байт, 11 просмотров)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tedorius
 Аватар для Tedorius
7 / 7 / 0
Регистрация: 12.06.2012
Сообщений: 59
07.12.2012, 23:14  [ТС]     Вывести все возможные комбинации цепочек в матрице смежности #2
Неужели никто не может помочь?

Добавлено через 4 часа 42 минуты
Актуально
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
07.12.2012, 23:48     Вывести все возможные комбинации цепочек в матрице смежности #3
Поиск в глубину, не? А наличие повторной строки проверять при помощи добавления map.
Tedorius
 Аватар для Tedorius
7 / 7 / 0
Регистрация: 12.06.2012
Сообщений: 59
08.12.2012, 00:07  [ТС]     Вывести все возможные комбинации цепочек в матрице смежности #4
Это не поиск в глубину, т.к. у меня не дерево и связи могут быть с абсолютно любым узлом.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
08.12.2012, 00:08     Вывести все возможные комбинации цепочек в матрице смежности #5
А почему поиск в глубину и сразу - на дереве? его можно прикрутить много к чему, и не только к деревьям.
Tedorius
 Аватар для Tedorius
7 / 7 / 0
Регистрация: 12.06.2012
Сообщений: 59
08.12.2012, 00:09  [ТС]     Вывести все возможные комбинации цепочек в матрице смежности #6
В этом и заключается проблема. Мне надо остановить цепочку если узел уже описывался.

Добавлено через 31 секунду
Ну помогите с реализацией тогда =)
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
08.12.2012, 00:12     Вывести все возможные комбинации цепочек в матрице смежности #7
А какие ограничения на количество вершин?
Tedorius
 Аватар для Tedorius
7 / 7 / 0
Регистрация: 12.06.2012
Сообщений: 59
08.12.2012, 00:15  [ТС]     Вывести все возможные комбинации цепочек в матрице смежности #8
Вы имеете в виду количество выходов из вершины? тогда два. Если имеете в виду общее количество вершин, то сколько угодно.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
08.12.2012, 00:15     Вывести все возможные комбинации цепочек в матрице смежности #9
Сколько угодно? Многовато.
Tedorius
 Аватар для Tedorius
7 / 7 / 0
Регистрация: 12.06.2012
Сообщений: 59
08.12.2012, 00:17  [ТС]     Вывести все возможные комбинации цепочек в матрице смежности #10
Ну скажем 20. Разве это имеет значение? Мы же просто задаем в матрице смежности связи и проходим по ней.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.12.2012, 00:19     Вывести все возможные комбинации цепочек в матрице смежности
Еще ссылки по теме:

C++ Найти все возможные комбинации по номеру карты
C++ Вывести все возможные комбинации трех натуральных чисел x, y и z до 36 с определенными условиями
Все возможные комбинации из 10 цифр по n C++

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

Или воспользуйтесь поиском по форуму:
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
08.12.2012, 00:19     Вывести все возможные комбинации цепочек в матрице смежности #11
Tedorius, 20? Это меняет дело.
Как можно сделать (версия для маленьких значений): на первое место в исходной строке ставим всевозможные вершины, на второе - не посещенного ранее соседа первой вершины и т.д.
Yandex
Объявления
08.12.2012, 00:19     Вывести все возможные комбинации цепочек в матрице смежности
Ответ Создать тему
Опции темы

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