Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > система фундаментальных циклов

Автор: Inka94 8.4.2012, 15:17

Помогите пожалуйста! Надо написать программу для построения системы фундаментальных циклов.Мыслей ноль вообще,алгоритм примерно такой:
1.Определяем, связан ли граф (Если нет — циклов нет);
2.Строим матрицу смежности остовного дерева графа;
3.Устраиваем цикл по хордам;
4.Выводим список фундаментальных циклов графа.
Вся теперь проблема в реализации...Основная проблема в методе заполнения матрицы остовного дерева графа, заданного матрицей смежности. Есть вариант идти через списки,но т.к я новичок в этом мы это еще не изучали... ну естественно и дальше вся работа не идет.
Кто сталкивался с подобной проблемой помогите! Мож какие идеи есть?

Автор: Inka94 8.4.2012, 16:49

вот начало я тут немного попробовала:

Код



public class Matrix {
public int[]GetMatrixAttainability(){// Метод, возвращающий матрицу достижимости
int[] mtxAtt;int[] mtxFrame;int [] mtxAdj;int vCount;
int[] matrix = (int[])mtxAdj.clone();// Создаем матрицу смежности с рефлексивным отношением
for (int i = 0; i<vCount; i++){
for (int j = 0; j<vCount; j++){
matrix[i][j] = 1; }
mtxAtt = matrix;// Создаем матрицу достижимости как матрицу смежности
for (int i=0;i<vCount;i++)// Запускаем цикл по количеству вершин
{
mtxAtt=Multiplication(mtxAtt,matrix);// Умножаем матрицу достижимости на матрицу смежности
}
for(int i=0;i<vCount;i++){ // "Нормируем" матрицу достижимости
for(int j=0;j<vCount;j++){
if(mtxAtt[i][j]!=0){// Если число матрицы отлично от 0
mtxAtt[i][j] =1;
}}}
return mtxAtt;}
}
public int[] Multiplication (int[]matrix1,int[]matrix2) {
int[] matrix = new int[vCount][vCount];// Создаем новую матрицу
for (int i = 0; i<matrix1.GetLength(0); i++){// Цикл по количеству строк 1 матрицы
for (int j = 0; j<matrix2.GetLength(1); j++){// Цикл по количеству столбцов 2 матрицы
for (int k = 0; k<matrix2.GetLength(0); k++){// Цикл по количеству строк 2 матрицы
matrix[i][j]= matrix1[i][k] * matrix2[k][j];// Получение [i,j] элемента итоговой матрицы
}}}
return matrix;// Возвращаем результат перемножения матриц
}
}

выдает ошибку =(
array required but int found

Автор: GZep 8.4.2012, 19:40

Никто не будет ломать зрение на чтение такого кода.
Оформите по-человечески, тут есть тег код с подсветкой и текст ошибки не забудте.

Автор: Inka94 8.4.2012, 21:52

Цитата(GZep @ 8.4.2012, 19:40)

Сделала.

Автор: toxx 8.4.2012, 21:57

Inka94,
Плохо отформатировали

Автор: Inka94 8.4.2012, 23:24

разобралась в чем прикол.Неправильно задала двумерный массив.Разбила на 2 класса,"связала" между собой.Теперь во втором методе возникает ошибка-"missing return statement"..
вот в общем состояние программы на данный момент.Насчет форматирования текста сори,сил уже больше ни на что нет )
1 класс:

Код


public class Matrix extends Un {
public int[][]GetMatrixAttainability(){// Метод, возвращающий матрицу достижимости
int[][] mtxAtt;int[][] mtxFrame;int [][] mtxAdj;int vCount;
int[][] matrix = (int[][])mtxAdj.clone();// Создаем матрицу смежности с рефлексивным отношением
for (int i = 0; i<vCount; i++){
matrix[i][i]= 1;
}
mtxAtt=matrix;// Создаем матрицу достижимости как матрицу смежности
for (int i = 0; i<vCount; i++) {// Запускаем цикл по количеству вершин
mtxAtt=Multiplication(mtxAtt, matrix);// Умножаем матрицу достижимости на матрицу смежности
}
for(int i=0;i<vCount;i++){ // "Нормируем" матрицу достижимости
for(int j=0;j<vCount;j++){
if(mtxAtt[i][j]!=0){// Если число матрицы отлично от 0
mtxAtt[i][j]=1;
}}}
return mtxAtt;
}}

второй :

Код


