2020년 소프트웨어 엔지니어의 구직은'알고리즘'이라는 단어의 동의어다.최근 처리에 사용할 수 있는 데이터의 양이 증가함에 따라 이 회사들은 진정으로 문제를 잘 해결하고 언제 어떤 데이터 구조를 사용할지 아는 사람을 고용하기를 희망한다.그러나 내가 이 모든 정보를 이해하는 데 얼마나 많은 시간을 들였든지 간에 다른 주제보다 더 어려운 주제가 있는 것 같다.이 주제는 도형이다.
나는 그림이 무엇인지, 왜, 어디서 그것을 사용하는지, 심지어 기본적인 역행 알고리즘 - BSF (광도 우선 검색) 와 DSF (깊이 우선 검색) 를 안다.그러나 가장 어려운 부분은 코드에 그림을 어떻게 표시하는지 이해하는 것이다.제가 최근에 시작한 소프트웨어 엔지니어 경력에서 저는 Hacker Rank, Leet Code와 유사한 자원의 알고리즘 도전 외에 몇 번만 사용해야 합니다.그래서 이 글에서 나는 C#로 그림을 나타내는 몇 가지 다른 방식을 설명하려고 한다. 나는 최종적으로 어떻게 하는지 기억하길 바란다.공부하는 가장 좋은 방법은 남을 가르치는 것이기 때문이다.

용어

다른 언어를 배우고 있다고 상상해 보세요.만약 아무런 언어 환경도 없이 당신에게 단어를 던지고, 익숙하게 들리는 것이 하나도 없다면, 당신은 멀리 갈 수 없을 것이다.그러나 만약 당신이 이미 몇 가지 단어를 배워서 하나의 어휘, 심지어 기본적인 어휘를 발전시켰다면 모든 것을 완전히 이해하지 못하더라도 다른 사람이 당신에게 한 말을 이해하고 심지어 대답을 시도할 수 있을 것이다.우리는 이곳에서 같은 개념을 응용하여 새로운 어휘를 배울 것이다.

도표

도형이 어리석다는 것은 포함되지 않는다.간단하게 말하자면, 그것은 직선으로 연결된 점일 뿐이다.점은 정점(단수의 정점) 또는 노드라고도 할 수 있으며, 선은 통상적으로 "모서리"라고 부른다.

모서리 꼭대기

이것은 마치 엉망진창인 사전처럼 들린다. 왜냐하면 우리는 이미'그림'절에서 그것을 소개했지만, 정점은 그림에서 그림의 가장자리를 통해 연결할 수 있는 점일 뿐이다.

가장자리

이것은 오랫동안 나에게 약간의 곤혹을 가져왔다. 왜냐하면 내 머릿속의'가장자리'는 어떤 일의 끝을 대표하거나 인터넷에서 말한 바와 같이'한 물체의 외부 경계'이기 때문이다.그러나 수학 그림에서는 그렇지 않습니다. 모서리는 두 노드(정점)를 연결하는 선일 뿐입니다.

무방향도

방향이 없는 그림에서 모서리는 방향이 없으며 노드 B에서 노드 A와 같은 모서리를 통해 노드 A에서 노드 B로 이동할 수 있습니다.

방향도

유방향 그림에서 각 모서리는 한 방향이 있고 한 모서리가 이 방향을 가리키면 노드 a에서 노드 B까지만 할 수 있다.

인접 교점

한 모서리에만 연결된 교점 (노드) 입니다.참고: 교점은 인접할 수 없습니다.

테두리 권중

이것은 또한 가장자리의 원가라고도 부른다.이것은 노드 A에서 노드 B까지의 경로가 다른 경로보다 우수한지 정의하는 데 사용됩니다. 권한이 작을수록 경로가 좋습니다.

추상적인 GraphBase 클래스 정의

이 새 어휘표가 있으면 코드에서 그림 표시를 더 쉽게 볼 수 있고 완전히 잃어버리지 않기를 바랍니다.우리는 두 가지 다른 표현을 실현하고자 하기 때문에, 나는 추상적인 클래스를 정의하는 것부터 시작하여, 나는 그것을 GraphBase라고 부른다.

public abstract class GraphBase
    {
        protected readonly int NumVertices;
        protected readonly bool Directed;

        public GraphBase(int numVertices, bool directed = false)
        {
            this.NumVertices = numVertices;
            this.Directed = directed;
        }

        public abstract void AddEdge(int v1, int v2, int weight);

        public abstract IEnumerable<int> GetAdjacentVertices(int v);

        public abstract int GetEdgeWeight(int v1, int v2);

        public abstract void Display();

        public int NumVertices { get { return this.numVertices; } }
    }

그림의 인접 행렬 표시

이곳의 코드는 매우 간단해서 말하지 않아도 안다.이제 그것을 사용하고 인접 행렬을 사용하여 그림을 만들어 봅시다.이해하기 편리하도록 나는 블록을 나누어 코드를 발표할 것이다.매트릭스 필드와 구조 함수부터Generate Empty Matrix 방법을 순서대로 호출하여 빈 값(또는 0)으로 매트릭스를 채웁니다.이 행렬은 우리의 그림 표시가 될 것이다.

        int[,] Matrix;
        public AdjacencyMatrixGraph(int numVertices, bool directed = false) : base(numVertices, directed)
        {
            GenerateEmptyMatrix(numVertices);
        }

        private void GenerateEmptyMatrix(int numVertices)
        {
            this.Matrix = new int[numVertices, numVertices];
            for (int row = 0; row < numVertices; row++)
            {
                for (int col = 0; col < numVertices; col++)
                {
                    Matrix[row, col] = 0;
                }
            }
        }

만약 우리가 9개의 정점을 가진 그림을 가지고 있다면, 구조 함수를 호출한 후, 행렬은 다음과 같다.

하지만 81개의 다른 칸을 포함하고 있습니다!맞아요. 그 작업 방식은 정점이 다른 정점에 연결되어 있는지 알고 싶다면, 이 행렬에서 빠르게 찾을 수 있습니다.예를 들어, 정점 0이 정점 8에 연결되어 있는지 확인하려면 행렬의 오른쪽 위 모서리에 있는 요소를 보고 이 두 노드가 연결되어 있지 않은지 빨리 확인하십시오.이제 모서리를 추가하는 방법을 추가하고'연결'이라는 두 정점 후에 어떻게 변화하는지 보겠습니다.

public override void AddEdge(int v1, int v2, int weight = 1)
{
    if (v1 >= this.numVertices || v2 >= this.numVertices || v1 < 0 || v2 < 0)
        throw new ArgumentOutOfRangeException("Vertices are out of bounds");

    if (weight < 1) throw new ArgumentException("Weight cannot be less than 1");

    this.Matrix[v1, v2] = weight;

    //In an undirected graph all edges are bi-directional
    if (!this.directed) this.Matrix[v2, v1] = weight;
}            

여기는 그리 복잡한 일이 없다.우리는 정점이 행렬의 경계 안에 있는지, 권한이 1보다 작지 않은지, 주어진 노드 사이에 모서리를 만드는지 검증합니다.만약 그것이 방향도가 없다면, 모서리는 양방향으로 존재해야 하며, 행렬은 대칭적으로 보일 것이다.
이제 정점 0에서 정점 8에 모서리를 추가하여 행렬을 어떻게 바꾸는지 봅시다.

class Program
{
    static void Main(string[] args)
    {
        var adjMatrixGraph = new AdjacencyMatrixGraph(9, false);
        adjMatrixGraph.AddEdge(0, 8);
    }
}

다음은 이 모서리를 추가한 후 행렬의 모양입니다.

보시다시피 0에서 8까지의 모서리와 8에서 0까지의 모서리가 무방향 그림이기 때문에 생성되었습니다.
지금까지는 괜찮았지만, 우리는 아직 완성하지 못했다.그림을 훑어보기 위해서, 우리는 인접한 정점을 찾는 방법이 필요하다.다음은 우리가 그것을 실현할 것이다.

public override IEnumerable<int> GetAdjacentVertices(int v)
{
    if (v < 0 || v >= this.numVertices) throw new ArgumentOutOfRangeException("Cannot access vertex");

    List<int> adjacentVertices = new List<int>();
    for (int i = 0; i < this.numVertices; i++)
    {
        if (this.Matrix[v, i] > 0)
            adjacentVertices.Add(i);
    }
    return adjacentVertices;
}

보시다시피, 인접한 정점을 가져오는 것은 정점이 있는 줄에서 교체하는 것처럼 간단하고, 0보다 큰 일치하는 정점 가장자리를 가져오는 것입니다.
0에서 8, 0에서 3, 8에서 4 세 개의 모서리를 추가한 다음 0 번째 정점의 인접 정점을 얻습니다.

var adjMatrixGraph = new AdjacencyMatrixGraph(9, false);
adjMatrixGraph.AddEdge(0, 8);
adjMatrixGraph.AddEdge(0, 3);
adjMatrixGraph.AddEdge(8, 4);
var adjacent = adjMatrixGraph.GetAdjacentVertices(0);

이것은 우리의 행렬과 인접한 정점의 외관이다.

보시다시피 우리는 정점 0과 인접한 정점으로 3과 8을 정확하게 얻었고 정점 4를 정확하게 무시했다. 왜냐하면 8과 인접하지만 0이 아니기 때문이다.만약 우리가 지금 정점 8에서 GetAdjacentVertices를 호출한다면, 정점 0과 4는 8과 인접해야 한다.

var adjacent = adjMatrixGraph.GetAdjacentVertices(8);

우리가 지금 해야 할 마지막 일은 getedgewight 방법을 실현하는 것이다.행렬 표현을 사용하면 교점 1과 교점 2의 교점 값을 쉽게 얻을 수 있습니다.

public override int GetEdgeWeight(int v1, int v2)
{
    return this.Matrix[v1, v2];
}

이것은 절대로 그리 나쁘지 않다.가장 도전적인 부분은 C#에서 2D 배열이 작동하는 방식을 기억하는 것입니다.
이제 인접 집합을 사용한 그림의 또 다른 실현을 빨리 봅시다.

그림의 인접 집합 표시

집합 표시도를 사용할 수 있도록 Node라는 클래스를 정의합니다. 이 클래스는 모서리를 보존하고 인접한 정점에 쉽게 접근할 수 있도록 합니다.

public class Node
{
   private readonly int VertexId;
   private readonly HashSet<int> AdjacencySet;

   public Node(int vertexId)
   {
       this.VertexId = vertexId;
       this.AdjacencySet = new HashSet<int>();
   }

   public void AddEdge(int v)
   {
       if (this.VertexId == v)
           throw new ArgumentException("The vertex cannot be adjacent to itself");
       this.AdjacencySet.Add(v);
   }

   public HashSet<int> GetAdjacentVertices()
   {
       return this.AdjacencySet;
   }
}

각 노드에는 정점 ID 필드가 있으므로 모서리를 포함하는 인접 해시 집합을 쉽게 참조할 수 있습니다.모서리를 추가하는 것은 집합에 정점을 추가하는 것과 마찬가지로 간단하고, 인접 정점을 가져오는 것은 인접 집합을 되돌리는 것과 마찬가지로 간단하다.
이제 AdjacencySetGraph를 사용하여 GraphBase를 구현하는 방법을 살펴보겠습니다.지난번과 마찬가지로 우리는 구조 함수부터 시작합시다.

private HashSet<Node> vertexSet;
public AdjacencySetGraph(int numVertices, bool directed = false) : base(numVertices, directed)
{
       this.vertexSet = new HashSet<Node>();
       for (var i = 0; i < numVertices; i++)
       {
           vertexSet.Add(new Node(i));
       }
}

여기서 정점 정보를 나타내는 노드를 저장하고 그래픽 객체를 작성할 때 지정한 정점 수로 채우는 다른 컬렉션을 만들었습니다.지금까지는 간단했어.
AddEdge 방법을 살펴보겠습니다.

public override void AddEdge(int v1, int v2, int weight = 1)
{
      if (v1 >= this.numVertices || v2 >= this.numVertices || v1 < 0 || v2 < 0)
           throw new ArgumentOutOfRangeException("Vertices are out of bounds");

      if (weight != 1) throw new ArgumentException("An adjacency set cannot represent non-one edge weights");

      this.vertexSet.ElementAt(v1).AddEdge(v2);

      //In an undirected graph all edges are bi-directional
      if (!this.directed) this.vertexSet.ElementAt(v2).AddEdge(v1);
}

너는 이런 방식으로 도형의 한계성을 나타내는 것에 주의했니?우리는 1이 아닌 가치가 있을 수 없다.음, GraphBase 추상류를 가지기에는 좀 이르다.
모서리 추가는 지정된 교점 ID를 사용하여 노드에 액세스하고 AddEdge 메서드를 호출하는 것과 마찬가지로 간단합니다. 이 메서드는 교점을 인접한 교점 집합에만 추가합니다.따라서 인접한 교점을 얻는 것은 매우 간단하다.

public override IEnumerable<int> GetAdjacentVertices(int v)
{
      if (v < 0 || v >= this.numVertices) throw new ArgumentOutOfRangeException("Cannot access vertex");
      return this.vertexSet.ElementAt(v).GetAdjacentVertices();
}

마지막으로, GetEdgeWight 방법을 구현해야 하지만, 값이 1이 아닌 권한을 얻을 수 없기 때문에, 1을 되돌려주기만 하면 됩니다.

public override int GetEdgeWeight(int v1, int v2)
{
     return 1;
}

나는 당신에게 모든 방법의 장단점과 모든 실현 과정에서 처리되지 않은 가능한 문제를 찾아내게 할 것입니다.도형의 대가가 되는 데 도움이 됐으면 좋겠어요.나는 내가 마침내 그것을 얻었다고 믿는다.만약 필요하다면 이 두 가지 도형 표현법 중 하나를 사용하여 깊이 우선 검색이나 광도 우선 검색 알고리즘을 실현할 수 있다.만약 당신이 이 글을 읽고 있다면, 오류나 참을 수 없는 일을 보았다면, 댓글 부분에 메시지를 남겨 주십시오. 우리는 토론을 할 수 있습니다.

도형이 당신에게 쉬워요?

P, 나는 이 문장에서 도형에 관한 많은 일을 언급하지 않았다.예를 들어 순환도와 비순환도.이 글은 코드로 기본 도형을 표시하는 것에 관한 것이다. 만약에 이 주제에 대한 정보를 더 알고 싶다면 인터넷에 이 주제를 깊이 있게 이해하는 데 도움을 줄 수 있는 자원이 많다.