자료구조와 그래프 , data structure for design and graph

(1) 그래프

: 자료구조 디자인의 한 방법

: 기본적으로 위 그림처럼 vert(노드 또는 정점)와 edge(간선)으로 연결

 

(2) 그래프와 트리와의 차이점

그래프는 "노드간의 관계"를 나타내며 , 트리는 "노드간의 계층"을 표현한다.

 

(3) 그래프의 유형

- 방향성과 무방향성 (directed & undirected)

- 순환과 비순환 (cyclic & Acyclic)

 

(4) 가중그래프

: 경로의 총 가중치가 높을수록 경로이동시간(비용)이 길어진다

 

(5) 그래프 표현방법

- 인접리스트(adjacency lists)와 인접행렬(adjacency matrices)

class Graph:
    def __init__(self):
        self.vertices = {
                            "A": {"B"},   # 여기서 {"B"}가 set의 형태이다.
                            "B": {"C", "D"}, # {"B" : {}}의 형태는 딕셔너리
                            "C": {"E"},     # 즉, 딕셔너리 안에 set이 있는 것이다.
                            "D": {"F", "G"},
                            "E": {"C"},
                            "F": {"C"},
                            "G": {"A", "F"}
                        }
                                                             
class Graph:
    def __init__(self):
        self.edges = [[0,1,0,0,0,0,0],
                      [0,0,1,1,0,0,0],
                      [0,0,0,0,1,0,0],
                      [0,0,0,0,0,1,1],
                      [0,0,1,0,0,0,0],
                      [0,0,1,0,0,0,0],
                      [1,0,0,0,0,1,0]]  

- 가중치 부여시

class Graph:
    def __init__(self):
        self.vertices = {
                            "A": {"B": 1},  # 가중치 부여
                            "B": {"C": 3, "D": 2},  # 가중치 부여
                            "C": {},
                            "D": {},
                            "E": {"D": 1}   # 가중치 부여
                        }
 
 class Graph:
    def __init__(self):
        self.edges = [[0,1,0,0,0],
                      [0,0,3,2,0],
                      [0,0,0,0,0],
                      [0,0,0,0,0],
                      [0,0,0,1,0]]