Посчитать количество компонент связности графа
Нужно посчитать количество компонент связности графа (метод connected в классе Graph) с помощью матрицы смежности, но он постоянно выводит цифру 2, как исправить?
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
{
List<Vertex> Vertexes = new List<Vertex>();
List<Edge> Edges = new List<Edge>();
public int VertexCount => Vertexes.Count;
public int EdgeCount => Edges.Count;
public void AddVertex(Vertex vertex)
{
Vertexes.Add(vertex);
}
public void AddEdge(Vertex from, Vertex to)
{
var edge = new Edge(from, to);
Edges.Add(edge);
}
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 List<Vertex> GetVetexLists(Vertex vertex)
{
var result = new List<Vertex>();
foreach (var edge in Edges)
{
if (edge.From == vertex)
{
result.Add(edge.To);
}
}
return result;
}
public void DFS(Vertex cur)
{
var list = new List<Vertex>
{
cur
};
cur.visited = true;
for (int i = 0; i < list.Count; i++)
{
var vertex = list[i];
foreach (var v in GetVetexLists(vertex))
{
if (!v.visited)
DFS(v);
}
}
}
public int Connected()
{
int cnt = 0;
while (true)
{
foreach (Vertex v in Vertexes)
{
if (!v.visited)
{
DFS(v);
++cnt;
}
}
return cnt;
}
}
public bool Wave(Vertex start, Vertex finish)
{
var list = new List<Vertex>
{
start
};
for (int i = 0; i < list.Count; i++)
{
var vertex = list[i];
foreach (var v in GetVetexLists(vertex))
{
if (!list.Contains(v))
{
list.Add(v);
}
}
}
return list.Contains(finish);
}
}
}