그래프(G)는 정점(V)과 간선(E)으로 이루어져 있음 그래프의 종류 -무방향 그래프: 간선에 방향성이 없음 -방향성 그래프: 간선에 방향성이 있음 -가중치그래프: 간선에 가중치가 부여된 그래프 병렬 간선: X -> Z의 간선이 h,i 두개가 복수로 존개가능함 루프: 출발지 정점과 목적지 정점이 같은경우 ex) edge j 그래프G에서 점선을 다 지우면 G'인 그림임 부분 그래프: G'은 그래프G의 일부분임 V-V'을 잇는 E는 존재할 수없다. 신장부분그래프: 그래프 G'은 그래프G의 일부분인데 G의 모든 정점을 가지있음 연결 그래프: 모든 정점 간에 경로가 존재 트리는 연결그래프이고 Forest는 연결되지 않은 그래프임 파이썬으로 그래프 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..

그래프 순회는 그래프의 모든 정점을 방문하는 방법임 순회방법으로는 깊이 우선 탐색과 너비 우선 탐색이 있음. 먼저 깊이 우선 탐색에 대해 알아보자 unexplored vertex는 방문하지않은 정점이고 visted vertex는 한번 지나온 정점임 A -> B -> C로 순서일 때, C -> A가 연결되있음. 하지만 A는 이미 지나온 정점임. C -> A Edge를 back edge로 표기함 이제 C는 D로 가거나 E로 갈 수 있음. 파이썬으로 구현해보면 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def DFS(g, u, discovered): for e in g.incident_edges(u): v = e.opposite(u) if v not in discovered: dis..