0402 그래프

그래프는 루트 노드와 부모 자식 개념이 없다.
그래프는 네트워크 모델을 표현하는 구죠
연결이 단절된 부분 그래드들의 집합으로 구성 가능

정점(vertex)과 간선(edge)으로 구성
정점=그래프 노드
간선=노드를 연결하는 라인
그래프 G=(V,E)

가중치 = 한 정점에서 다른 정검으로 가는 간선에 할당된 비용
인접 정점 = adjacent vertex
부분 그래프 = 한 그래프의 부분 영역을 가리키는 것으로 정점과 간선
집합의 부분 집합
방향 그래프 = 간선이 방향을 가지는 그래프
무방향 그래프 = 간선이 양방향
차수 = 한 노드에 연결된 노드 정점들의 수
진입 차수 = 방향 그래프에서 밖에서 들어오는 간선의 수
진출 차수 = 방향 그래프에서 밖으로 나가는 간선의 수
경로 = 간선으로 연결된 정덤들을 순서대로 나열
단순 경로 = 경로 상에 존재하는 모든 정점이 서로 다른 경로
경로 길이 = 경로를 구성하는데 사용된 간선의 수

public class Node
    {
        public string data;
        public List<Node> Neighbors { get; private set; }

        public List<int> Weights { get; private set; }

        public Node(string data) 
        {
            this.Neighbors = new List<Node>();
            this.Weights = new List<int>();
            this.data= data;
        }
    }

public class Graph
    {
        public List<Node> nodes;
        public bool directed;
        public Graph(bool directed = false)
        {
            this.nodes = new List<Node>();
            this.directed = directed;
        }
        //정점 추가
        public void AddVertex(Node node) 
        {
            this.nodes.Add(node);
        }

        //간선 추가
        public void AddEdge(Node from, Node to, int weight=1) 
        {
            from.Neighbors.Add(to);
            from.Weights.Add(weight);
            if (!this.directed) 
            {
                to.Neighbors.Add(from);
                to.Weights.Add(weight);
            }
        }
        
        //출력
        public void Print() 
        {
            foreach (var vertex in this.nodes) 
            {
                var count = vertex.Neighbors.Count;
                for (int i = 0; i < count; i++) 
                {
                    Console.WriteLine("{0}--{1}--{2}", vertex.data, vertex.Weights[i], vertex.Neighbors[i].data);
                }
            }
        }
    }

public class App
    {
        public App()
        {
            Console.WriteLine("App");

            Graph graph = new Graph();
            
            //정점 추가
            var seoul = new Node("서울");
            graph.AddVertex(seoul);
            var daejoen = new Node("대전");
            graph.AddVertex(daejoen);
            var deaku = new Node("대구");
            graph.AddVertex(deaku);
            var busan = new Node("부산");
            graph.AddVertex(busan);
            var krandreoung = new Node("강릉");
            graph.AddVertex(krandreoung);

            //간선 연결
            graph.AddEdge(seoul, krandreoung, 10);
            graph.AddEdge(seoul, deaku, 7);
            graph.AddEdge(seoul, daejoen, 6);
            graph.AddEdge(deaku, busan, 3);
            graph.AddEdge(daejoen, busan, 7);
            graph.AddEdge(krandreoung, deaku, 7);

            graph.Print();
        }
    }

 

dictionary로 그래프 구현

public class Graph
    {
        //컬랙션
        private Dictionary<string, List<Node>> dic;
        public Graph() 
        {
            this.dic = new Dictionary<string, List<Node>>();
        }
        public void AddVertex(string key) 
        {
            //키 중복 확인
            if (!this.dic.ContainsKey(key))
            {
                this.dic.Add(key, new List<Node>());
            }

        }
        //간선 추가
        public void AddEdge(string from, string to, int weight) 
        {
            //from 인접리스트에 정점 추가
            var list = this.dic[from];
            list.Add(new Node(to, weight)); 
        }
        public void Print() 
        {
            foreach(var pair in this.dic)
            {
                var from = pair.Key; //from
                
                //edge = 인접 vertex
                foreach (var edge in pair.Value) 
                {
                    Console.WriteLine("{0}--{1}--{2}", from, edge.Weight, edge.key); //from의 인접 리스트
                }
            }
        }
    }

public class Node
    {
        public string key;
        public int Weight;
        public Node(string key,int weight=1) 
        {
            this.key = key;
            this.Weight = weight;
        }
    }

public App()
        {
            Console.WriteLine("App");

            Graph graph = new Graph();

            graph.AddVertex("seoul");
            graph.AddVertex("busan");
            graph.AddEdge("seoul", "busan", 10);
            graph.Print();

            
        }

 

linkedlist로 그래프 구현

//정점 클래스(vertex)
    public class Node
    {
        public string key;
        //간설들의 리스트
        public LinkedList<Edge> edges;
        public Node(string key) 
        {
            this.key = key;
            this.edges = new LinkedList<Edge>();
            
        }
    }

//간선 
    public class Edge
    {
        //from=key
        public string from;
        public string to;
        public int weight;
        public Edge( string from, string to, int weight) 
        {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

public class Graph
    {
        //정점 관리용 컬랙션 선언
        public List<Node> nodes;

        public Graph() 
        {
            this.nodes = new List<Node>();
        }
        public void AddVertex(string key) 
        {
            this.nodes.Add(new Node(key));
        }
        public void AddEdge(string from, string to, int weight = 1) 
        {
            //정점리스트에서 from 키를 갖는 요소를 찾는다.
            var fromVertex = this.nodes.Find(x => x.key == from);

            //찾은 정점에 인접 리스트에 간선 추가
            fromVertex.edges.AddLast(new Edge(from, to, weight));
        }
        public void Print() 
        {
            foreach (var vertex in this.nodes) 
            {
                foreach (var edge in vertex.edges) 
                {
                    var from = vertex.key;
                    Console.WriteLine("{0}--{1}--{2}", vertex.key, edge.weight, edge.to);
                }
            }
        }
    }

public class App
    {
        public App()
        {
            Console.WriteLine("App");

            Graph graph = new Graph();

            graph.AddVertex("서울");
            graph.AddVertex("부산");

            graph.AddEdge("서울", "부산", 10);
            graph.Print();

        }
    }