[코딩인터뷰] 문제 4.2

문제 4.2

Solutions.Library

	#region Question 4.2
	/*
	* 주어진 유향 그래프(directed graph)에서 특정한 두 노드 간에 경로(route)가 존재하는지를 판별하는 알고리즘을 구현하라.
	*/
	public static bool Q2_Search<T>(Graph<T> graph, GraphNode<T> start, GraphNode<T> end)
	{
	var nodeList = new LinkedList<GraphNode<T>>();
	// 모든 노드의 방문 상태를 초기화
	foreach (var node in graph.Nodes)
	{
	node.State = GraphNodeState.Unvisited;
	}
	//시작 노드 설정
	start.State = GraphNodeState.Visiting;
	nodeList.AddLast(start);
	// 그래프 너비 우선 탐색 시작
	while (nodeList.Count != 0)
	{
	var unvisited = nodeList.First.Value;
	nodeList.RemoveFirst();
	if (unvisited != null)
	{
	// 인접 노드 확인
	foreach (var adjacentNode in unvisited.Adjacent)
	{
	// 인접 노드를 방문하지 않은 상태인지 확인
	if (adjacentNode.State == GraphNodeState.Unvisited)
	{
	// 원하던 목적지에 도달
	if (adjacentNode == end)
	{
	return true;
	}
	else
	{
	// 현재 방문중인 인접 노드의 인접 노드를 추가
	adjacentNode.State = GraphNodeState.Visiting;
	nodeList.AddLast(adjacentNode);
	}
	}
	}
	// 모든 인접 노드를 확인하여 방문 완료 마킹
	unvisited.State = GraphNodeState.Visited;
	}
	}
	return false;
	}
	/* C# 8.0 버전에는 지원될 수도?
	* 그래프 노드의 속성을 확장하는 방법이 좀더 객체지향적인 설계
	public extension GraphNodeState extends GraphNode { }
	*/
	#endregion

view raw Code_Q4_2.cs hosted with ❤ by GitHub

	[TestMethod]
	public void Q4_2()
	{
	var nodes = new Collection<GraphNode<string>>()
	{
	new GraphNode<string>("a"),
	new GraphNode<string>("b"),
	new GraphNode<string>("c"),
	new GraphNode<string>("d"),
	new GraphNode<string>("e"),
	new GraphNode<string>("f"),
	};
	nodes[0].Adjacent.Add(nodes[1]);
	nodes[0].Adjacent.Add(nodes[2]);
	nodes[3].Adjacent.Add(nodes[4]);
	nodes[4].Adjacent.Add(nodes[5]);
	var graph = new Graph<string>(nodes);
	Assert.IsTrue(TreeGraph.Q2_Search(graph, nodes[3], nodes[5]));
	Assert.IsFalse(TreeGraph.Q2_Search(graph, nodes[0], nodes[5]));
	}

view raw Test_Q4_2.cs hosted with ❤ by GitHub