0

Нужно реализовать BFS, DFS и определить связность через матрицу смежности (то есть не используя списки!) Есть, набросок

public class Edge
{
    public Vertex From { get; set; }
    public Vertex To { get; set; }
    public int Weight { get; set; }
    public Edge(Vertex from, Vertex to, int weight = 1)
    {
        From = from;
        To = to;
        Weight = weight;
    }
    public override string ToString()
    {
        return $"({From};{To})";
    }
}
public class Vertex
{
    public int Number { get; set; }
    public bool visited { get; set; }
    public Vertex prev;
    public Vertex(int number)
    {
        Number = number;
    }

    public override string ToString()
    {
        return $"({Number})";
    }
}
class Graph
{
    public List<Vertex> Vertexes = new List<Vertex>();
    List<Edge> Edges = new List<Edge>();
    public int VertexCount => Vertexes.Count;
    public int EdgeCount => Edges.Count;
    Queue<Vertex> Q = new Queue<Vertex>();
    public void AddVertex(Vertex vertex)
    {
        Vertexes.Add(vertex);

    }
    public bool AddEdge(Vertex from, Vertex to)
    {
        Edge edge = new Edge(from, to);
        if (Edges.Contains(edge)) return false;
        Edges.Add(edge);
        return true;
    }
    public int[,] GetMatrix()
    {
        var matrix = new int[Vertexes.Count, Vertexes.Count];
        foreach (var edge in Edges)
        {
            var row = edge.From.Number - 1;
            var column = edge.To.Number - 1;
            matrix[row, column] = edge.Weight;
        }
        return matrix;
    }
    public void PrintPath(Vertex s, Vertex v)
    {
        if (v == s)
        {
            Console.WriteLine(s);
        }
        else
        {
            if (v.prev == null)
            {
                Console.WriteLine("Пути из s в v нет");
            }
            else
            {
                PrintPath(s, v.prev);
                Console.WriteLine(v);
            }
        }

    }

    public void DFS(Vertex start)
    {
        start.visited = true;
        var matrix = new int[Vertexes.Count, Vertexes.Count];
        for (int i = 0; i < Vertexes.Count; i++)
        {
            Vertex v = Edge.To;
            var index = GetIndex(v);
            if (matrix[index][i] == 1 && (!v.visited))
            {
                DFS(i, v);
            }
        }

    }
    public void BFS(Vertex start)
    {
        Q.Enqueue(start);
        start.visited = true;
        var matrix = new int[Vertexes.Count, Vertexes.Count];
        while (Q.Count > 0) 
        {
            Vertex v = Q.Dequeue();
            var index= Vertexes.IndexOf(v);
            for (int i = 0; i < Vertexes.Count; i++)
            {
                    if (matrix[index, i] == 1)
                    {
                    Q.Enqueue(v); 
                    }
            }
        }
    }
}
8
  • Что именно не получается?
    – aepot
    13 июн 2021 в 9:59
  • Сделать рабочий BFS и DFS 14 июн 2021 в 17:19
  • Нет, я не про это спрашивал.
    – aepot
    14 июн 2021 в 17:20
  • BFS и DFS не отмечает посещенные вершины 14 июн 2021 в 18:32
  • - У меня не работает - Что не работает? - Ничего не работает! - А надо что? - А надо чтобы работало!
    – aepot
    14 июн 2021 в 18:35

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Посмотрите другие вопросы с метками или задайте свой вопрос.