728x90 반응형 SMALL Graphy3 Graphy 인접행렬 이전에는 각 노드를 생성하고 이를 서로 연결하여 그래프를 만드는 이론과 코딩을 설명하였다. 하짐나 이건 그래프의 아주 기초적인 단계이며, 이를 바탕으로 여러 그래프가 존재한다. 그 중 그래프를 나타내는 다른 표현을 설명하겠다. 인접행렬이란? 그래프를 2차원 행렬로 표현 한것으로 각 노드 중간에 존재하는 엣지의 연결성을 나타내는 리스트이다. 이 행렬은 노드수 X 노드수의 크기를 가지며, 각 노드들의 연결 관계를 나타내고 있다. 예를 들어 아래와 같은 그래프가 존재하다고 가정하자. 이 그래프는 어떠한 가중치도 존재하지 않는 그래프이다. 이 그래프를 이렇게 표현 할 수도 있지만, 행렬로 나타내면 다음과 같이 표현 할 수 있다. 각 노드들간의 관계를 0과 1로 표현하였다. 연결이 되어있으면 1, 연결이 되어있지.. 2023. 6. 26. 그래프 만들고, 연결하기 이전까지는 그래프에 대한 이론을 설명하였다. 이번에는 이러한 이론을 바탕으로 그래프를 실제로 만들고 연결해보아야 한다. 코딩으로 옮기기전에 텍스트 파일을 미리 준비하였다. 안에는 임의로 넣어둔 서울 지하철 역이다. 파일 제목은 node.txt로 해두었다. 그리고 이 텍스트 파일을 파이썬 파일과 같은 경로에 넣어두었다. 다음은 그래프를 만드는 class를 구현하였다. class StationNode: # 지하철 역을 노드로 만들어 준다. def __init__(self, station_name): self.station_name = station_name 이렇게 클래스를 이용하여, 데이터가 들어올때 마다 노드를 하나 생성 한다. 그리고 다음에는 이렇게 생성된 노드를 하나의 그래프로 연결해주어야 한다. de.. 2023. 6. 23. 그래프 이론 그래프란? 연결 데이터를 저장 할 수 있는 자료구조를 의미한다. 자료구조에는 많은 형태가 있다. 예를 들어 스택, 큐, 링크드 리스트...등등 선형 구조, 비선형 구조, 계층 구조 등이 존재한다. 여기서 그래프는 선형적, 계층적 구조를 가진다. 그럼 왜 CS(Computer Science)에서 그래프를 다루어야 할까? 바로 그래프는 기존의 자료구조에서 표현 할 수 없는 데이터를 나타낼 수 있기 때문이다. 예를들어 SNS에서도 많이 사용된다. 누가 누구를 팔로우, 팔로잉 했는지 또 누구와 관련이 있는지 알아 낼 수 있기 때문이다. 또한 탐색에서도 많이 이용된다. 깊이 우선 탐색, 넓이 우선 탐색 등 다양하게 응용 및 이용 될 수 있기 때문이다. 이러한 그래프는 여러 종류가 존재하는데, 무방향 그래프, 방향.. 2023. 6. 20. 이전 1 다음 반응형 LIST
