Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// <summary>
- /// Немного измененная функция алгоритма Дейкстры.
- /// </summary>
- /// <param name="adjacencyMatrix">матрица смежности</param>
- /// <param name="matrixSize">размер матрицы</param>
- /// <param name="srcVertex">стартовая вершина</param>
- /// <param name="destVertex">конечная вершина</param>
- /// <param name="visited">булевый массив посещенности вершин</param>
- /// <param name="visitedCount">количество посещенных вершин</param>
- /// <param name="neededVertexes">посещенные ребра</param>
- private void Dijkstra(int[,] adjacencyMatrix, int matrixSize, int srcVertex, int destVertex, bool[] visited, int visitedCount, ref int neededVertexes)
- {
- for (int i = 0; i < matrixSize; i++)
- {
- if (adjacencyMatrix[srcVertex, i] != 0 && !visited[i])
- {
- if (i == destVertex && neededVertexes < visitedCount + 1)
- neededVertexes = visitedCount + 1;
- else
- {
- visited[i] = true;
- Dijkstra(adjacencyMatrix, matrixSize, i, destVertex, visited, visitedCount + adjacencyMatrix[srcVertex, i], ref neededVertexes);
- visited[i] = false;
- }
- }
- }
- }
- /// <summary>
- /// Возвращает минимальное количество дуг, с которыми орграф остается сильно связным.
- /// </summary>
- /// <param name="matrix">матрица смежности</param>
- /// <returns>минимальное количество дуг, с которыми орграф остается сильно связным</returns>
- private int GetNeededEdges(int[,] matrix)
- {
- int matrixSize = matrix.GetLength(0);
- int[] counts = new int[matrixSize];
- bool[] visited = new bool[matrixSize];
- visited[0] = true;
- for (int i = 0; i < matrixSize; i++)
- for (int j = 0; j < matrixSize; j++)
- Dijkstra(matrix, matrixSize, i, j, visited, 0, ref counts[i]);
- return counts.Max() + 1;
- }
- /// <summary>
- /// Возвращает количество дуг для данной матрицы смежности, не учитывая петли.
- /// </summary>
- /// <param name="matrix">матрица смежности</param>
- /// <returns>количество дуг</returns>
- private int GetEdgeCount(int[,] matrix)
- {
- int edgeCount = 0;
- for (int i = 0; i < matrix.GetLength(0); i++)
- for (int j = 0; j < matrix.GetLength(1); j++)
- if (matrix[i, j] == 1 && i != j)
- edgeCount++;
- return edgeCount;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement