2022/04/28) 1. 그래프와 인접행렬 [그래프와 탐색(DFS, BFS(넓이우선))]

1. 그래프

• 기호 표현법 : G(V, E)
  • Graph(Vertex, Edge)의 약자로, 정리하면 그래프는 V와 E로 이루어진 자료구조라는 뜻이다.
  • V는 정점 혹은 노드라고 말하고, E는 간선이라고 말한다.

2. 인접행렬

• 인접행렬의 정의, 만드는 법, 읽는 법
  • 인접행렬 : 그래프의 구조를 표현하기 위해 각 노드가 연결된 형태를 2차원 배열에 기록하는 방식이다. 정점 수만큼의 열과 행을 만들어야 하고, 정점 i와 j 사이에 간선(edge)이 있으면 i번째 행과 j번째 열의 원소가 1, 그렇지 않으면 0으로 표시된다.
    ex ) 정점(노드)가 5개라면, 정점1과 나머지 정점 4개가 연결돼 있는지 표현해야 하므로, 5개의 열과 행을 만들어야 함.
  • 생성 하는 법 : 연결정보가 입력되는데, 앞의 것을 a 뒤의 것을 b로 둔다. 그래프마다 표시하는 방법이 다르므로 뒤에서 제대로 살펴 보도록 하자.
  • 생성 시 주의할 점 : 행과 열의 인덱스 번호는 1로 시작해야 한다. (노드번호가 1부터 시작하므로)
    => graph배열 생성 시, Array.from(Array(n+1), ()=>Array(n+1).fill(0));
  • 인접행렬 읽는 법 : 무조건 행에서 열 방향으로 읽어야 한다.
    "○번 노드에서 ○번 노드로 간다." "○번 노드에서 ○번 노드로 가는데, 가중치는 ○이다."

3. 그래프 종류

• 1. 무방향 그래프 : 정점의 방향이 없다. 그러므로 정점 a와 b가 연결돼 있다면, a에서 b로 그리고 b에서 a로도 갈 수 있으므로 graph[a][b]=1; graph[b][a]=1;를 해준다.
     
• 2. 방향 그래프 : 정점의 방향이 있다. 그러므로 graph[a][b]=1;만 해준다.
     
• 3. 가중치 방향그래프 : 방향 그래프에 가중치가 더해졌다. 이전엔 1를 삽입해 주었다면, 이젠 가중치값을 삽입해준다. graph[a][b]=c;