public class Un {
public int Multiplication(int[][] matrix1, int[][] matrix2) {
int vCount=0;
int[][] matrixn;
int[][] matrix = new int[vCount][vCount];// Создаем новую матрицу
for (int i = 0; i<matrix1.length; i++){// Цикл по количеству строк 1 матрицы
for (int j = 0; j<matrix2.length; j++){// Цикл по количеству столбцов 2 матрицы
for (int k = 0; k<matrix2.length; k++){// Цикл по количеству строк 2 матрицы
matrix[i][j]+= matrix1[i][k] * matrix2[k][j];// Получение [i,j] элемента итоговой матрицы
}
return matrix[i][j];
}}}}

вот тут и вылетает ошибка :"missing return statement"
голову сломала уже что и как,ничего путного не нашла.

Автор: GZep 8.4.2012, 23:27

Зато теперь хотя бы видно:

Код


int[] matrix;

Код


matrix[i][j] = 1;

Массив matrix декларирован как одномерный, а обращаетесь к нему как к двумерному.

Должно быть вроде такого:

Код


int[][] matrix;
matrix = new int[][];

Добавлено через 3 минуты и 56 секунд

Цитата(Inka94 @ 8.4.2012, 23:24

)

Насчет форматирования текста сори,сил уже больше ни на что нет

на сколько знаю, в современных IDE это делается одной командой.

Цитата(Inka94 @ 8.4.2012, 23:24

)

вот тут и вылетает ошибка :"missing return statement"

да потому что код неотформатированный! был бы отформатированный, увидели бы что в конце неправильно расставлены скобки и return не "внутри" метода. Вот компилятор и ругается, что return выражение найти не может.

Добавлено через 5 минут и 14 секунд
Подсказка: после return должно быть 2 закрывающиеся фигурные скобки.

Автор: Inka94 8.4.2012, 23:33

Оо спасибо )) ща гляну ))

Добавлено через 14 минут и 25 секунд
типа так что ли?

Код


public class Un {
public int Multiplication(int[][] matrix1, int[][] matrix2) {
int vCount=0;
int[][] matrix = new int[vCount][vCount];// Создаем новую матрицу
for (int i = 0; i<matrix1.length; i++){// Цикл по количеству строк 1 матрицы
for (int j = 0; j<matrix2.length; j++){// Цикл по количеству столбцов 2 матрицы
for (int k = 0; k<matrix2.length; k++){// Цикл по количеству строк 2 матрицы
matrix[i][j]+= matrix1[i][k] * matrix2[k][j];// Получение [i,j] элемента итоговой матрицы
}}}
return matrix[i][j];}}

Автор: Mirkes 10.4.2012, 18:21

Цитата(Inka94 @ 8.4.2012, 15:17

)

1.Определяем, связан ли граф (Если нет — циклов нет);

Извините за наивный вопрос, но почему связность графа влечет его ацикличность?

Автор: Inka94 15.4.2012, 01:28

Цитата(Mirkes @ 10.4.2012, 18:21)

Цитата(Inka94 @ 8.4.2012, 15:17

)

1.Определяем, связан ли граф (Если нет — циклов нет);

Извините за наивный вопрос, но почему связность графа влечет его ацикличность?

А что вас смущает?

Автор: Mirkes 15.4.2012, 16:38

Насколько я помню, наличие циклов и связность графов понятия не связанные. Если взять два циклических графа и объединить, то будем иметь циклический несвязный граф. Например. Если вершины 1, 2 и 3 связаны каждый с каждым, то мы имеем цикл. Если вершины 4, 5 и 6 связаны каждый с каждым, то имеем еще один цикл. Граф со всеми шестью вершинами несвязный, но имеет два цикла. Именно это я и имел в виду.
Стало интересно, полез в искать определения. Вообще говоря фундаментальный цикл определяется для произвольного ОСТОВА графа, а не для ОСТОВНОГО ДЕРЕВА. Так что утверждение в пункте 1 - не верно. Если граф не связен, я посовтовал бы разбить его на вязные компоненты и искать фундаментальные циклы в каждой компоненте отдельно. Это намного быстрее. А вот утверждать ацикличность на основании несвязности - грубая ошибка.

Автор: Inka94 7.5.2012, 22:01

Цитата(Mirkes @ 15.4.2012, 16:38)

Ого,я как-то об этом абсолютно не задумывалась...Спасибо большое,что сказали. Это немного меняет алгоритм и вообще почти всю программу на задачу...Даже стыдно,что не обратила внимание.