# 영어 소문자로 표현된 정점들을 인덱스값과 매핑하기 위한 자료구조 
dict = {
    "a" : 0,
    "b" : 1,
    "c" : 2,
    "d" : 3,
    "e" : 4,
    "f" : 5,
    "g" : 6
}

# 인접행렬을 위한 2차원 배열 정의 및 초기화
adj_mat = [[0] * len(dict) for _ in range(len(dict))]

# 입력한 간선들을 포함한 2차원 배열
input = [["a","b"],["a","c"],["b","c"],["c","d"],["d","e"],["d","f"],["d","g"],["e","f"]]
key_list = list(dict.keys())        # dict의 키값들을 대입
val_list = list(dict.values())      # dict의 값들을 대입

# 그래프 구조를 위한 Graph Class 선언
class Graph:
    adj = []        # 입력 그래프를 저장하기 위한 빈 배열
 
    # 정점의 수가 v이고 간선의 수가 e인 빈 그래프를 선언하고 초기화하는 멤버 함수
    def __init__(self, v, e):
        self.v = v
        self.e = e
        Graph.adj = [[0 for i in range(v)]
                        for j in range(v)]
 
    # 간선을 추가하는 함수
    def addEdge(self, start, e):
        Graph.adj[start][e] = 1
        Graph.adj[e][start] = 1
 
    # 깊이 우선 탐색 함수
    def DFS(self, start, visited):
         
        print(key_list[start], end = "")
        print( end = " -> ")
        visited[start] = True
 
        # 그래프에서 탐색되지 않은 정점에 대해 DFS() 함수를 재귀적으로 호출
        for i in range(self.v):
            if (Graph.adj[start][i] == 1 and
                    (not visited[i])):
                self.DFS(i, visited)

    # 너비 우선 탐색 함수
    def BFS(self, start):         
        visited = [False] * self.v
        q = [start]         # bfs를 적용하기 위한 큐 구조를 선언하고 start 정점을 삽입
        
        visited[start] = True   # start 정점을 탐색했다고 표시
 
        while q:
            vis = q[0]      # 큐에 있는 정점과 탑에 있는 정점을 vis에 대입
            
            # vis를 출력하고 큐에서 팝
            position1 = val_list.index(vis)
            print(key_list[position1], end = "")
            print( end = " -> ")
            q.pop(0)
            
            for i in range(self.v):
                # vis의 탐색되지 않은 인접한 정점들을 큐에 입력
                if (Graph.adj[vis][i] == 1 and
                      (not visited[i])):                                               
                    q.append(i)
                    visited[i] = True   # 정점 i를 탐색했다고 표시

# 새로운 그래프 G 선언
G = Graph(7, 8)

# 선언된 그래프 G를 입력 데이터를 통해 초기화
for pair in input:
    G.addEdge(dict[pair[0]],dict[pair[1]])

# 그래프 G에 대한 인접행렬을 출력
print("예제로 제공된 그래프를 인접행렬로 표현하면 다음과 같다.")

dict_keys = list(dict.keys())
print(end = "            ")
for i in dict:
    print(i, end = " ")
print()

print("          \u250c               \u2510")
for i in range(0, len(dict)):
    print("       ", dict_keys[i], "| ", end = "")
    for j in range(0, len(dict)):
        print("%d" % G.adj[i][j], end = " ")
    print("| ")
print("          \u2514               \u2518")

# 너비 우선 탐색 방법으로 탐색한 정점들을 순서대로 출력
print("\n그래프를 너비 우선 탐색 방법으로 탐색할 때 정점들의 순서는 다음과 같다.: \n")
G.BFS(dict["a"])
print(end="\b\b\b     \n")

# 정점들의 탐색에 대한 정보를 저장하기 위한 이진 배열 선언 및 초기화
visited = [False for i in range(len(dict))] 

# 깊이 우선 탐색 방법으로 탐색한 정점들을 순서대로 출력
print("\n\n그래프를 깊이 우선 탐색 방법으로 탐색할 때 정점들의 순서는 다음과 같다.: \n")
G.DFS(dict["a"], visited)
print(end="\b\b\b     \n\n\n")
