Исходник поиска фундаментальных графов


Добавил:DMT
Дата создания:25 апреля 2008, 12:53
Дата обновления:25 апреля 2008, 12:53
Просмотров:5224 последний позавчера, 16:45
Комментариев: 0
Исходник поиска фундаментальных графов
Код на C++
  1. #include <conio.h>
  2. #include <stdio.h>
  3. #include <iostream.h>
  4. #include <stdlib.h>
  5.  
  6. #define SIZE1 8
  7. #define SIZE2 5
  8. #define FILENAME "result.txt"
  9.  
  10. FILE *out;
  11.  
  12. int index, // индекс в стеке
  13. Stack[SIZE1], // Стек
  14. Number, // Количество выводимых строк
  15. WGN[SIZE1], // массив закраски
  16. Record[SIZE1][SIZE2] = {{1, 3, 6, -1, -1}, // Граф, заданный списком
  17. {0, 3, 4, 6, -1}, // инцендентности
  18. {5, 7, -1, -1, -1},
  19. {0, 1, 6, -1, -1},
  20. {1, 6, 7, -1, -1},
  21. {2, 7, -1, -1, -1},
  22. {0, 1, 3, 4, -1},
  23. {2, 4, 5, -1, -1}},
  24. Styag[7][2] = {{0, 1}, // Ребра стягивающего дерева
  25. {1, 3},
  26. {1, 4},
  27. {4, 6},
  28. {4, 7},
  29. {7, 2},
  30. {2, 5}};
  31.  
  32. //Функция поиска фундаментальнх графов
  33. void Search(int v)
  34. {
  35. int u, // содержит значение u
  36. flag; // Флаг отсеивания лишнего
  37. Stack[index] = v; // Помещаем в стек значение
  38. WGN[v] = 1; // закрашиваем вершину
  39. index++; // увеличиваем индекс стека
  40.  
  41. // проходим по всем вершинам связанным с вершиной v
  42. for(int i = 0; i < SIZE2 && Record[v][i] != -1; i++)
  43. {
  44. u = Record[v][i]; // получаем вершину u из строки
  45. if (WGN[u] == -1) // Если вершина не использовалась
  46. Search(u); // переходим на строку u в списке инцендентности
  47. else
  48. {
  49. // 1-е: в цикле минимум 3 вершины должно быть
  50. // 2-е: новый элемент должен быть началом цикла
  51. // тогда цикл найден
  52. if ((index - 3 >= 0) && (u == Stack[0]))
  53. {
  54. flag = 0;
  55. for(int c = 1; c < index; c++)
  56. for(int w = 0; w < 7; w++)
  57. if((Stack[c-1] == Styag[w][0] && Stack[c] == Styag[w][1]) ||
  58. (Stack[c] == Styag[w][0] && Stack[c-1] == Styag[w][1]))
  59. flag++;
  60. for(int w = 0; w < 7; w++)
  61. if((Stack[0] == Styag[w][0] && Stack[index-1] == Styag[w][1]) ||
  62. (Stack[index-1] == Styag[w][0] && Stack[0] == Styag[w][1]))
  63. flag++;
  64.  
  65. if(index - 1 != flag)
  66. break;
  67.  
  68. // выводим содержимое стека
  69. fprintf(out, "Ребро: ");
  70. cout<<endl<<"Ребро: ";
  71. for(int j = 0; j < index; j++)
  72. {
  73. cout<<Stack[j]<<" ";
  74. fprintf(out, "%i ", Stack[j]);
  75. }
  76. fprintf(out, "\n");
  77. Number++;
  78. if(Number == 22)
  79. {
  80. cout<<endl<<endl<<"Нажмите кнопку для продолжения.";
  81. getch();
  82. Number = 0;
  83. clrscr();
  84. }
  85. // отсечение не фундаментальных циклов
  86. break;
  87. }
  88. }
  89. }
  90. index--; // очищение стека путем уменьшения индекса
  91. WGN[v] = -1; // высвобождение вершины от краски
  92. }
  93.  
  94. void main(void)
  95. {
  96. int i, j;
  97. clrscr();
  98. out = fopen(FILENAME, "wt");
  99.  
  100. // инициализация и обнуление данных
  101. for(i = 0; i < SIZE1; i++)
  102. {
  103. index = 0;
  104. Stack[i] = WGN[i] = -1;
  105. }
  106. Number = 0;
  107.  
  108. // начало поиска
  109. for(i = 0; i < SIZE1; i++)
  110. if (WGN[i] == -1)
  111. Search(i);
  112. getch();
  113. fclose(out);
  114. }
При использовании обязательна ссылка на http://DMTSoft.ru
up