graph

그래프 정의

• 그래프 G는 (V,E)로 표시
• 간선(edge) 또는 링크(link): 정점들간의 관계의미
• undirectied graph: 무방향 그래프 - 그래프 vertex간의 방향성이 존재하지않는다(a,b) ==(b,a)
• directed graph : 그래프 vertex간의 link에 방향성이 존재한다.<a,b> ≠ <b,a>
• 가중치 그래프 , 네트워크: 간선에 비용이나 가중치가 할당된 그래프
• 부분 그래프 - 특정 그래프의 일부분으로 이루어진 그래프
• adjacent vertex - 간선에 의해서 직접 연결된 vertex
• degree - vertex에 연결된 간선의 수
• 무 방향 그래프에서 차수의 합은 간선수의 2배(무방향이면 같은 간선이 양쪽으로 두번 세어진다.
• directed graph에서 진입차수 진출차수로 방향에 따라서 나뉨
  • vertex로 들어오는 간선이 집입차수
  • vertex에서 나가는 방향의 간선이 진출차수
  • 모든 진출, 진입 차수의 합은 간선의 수와 같다.
• path - 무방향 그래프의 정점 s로 부터 정점 e까지의 경로
  • 정점의 나열로 나타낸다. vertex사이에 반드시 간선이 존재해야 경로가 될 수 있다(s,v1)무방향 그래프는 소괄호
  • 방향 그래프의 정점 s로 부터 e까지의 경로
    • 정점의 나열로 나타내기도하고 반드시 방향에 맞는 간선이 존재해야한다. <s, v1>
• simple path
  • 경로 중에서 반복되는 간선이 없는 경로
    • BACD는 단순경로임
    • BACA는 반복되는 구간이 존재하므로 단순 경로가 아니다.
• cycle - 시작 정점과 종료 정점이 동일한 경로
  • BACB는 사이클
• 그래프를 표현하는 방법

  • 인접행렬 - 인접행렬 M을 이용하는 방법
    - vertex의 수가 n개 이면 M은 n x n 정방행렬
    - 각 vertex를 index로 표현한다

    

    각행과 열의 동일한 인덱스에 vertex를 나타내는 구조이다 위에서 볼 수 있듯이 무방향 그래프의 인접행렬나타낸 행렬은 대칭행렬이된다.

  • 인접 리스트를 이용한 표현

    • undirectgraph의 경우에는

      • 직접 인접 vertex를 리스트 안에 리스트로 삽입한다.

      • direct graph의 경우에는 직접적 해당 vertex의 진출 간선을 리스트로 표현한다.

        인접행렬	인접 리스트
        간서의 수에 상관없이 항상 n**2의 미메리 공간이 필요해서 메모리에 비효울적 그러나 dense graph에서 효과적이다.	n+2e개의 연결 리스트가 필요하다 희소 그래프에서 효과적이다
        M[u][v] 를 조사하면 바로 간선의 유무를 알 수 있어서 시간 복잡도는 O(1)	연결 리스트 전체를 조사해애한다
        해당 정점의 차수를 구하는 degree(v)는 정점 v에 해다하는 행을 조사하ㅏ면됨 따라서O(n)이다	연결시트으의 길이를 반환하면 된다 O(d)
        인접 정점을 구하는 adjacent(v)는 O(n)의 시간이 요구된다.	정점 v에 간선으로 직접 연결된 모든 정점을 구하는 adjacent(v)연산도 위와 동일
        전체 그래프의 간선의 수를 알아낼려면 전체 행렬을 조사해야 하므로 O(n**2)	전체 간서의 수를 알아내려면 헤더 노드를 포함하여 모든 인접 리스트를 조사해야 하므로 O(n+e)

        

        인접행렬로 표한현 그래프 가중치 그래프를 표현할 때는 가중치를 리스트에 삽입한다 인접행렬로 무방행렬을 표현할 때는 인덱스 자기에 간선이 있으면 1을 없으면 0을 삽입한다.

        
        #인접행렬
        vertex = ['a', 'b', 'c', 'd', 'e']
        M = [[0, 1, 1, 0, 0],
             [1, 0, 0, 1, 1],
             [1, 0, 0, 1, 0],
             [0, 1, 1, 0, 1]
             [0, 1, 0, 1, 0]]
        
        #인접 리스트
        vertex2 = ['A','B','C','D','E','F','G','H']
        adjsust = [[1,2],
                   [0,3],
                   [0,3],
                   [1,2,4],
                   [2,6,7],
                   [4,7],
                   [4,6]]
        #딕셔너리와 set을 이용한 방법
        mygraph = {'S': {'A', 'C', 'B'}, 'A': {'S', 'D'}, 'B': {'S', 'D'}, 'D': {'B', 'C'}, 'C': {'S', 'D'}}

        밑에 인접 행렬을 가중치를 제외하고 만듦

      • 그래프를 탐색하는 방법

        • DPS BPS
          • DPS - 깊이 우선탐색 - 한 방향으로 끝까지 가다가 더이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색 진행
          • 되돌아가기 이위해서는 스택필요
          • 순환함수 호룰로 묵시적인 스택이용

파이선 집합 자료형 정리한거

def dfs(graph, start, visited=set()):  # 파라미터로 딕셔너리로 구현한 인접 리스트, 탐색을 시작할 vertex, 방문을 표시할 visited  = set()을 전달한다.

    if start not in visited:  # start가 아직 방문하지 않은 노드일 경우에
        visited.add(start)  # 방문하지 않은 vertex일 경우에는 start를 방문을 나타내는 집합에 추가
        print(start, end=' ')  # 방문하면서 내부의 요소를 출력
        nbr = sorted(graph[start] - visited)  # start를 키값으로 저장하고 있는 셋에서 이미 방문한 쎗과 차집합 연산을 통해서 제거함
        for i in nbr:
            dfs(graph, i, visited)  # 인접한 노드를 이용해서 재귀적으로 다시 호출한다.
            # 이 반복문이 이게 dfs인 이유이다 끝까지 재귀저으로 이동하고 if문의 조건에 맞지 않으면 None를 반환하기 때문에
            # 깊이 우선연란이라고 할 수 있다.

• bfs 너비 우선 탐색 - 인접한 곳을 제일 우선순위로 방문한 후에 다른 정점을 방문하는 방법을 사용한다.

def dfs_cc(graph, color, vertex, visited):#파이선에서도 배열은 레퍼런스가 전해지기 때문에 파라미터로 전달되어질 set의 원본의 값이 변한다.
    if vertex not in visited:
        visited.add(vertex)#재귀함수에서도 다른함수에서 호출되어서 추가된 값이 저장된다.
        color.append(vertex)# 재귀함수에서도 다른함수에서 호출되어서도 값의 변경된 값이 유지가된디.
        nbr = graph[vertex] - visited# 차집합을 이용해서 이미 방문한 값을 제외시킨다.
        for i in nbr:
            dfs_cc(graph, color, i, visited)
    return color

def find_conneccted_componet(graph):
    visited = set() #방문을 점검할 집합을 생성함
    colorlist = [] # 분리된 그래프를 저장할 배열을 생성함

    for vtx in graph: #graph에 들어있는 원소를 차례대로 방문함
        if vtx not in visited:# 만약 방문한 집합에 들어있지않는 요소가 있다면
            color = dfs_cc(graph, [], vtx, visited)#dfs를 돌아서 연결되어있는 
            colorlist.append(color)

    print("그래프 연결성분의 개수:",len(colorlist))
    print(colorlist)

find_conneccted_componet(graph2)

• dfs_cc(graph, color, vertex, visitied)
• 위 함수가 find connedted componet 함수의 가장 중요한 부분이다 위함수는 dps로 그래프를 순환해서 방문된 각 요소들을 리스트로 만들어서 반환한다 이때 find connedted component 함수에 파라 미터로 전다한 visited와 같은 set을 사용하기 때문이 아래 함수에서 방문한 요소들은 더이상 방문하지 않고 하나의 리스트로 컴파인되어서 반환한다 마지막에 colorlist의 길이는 내부에 append한 list를 요소로 가지고 있기 때문에 len(colorlist)가 반환하는 값은 이어지지 않고 존재하고 있는 그래프의 갯수를 반환하게 된다.