#c#
#c#
Вопрос:
Я пытаюсь создать метод DFS, в котором пользователь вводит начальный узел, и метод будет отображать все узлы, которые могут быть достигнуты с этого начального узла.
Проблема, с которой я сталкиваюсь, заключается в том, что мой метод DFS всегда возвращает начальный узел.
Я использовал следующий пример в main методе.
Класс GraphNode
public class GraphNode<T>
{
private T id;
private LinkedList<T> adjList;
// constructor
public GraphNode(T id)
{
this.id = id;
adjList = new LinkedList<T>();
}
public T ID
{
get { return id; }
set { id = value; }
}
public void AddEdge(GraphNode<T> to)
{
adjList.AddLast(to.ID);
}
public void RemoveEdge(GraphNode<T> to)
{
adjList.Remove(to.ID);
}
public LinkedList<T> GetAdjList()
{
return adjList;
}
}
Класс Graph (содержащий метод DFS)
public class Graph<T> where T : IComparable
{
private LinkedList<GraphNode<T>> nodes;
public Graph()
{
nodes = new LinkedList<GraphNode<T>>();
}
public bool IsEmptyGraph()
{
return nodes.Count == 0;
}
public int NumNodesGraph()
{
//LinkedList<T> currentNodes;
LinkedList<T> nodeCounterList = new LinkedList<T>();
// to be completed
foreach (GraphNode<T> n in nodes)
{
nodeCounterList.AddFirst(n.ID);
}
return nodeCounterList.Count;
}
public int NumEdgesGraph()
{
LinkedList<T> edgeCounterList = new LinkedList<T>();
int numberOfEdges = 0;
foreach (GraphNode<T> n in nodes)
{
edgeCounterList = n.GetAdjList();
for(int i = 0; i < edgeCounterList.Count; i )
{
numberOfEdges ;
}
}
return numberOfEdges;
}
public bool ContainsGraph(GraphNode<T> node)
{
foreach (GraphNode<T> n in nodes)// iterate through all nodes in a graph
{
if (n.ID.CompareTo(node.ID) == 0)
return true;
}
return false;
}
public bool IsAdjacent(GraphNode<T> from, GraphNode<T> to)
{
foreach (GraphNode<T> n in nodes)
{
if (n.ID.CompareTo(from.ID) == 0)
{
bool b = from.GetAdjList().Contains(to.ID);
if (b == true)
return true;
}
}
return false;
}
public void AddNode(T id)
{
nodes.AddLast(new GraphNode<T>(id));
}
public GraphNode<T> GetNodeByID(T id)
{
foreach (GraphNode<T> n in nodes)
{
if (id.CompareTo(n.ID) == 0)
{
return n;
}
}
return null;
}
public void AddEdge(T from, T to)
{
GraphNode<T> n1 = GetNodeByID(from);
GraphNode<T> n2 = GetNodeByID(to);
if (n1 != null amp;amp; n2 != null)
{
n1.AddEdge(n2);
}
else
{
Console.WriteLine("Nodes not found; no edge added");
}
}
public void RemoveEdge(T from, T to)
{
GraphNode<T> n1 = GetNodeByID(from);
GraphNode<T> n2 = GetNodeByID(to);
if (n1 != null amp;amp; n2 != null)
{
n1.RemoveEdge(n2);
}
else
{
Console.WriteLine("Nodes not found; no edge added");
}
}
public void DepthFirstTraverse(T startID, ref List<T> visited)
{
LinkedList<T> adj;
Stack<T> toVisit = new Stack<T>();
GraphNode<T> current = new GraphNode<T>(startID);
toVisit.Push(startID);
while(toVisit.Count != 0)
{
current.ID = toVisit.Pop();
visited.Add(current.ID);
adj = current.GetAdjList();
foreach (T n in adj)
{
if (toVisit.Contains(n) == false amp;amp; visited.Contains(n) == false)
{
toVisit.Push(n);
}
}
}
foreach(Object s in visited)
{
Console.WriteLine(s " ");
}
}
}
тестирование основного метода
static void Main(string[] args)
{
Graph<char> myGraph = new Graph<char>();
myGraph.AddNode('A');
myGraph.AddNode('B');
myGraph.AddNode('C');
myGraph.AddNode('D');
myGraph.AddNode('E');
myGraph.AddNode('F');
myGraph.AddNode('G');
myGraph.AddEdge('B', 'A');
myGraph.AddEdge('A', 'C');
myGraph.AddEdge('A', 'F');
myGraph.AddEdge('A', 'G');
myGraph.AddEdge('C', 'F');
myGraph.AddEdge('C', 'D');
myGraph.AddEdge('F', 'E');
List<char> visited = new List<char>();
myGraph.DepthFirstTraverse('B', ref visited);
}
Комментарии:
1. Разве вы не должны делать
current = GetNodeById(toVisit.Pop());, потому что в противном случае вы просто устанавливаете идентификатор, и список пуст. Также я бы сделалvistedHashSet<T>
Ответ №1:
Основная проблема, вероятно, заключается в вашем методе DFS, в котором вы создаете новый GraphNode с ID = strartID вместо того, чтобы использовать тот, который находится на графике, но этот новый узел не относится к вашему графику, действительно, на самом деле, это новый график, попробуйте заменить вашу строку GraphNode<T> current = new GraphNode<T>(startID); на GraphNode<T> current = this.GetNodeByID(startID); в этомтаким образом, вы берете узел графика с идентификатором, равным startId, у которого есть несколько других подключенных узлов. Ниже исправленный код:
public void DepthFirstTraverse(T startID, ref List<T> visited)
{
LinkedList<T> adj;
Stack<T> toVisit = new Stack<T>();
GraphNode<T> current;
toVisit.Push(startID);
while(toVisit.Count != 0)
{
//OLD
//current.ID = toVisit.Pop();
//NEW
current = this.GetNodeByID(toVisit.Pop());
visited.Add(current.ID);
adj = current.GetAdjList();
foreach (T n in adj)
{
if (toVisit.Contains(n) == false amp;amp; visited.Contains(n) == false)
{
toVisit.Push(n);
}
}
}
foreach(Object s in visited)
{
Console.WriteLine(s " ");
}
}
Редактировать:
Я забыл обновить текущий узел, изменив с current.ID = toVisit.Pop(); на current = this.GetNodeByID(toVisit.Pop());
Комментарии:
1. Это все равно не сработает, потому
current.Id = toVisit.Pop()что просто изменяет идентификатор и фактически не получает узел, связанный с идентификатором, и вы просто просматриваете список начальных узлов соседних узлов снова и снова.2. Вы правы, спасибо. Я забыл обновить текущий узел. Я только что отредактировал приведенный выше код. — Я пробовал с двухуровневым графиком и, похоже, работает, достигая каждого узла, прямо или косвенно связанного с основным
3. И вам действительно больше не нужно
GraphNode<T> current = this.GetNodeByID(startID);, так как он снова будет искать узел в начале цикла.4. @juharr Спасибо за вашу помощь, это сработало, теперь я пытаюсь найти материнскую вершину графика. У вас есть представление о том, как с этим справиться? Я знаю, что это будет метод типа generic list:
public List<T> mothervertex()