C#
자료구조 : 그래프 (Graph)

그래프(Graph)는 노드(꼭지점, Vertex)과 변(Edge)로 구성되어 있는 자료 구조로서 트리와 다르게 사이클(Cycle)을 허용한다. Edge 에 방향을 허용하느냐 마느냐에 따라서 방향이 있는 그래프(Directed Graph), 혹은 방향이 없는 그래프(Undirected Graph)로 나눌 수 있다. 또한 각 변에 가중치(Weight)를 주어 노드와 노드 사이에 숫자로 거리, 비용등의 관계를 표현할 수 있다. 일반적으로 Graph 자료구조는 인접리스트(Adjacency List)나 인접 행렬 (Adjacency Matrix) 등의 방법으로 표현한다. 그래프는 도시간 최단 행로를 구하거나 웹 링크 연결도를 표현하는 등 여러 종류의 자료를 표현하는데 사용될 수 있다.



C#으로 간단한 그래프 구현

.NET Framework은 그래프와 관련된 클래스를 제공하지 않는다. 그래프를 구현하는 한 방식으로 아래 코드는 각 노드마다 인접한 노드들의 리스트를 가지고 있는 인접리스트(Adjacency List)를 사용하고 있다. Graph클래스는 GraphNode들을 갖는 리스트를 기본 필드로 갖고 있으며, 각 GraphNode는 데이타 (혹은 키+데이타) 필드와 인접 노드 리스트를 기본적인 필드로 가지고 있다. GraphNode는 필요에 따라 Weight 배열을 가질 수 있는데, 이는 각 변(Edge)의 가중치를 저장할 필요가 있을 때 사용된다.

예제

// GraphNode 클래스
public class GraphNode<T>
{
    private List<GraphNode<T>> _neighbors;
    private List<int> _weights;

    public T Data { get; set; }

    public GraphNode()
    {                
    }

    public GraphNode(T value)
    {
        this.Data = value;
    }

    public List<GraphNode<T>> Neighbors
    {
        get
        {
            _neighbors = _neighbors ?? new List<GraphNode<T>>();
            return _neighbors;
        }
    }

    public List<int> Weights
    {
        get 
        { 
            _weights = _weights ?? new List<int>();
            return _weights;
        }
    }
}

// Graph 클래스
public class Graph<T>
{
    private List<GraphNode<T>> _nodeList;

    public Graph()
    {
        _nodeList = new List<GraphNode<T>>();
    }

    public GraphNode<T> AddNode(T data)
    {
        GraphNode<T> n = new GraphNode<T>(data);
        _nodeList.Add(n);
        return n;
    }

    public GraphNode<T> AddNode(GraphNode<T> node)
    {
        _nodeList.Add(node);
        return node;
    }

    public void AddEdge(GraphNode<T> from, GraphNode<T> to, bool oneway=true, int weight=0)
    {            
        from.Neighbors.Add(to);
        from.Weights.Add(weight);
            
        if (!oneway)
        {
            to.Neighbors.Add(from);
            to.Weights.Add(weight);
        }
    }

    internal void DebugPrintLinks()
    {
        foreach (GraphNode<T> graphNode in _nodeList)
        {                
            foreach (var n in graphNode.Neighbors)
            {
                string s = graphNode.Data + " - " + n.Data;
                Console.WriteLine(s);
            }                
        }
    }
}

// Graph 테스트
internal class Program
{
    private static void Main(string[] args)
    {
        Graph<int> g = new Graph<int>();
        var n1 = g.AddNode(10);
        var n2 = g.AddNode(20);
        var n3 = g.AddNode(30);
        var n4 = g.AddNode(40);
        var n5 = g.AddNode(50);

        g.AddEdge(n1, n3);
        g.AddEdge(n2, n4);
        g.AddEdge(n3, n4);
        g.AddEdge(n3, n5);

        g.DebugPrintLinks();
    }
}




본 웹사이트는 광고를 포함하고 있습니다. 광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.




Comment demoronator@*** 11/2/2016 2:54:10 AM
Comment admin@*** 11/2/2016 4:52:35 AM
Comment hanlziggy@*** 4/7/2017 2:48:47 PM
Comment admin@*** 4/7/2017 7:47:07 PM