gpt-4-0314· openai
Suzhen/CodeChat
напиши проверку графа на циклическую зависимость подробно обьясняя каждое действие на c#
- User
напиши проверку графа на циклическую зависимость подробно обьясняя каждое действие на c#
- Assistant
Для проверки графа на циклические зависимости, мы можем использовать алгоритм обхода графа в глубину (DFS) с отслеживанием пройденных и текущих вершин. Если при обходе графа мы вернемся в вершину, которая является частью текущего пути обхода, это указывает на наличие цикла. Вот подробный код на C#:
- Создаем класс
Graphс методом добавления вершины и ребра:
public class Graph { // Список смежности для представления графа private readonly Dictionary<int, List<int>> adjList; public Graph() { adjList = new Dictionary<int, List<int>>(); } // Добавить вершину public void AddVertex(int vertex) { if (!adjList.ContainsKey(vertex)) { adjList[vertex] = new List<int>(); } } // Добавить ребро между вершинами 'from' и 'to' public void AddEdge(int from, int to) { AddVertex(from); AddVertex(to); adjList[from].Add(to); } // Вспомогательный метод для печати графа public void PrintGraph() { foreach (var vertex in adjList.Keys) { Console.Write($"{vertex}: "); Console.WriteLine(string.Join(", ", adjList[vertex])); } } }- Добавляем метод
IsCyclicдля проверки графа на циклическую зависимость:
// Проверка на циклическую зависимость public bool IsCyclic() { var visited = new HashSet<int>(); var currentPath = new HashSet<int>(); foreach (var vertex in adjList.Keys) { if (IsCyclicUtil(vertex, visited, currentPath)) { return true; } } return false; } // Вспомогательный метод для проверки цикла с использованием DFS private bool IsCyclicUtil(int vertex, HashSet<int> visited, HashSet<int> currentPath) { // Если вершина уже пройдена, возвращаем false if (visited.Contains(vertex)) { return false; } // Если вершина находится в текущем пути, возвращаем true if (currentPath.Contains(vertex)) { return true; } // Отмечаем вершину как посещенную и добавляем ее в текущий путь visited.Add(vertex); currentPath.Add(vertex); // Проходим дальше по соседям foreach (var neighbor in adjList[vertex]) { if (IsCyclicUtil(neighbor, visited, currentPath)) { return true; } } // Удаляем вершину из текущего пути после окончания проверки ее соседей currentPath.Remove(vertex); return false; }Теперь мы можем проверить граф на циклическую зависимость следующим образом:
public static void Main(string[] args) { var graph = new Graph(); graph.AddEdge(0, 1); graph.AddEdge(1, 2); graph.AddEdge(2, 3); graph.AddEdge(3, 1); if (graph.IsCyclic()) { Console.WriteLine("Граф содержит циклическую зависимость"); } else { Console.WriteLine("Граф не содержит циклической зависимости"); } }В данном примере граф содержит цикл между вершинами 1, 2 и 3, поэтому вывод будет "Граф содержит циклическую зависимость".
- Создаем класс
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.