[파이썬 자료구조와 알고리즘] Chapter 09. 그래프

학습 목표

• 그래프 개념 파악
• 그래프를 구성하는 파이썬 코드 작성
• 그래프로 활용되는 응용 프로그램 작성

 

Section00. 생활 속 자료구조와 알고리즘

버스정류장과 여러 노선이 함께 포함된 형태->그래프 구조

링크드인 같은 사회 관계망 서비스

 

 

Section01. 그래프의 기본

1. 그래프의 개념

-그래프(Graph): 여러 노드가 서로 연결된 자료구조

루트에서 하위 노드 방향으로만 이어지는 트리와 달리 그래프는 여러 노드가 연결되어 ㅣㅇㅆ을 수 있음

 

2. 그래프의 종류

정점을 연결하는 간선의 방향성 여부에 따라 방향 그래프와 무방향 그래프로 나뉨

간선에 가중치를 부여하여 가중치 그래프도 만들 수 있음

🤎무방향 그래프

-정점(Vertex): 트리의 노드에 해당하는 용어

-간선(Edge): 정점을 연결하는 선

그래프=정점_간선

무방향 그래프: 간선에 방향성이 없음

정점 Vertex, V

간선 Edge, E

그래프 Graph, G

-정점 집합: V(G)

-간선 집합: E(G)

V(G1)={A, B, C, D}
V(G2)={A, B, C, D}

무방향 그래프의 간선은 연결하는 두 정점을 ()괄호로 표현

정점 A와 B의 간선을 (A,B)로 표현

무방향 그래프는 방향이 없어 (A,B)와 (B,A)가 동일한 간선이므로 한 번만 표현하면 됨

E(G1)={(A,B),(A,C),(A,D),(B,C),(C,D)}
E(G2)={(A,B),(B,D),(D,C)}

🤎방향 그래프

방향성이 있는 그래프

화살표로 간선 방향 표기

그래프의 정점 집합이 무방향 그래프와 같음

V(G3)={A,B,C,D}
V(G4)={A,B,C,D}

방향 그래프의 간선은 연결하는 두 정점을 <>로 묶어 표현

<A,B>

방향에 있어 <A,B>와 <B,A>는 다른 간선

E(G3)={<A,B>,<A,C>,<D,A>,<D,C>}
E(G4)={<A,B>,<C,B>,<C,D>}

🤎가중치 그래프

간선마다 가중치가 다르게 부여된 그래프

 

3. 깊이 우선 탐색의 작동

-그래프 순회(Graph Traversal): 그래프의 모든 정점을 한 번씩 망문하는 것

-깊이 우선 탐색(Depth First Search, DFS)

-너비 우선 탐색(Breadth First Search, BFS)

 

-깊이 우선 탐색: 그래프는 트리와 달리 부모와 자식 개념이 없으므로 어떤 정점에서 시작해도 결과는 같음

계속 깊이를 파고드는 방식으로 방문하여 정점을 모두 방문

그래프는 정점마다 연결된 선이 여러 개 있을 수 있기 때문에 반드시 시작 정점까지 돌아가야 함

 

 

4. 그래프의 인접 행렬 표현

그래프를 코드로 구현할 때는 일반적으로 인접 행렬을 사용

-인접 행렬: 정방형으로 구성된 행렬, 정점이 4개인 그래프는 4X4 인접 행렬로 표현

왼쪽에는 출발점, 위쪽에는 도착점을 표현

연결되면 1, 연결되지 않으면 0으로 표시

출발점과 도착점이 같은 자기 자신은 모두 0으로 표시

 

🤎무방향 그래프의 인접 행렬

무방향 그래프는 방향성이 없으므로 출발점과 도착점을 바꾸어도 결과가 같음

대각선을 기준으로 서로 대칭되는 특성을 가짐

 

🤎방향 그래프의 인접 행렬

나가는 곳이 없으면 0으로 채움

대각선을 기준으로 대칭되지 않음

<A,B>와 <B,A>는 다름

 

 

 

Section02. 그래프의 구현

1. 그래프의 정점 생성

인접 행렬은 2차원 배열

class Graph():
	def __init__ (self, size):
    	slef.SIZE=size
        self.graph=[[0 for _ in range(size)] for _in range(size)]
        
G1=Graph(4)

2. 그래프의 정점 연결

배열의 행과 열이 첨자 0,1,2,3으로 표현되지만 개념적으로는 A,B,C,D로 생각할 수 있음

G1.graph[0][1]=1 #(A,B) 간선
G1.graph[0][2]=1 #(A,C) 간선
G1.graph[0][3]=1 #(A,D) 간선

G1.graph[1][0]=1 #(B,A) 간선
G1.graph[1][2]=1 #(B,C) 간선

같은 방식으로 출발점 C와 D를 다음과 같이 연결

G1.graph[2][0]=1 #(C, A) 간선
G1.graph[2][1]=1 #(C, B) 간선
G1.graph[2][3]=1 #(C, D) 간선

G1.graph[3][0]=1 #(D, A)간선
G1.graph[3][2]=1 #(D, C) 간선

무방향 그래프 G1과 방향 그래프 G3의 구현

#함수 선언 부분
Class Graph():
	def __init__ (self, size):
    	self.SIZE=size
        self.graph=[[0 for _ in range(size)] for _ in range(size)]
        
#전역 변수 선언 부분
G1, G3=None, None
G1=Graph(4)
G1.graph[0][1]=1; G1.graph[0][2]=1, G1.graph[0][3]=1
G1.graph[1][0]=1; G1.graph[1][2]=1
G1.graph[2][0]=1; G1.graph[2][1]=1; G1.graph[2][3]=1
G1.graph[3][0]=1; G1.graph[3][2]=1

print('G1 무방향 그래프')
for row in range(4):
	for col in range(4):
    	print(G1.graph[row][col], end=' ')
    print()
    
G3=Graph)4_
G3.graph[0][1]=1; G3.graph[0][2]=1
G3.graph[3][0]=1' G3.graph[3][2]=1

print('G3 방향 그래프')
for row in range(4):
	for col in range(4):
    	print(G3.graph[row][col], end=' ')
    print()

 

3. 그래프 개선

실제 그래프는 사람 이름, 도시 이름 등으로 구성하기도 함

변수 이름을 정점 번호로 지정하면 더 직관적

변수 이름 한글 가능

문별, 솔라, 휘인, 쯔위=0,1,2,3
G1.graph[문별][솔라]=1; G1.graph[문별][휘인]=1
G1.graph[솔라][문별]=1; G1.graph[솔라][쯔위]=1

nameAry=['문별', '솔라', '휘인', '쯔위', '선미', '화사']
print(' ', end=' ')
for v in range(G1.SIZE):
	print(nameAry[v], end= ' ')
print()
for row in range(G1.SIZE):
	print(nameAry[row], end=' ')
    for col in range(G1.SIZE):
    	print(G1.graph[row][col], end=' ')
    print()
print()

개선된 무방향 그래프 G1

#클래스와 함수 선언 부분
class Graph():
	def __init__ (self, size):
    	self.SIZE=size
        self.graph=[[0 for _ in range(size)] for _ in range(size)]
        
	def printGraph(g):
    	print(' ', end=' ')
        for v in range(g.SIZE):
        	print(nameAry[v], end=' ')
        print()
        for row in range(g.SIZE):
        	print(nameAry[row], end=' ')
            for col in range(g.SIZE):
            	print(g.graph[row][col], end=' ')
            print()
        print()
        
        
#전역변수 선언 부분
G1=None
nameAry=['문별', '솔라', '휘인', '쯔위', '선미', '화사']
문별, 솔라, 휘인, 쯔위, 선미, 화사=0,1,2,3,4,5

#메인코드부분
gSize=6
G1=Graph(gSize)
G1.graph[문별][솔라]=1; G1.graph[문별][휘인]=1
G1.graph[솔라][문별]=1; G1.graph[솔라][쯔위]=1
G1.graph[휘인][문별]=1; G1.graph[휘인][쯔위]=1
G1.graph[쯔위][솔라]1; G1.graph[쯔위][휘인]=1; G1.graph[쯔위][선미]=1; G1.graph[쯔위][화사]=1
G1.graph[선미][쯔위]=1; G1.graph[선미][화사]=1
G1.graph[화사][쯔위]=1; G1.graph[화사][선미]=1

print('G1 무방향 그래프')
printGraph(G1)

 

4. 깊이 우선 탐색의 구현

🤎깊이 우선 탐색 구현을 위한 준비

깊이 우선 탐색을 구현하려면 스택 사용

방문한 정점을 스택에 푸시해 놓고, 방문할 곳이 막다른 곳이라면 스택에서 팝하는 방식 사용

기존에 방문했는지 여부를 확인하고자 방문했던 기록을 저장하는 데 배열을 사용

 

별도의 top을 사용하지 않고 append()로 푸시, pop()으로 팝하는 스택 사용

len()으로 스택 길이를 확인하여 0이면 스택이 빈 것으로 처리

stack=[]
stack.apppend(값1)
data=stack.pop()

if len(stack)==0:
	print('스택이 비었음')

VisitedAry 배열에 방문 정점 저장

visitedAry 배열에 해당 정점이 있다면 방문한 적이 있는 거승로 처리

visitedAry=[]
visitedAry.append(0) #정점 A(번호 0)을 방문했을 때
visitedAry.append(1) #정점 B(번호 1)을 방문했을 때

if 1 in visitedAry:
	print('A는 이미 방문함')

방문 기록 visitedAry 배열을 출력할 때는 알파벳으로 출력하도록 변경

for i visitedAry:
	print(chr(ord('A')+i), end=' ')

🤎깊이 우선 탐색의 단계별 구현

그래프에서 다음 정점을 찾는 과정은 인접 행렬에서 먼저 만나는 1을 찾는 과정에 해당

①첫 번째 정점 방문

현재 정점을 가리키는 current 변수에 정점 A(번호 0)를 대입

정점 A를 스택에 푸시하고 방문 기록에 추가

current=0 #시작 정점
stack.append(current)
visitedAry.append(current)

②과정(정점 C 방문)

다음 정점을 방문하고자 현재 정점 A에 연결된 도착점 A~D 열에서 1을 찾음

1이 먼저 나오는 정점 C를 다음 정점으로 설정하고 반복문을 빠져나감

찾은 다음 정점 C를 현재 정점(current)으로 설정하고

스택과 방문 기록에 넣음

next=None
for vertex in range(4:
	if G1.graph[current][vertex]==1:
    	next=vertex
        break
        
current=next
stack.append(current)
visitedAry.append(current)

③과정(정점 B 방문)

다음 정점을 방문하고자 현재 정점 C와 연결된 도착점 A~D 열에서 1을 찾음

연결된 정점 A,B,C 중 방문한 적이 있는 정점 A를 탈락시키고 그 다음 순위인 정점 B를 방문

다음 정점 B를 현재 정점으로 설정하고

스택과 방문 기록에 넣음

next=None
for vertex in range(4):
	if G1.graph[current][vertex]==1:
    	if vertex in visitedAry: #방문한 적이 있는 정점이면 탈락
        	pass
        else: #방문한 적이 없으면 다음 정점으로 지정
        	next=vertex
            break
            
current=next
stack.append(current)
visitedAry.apend(current)

④과정(되돌아오는 이동)

다음 정점을 방문하고자 현재 정점 B와 연결된 도착점 A~D 열에서 1을 찾음

연결된 정점 C는 방문한 적이 있으므로 탈락시키고 그 다음 순위를 찾지만

더 방문할 정점을 못 찾아

스택에서 정점 B를 다시 팝하여 현재 정점으로 지정

next=None
for vertex in range(4):
	if G1.graph[current][vertex]==1: #방문한 적이 있는 정점이면 탈락
    	if vertex in visitedAry:
        	pass
        else: #방문한 적이 없으면 다음 정점으로 지정
        	next=vertex
            break
if next!=None: #다음에 방문할 정점이 있는 경우
	current-next
    stack.append(current)
    visitedAry.append(current)
else: #다음에 방문할 정점이 없는 경우
	current=stack.pop()

⑤과정(정점 D 방문)

현재 정점 B 다음으로 방문할 정점이 없어 스택에서 정점 C를 팝하여 현재 정점으로 지정

정점 C와 연결된 정점 중 A 와 B는 방문한 적이 있으므로 탈락시킴

정점 D를 방문하려고 현재 정점(current)으로 설정한 후 스택고 ㅏ방문 기록에 넣음

 

⑥과정(되돌아오는 이동)

정점 D와 연결된 정점 A와 C 둘 다 방문한 적이 있어 더 방문할 정점을 못 찾아 스택에서 ㅓㅇ점 D를 다시 팝하여 현재 정점으로 지정

 

⑦과정(되돌아오는 이동)

현재 정점 D 다음으로 방문할 정점이 없어 스택에서 정점 A를 팝함

다음 정점을 방문하기 전에 스택이 비어 있다면 모든 정점을 방문한 것임

반복문 종료.

 

깊이 우선 탐색 구현

#클래스와 함수 선언 부분
class Graph():
	def __init__ (self, size):
    	self.SIZE=size
        self.graph=[[0 for _ in range(size)] for _ in range(size)]
        
#전역 변수 선언 부분
G1=None
stack=[]
visitedAry=[] #방문한 정점

#메인코드
G1=Graph(4)
G1.graph[0][2]=1; G1.graph[0][3]=1
G1.graph[1][2]=1
G1.graph[2][0]=1; G1.graph[2][1]=1; G1.graph[2][3]=1
G1.graph[3][0]=1; G1.graph[3][2]=1

print('G1 무방향 그래프')
for row in range(4):
	for col in range(4):
    	print(G1.graph[row][col], end=' ')
    print()
    
current=0 #시작 정점
stack.append(current)
visitedAry.append(current)

while (len(stack)!=0):
	next=None
    for vertex in range(4):
    	if G1.graph[current][vertex]==1:
        	if vertex in visitedAry: #방문한 적이 있는 정점이면 탈락
            	pass
            else: #방문한 적이 없으면 다음 정점으로 지정
            	next=vertex
                break
                
                
    if next!=None: #다음에 방문할 정점이 있는 경우
    	current=next
        stack.append(current)
        visitedAry.append(current)
    else: #다음에 방문할 정점이 없는 경우
    	current=stack.pop()
        
print('방문순서->', end=' ')
for i in visitedAry:
	print(chr(ord('A')+i), end=' ')

 

Section03. 그래프의 응용

그래프의 정점이 모두 연결되었는지 확인하는 함수 작성

신장 트리 및 최소 비용 신장 트리

 

1. 친구가 연락되는지 호가인

특정한 친구가 연락되는지 확인하는 방법 살펴보기

비상연락망은 모든 친구가 연결되어 있어야 함

그래프 순회를 활용해서 모임 대표부터 시작하여 연결된 모든 친구에게 연락하기

특정 친구가 연락되었는지 여부 확인하는 방식 사용

 

우선 화사만 동떨어진 그래프의 인접 행렬 생성

gSize=6
G1=Graph(gSize)
G1.graph[문별][솔라]=1; G1.graph[문별][휘인]=1
G1.graph[솔라][문별]=1; G1.graph[솔라][쯔위]=1
G1.graph[휘인][문별]=1; G1.graph[휘인][쯔위]=1
G1.graph[쯔위][솔라]=1; G1.graph[쯔위][휘인]=1; G1.graph[쯔위][선미]=1
G1.graph[선미][쯔위]=1;

정점인 문별부터 방문을 시작하여 연결된 모든 친구에게 연락하고 그 결과를 visitedAry에 저장

stack=[]
visitedAry=[] #방문한 정점

current=0 #시작 정점
stack.append(current)
visitedAry.append(current)

while (len(stack)!=0):
	next=NNone
    for vertex in range(gSize):
    	if G1.graph[current][vertex]!=0:
        	if vertex in visitedAry: #방문한 적이 있는 정점이면 탈락
            	pass
            else: #방문한 적이 없으면 다음 정점으로 지정
            	next=vertex
                break
                
    if next!=None: #다음에 방문할 정점이 있는 경우
    	current=next
        stack.append(current)
        visitedAry.append(current)
    else: #다음에 방문할 정점이 없는 경우
    	current=stack.pop()

순회 결과인 visitedAry에 화사가 들어 있는지 확인하면 그래프에 연결된 상태인지 알 수 있음

if 화사 in visitedAry:
	print('화사가 연락이 됨')
else:
	print('화사가 연락이 안됨 ㅠ')

특정 정점이 그래프에 연결되어 있는지 확인하는 함수

gSize=6
def findVertex(g, findVtx):
	stack=[]
    visitedAry=[] #방문한 정점
    
    current=0 #시작 정점
    stack.append(current)
    visitedAry.append(current)
    
    while (len(stack)!=0):
    	next=None
        for vertex in range(gSize):
        	if g.graph[current][vertex]!=0:
            	if vertex in visitedAry: #방문한 적이 있는 정점이면 탈락
                	pass
                else: #방문한 적이 없으면 다음 정점으로 지정
                	next=vertex
                    break
            if next!=None: #다음에 방문할 정점이 있는 경우
            	current=next
                stack.append(current)
                visitedAry.append(current)
            else: #다음에 방문할 정점이 없는 경우
            	current=stack.pop()
                
        if findVtx in visitedAry:
        	return True
        else:
        	return False

 

2. 최소 비용으로 자전거 도로 연결

최소 간선으로 모든 정점이 연결되는 그래프인 신장 트리를  이용하여 최소 비용이 들게 우리나라 각 도시를 연결하는 자전거 도로 계획을 세움

 

🤎최소 신장 트리 개념

신장 트리(Spanning Tree): 최소 간선으로 그래프의 모든 정점이 연결되는 그래프

특징: 간선 개수가 '정점 개수-1'을 가짐

-최소 비용 신장 트리(Minimum Cost Spanning Tree): 가중치 그래프에서 만들 수 있는 신장 트리 중 합계가 최소인 것

-활용: 도시 간 도로를 건설할 때 가장 적은 비용으로 도로망을 구축하는 방법

-최소 비용 산장 트리를 구현하는 방법: 프림(Prim) 알고리즘, 크루스컬(Kruskal) 알고리즘

 

🤎전체 자전거 도로를 위한 가중치 그래프 구현

가중치가 없는 무방향 그래프는 간선이 연결되면 1, 연결되지 않으면 0

가중치 그래프는 간선이 연결되면 1 대신 가중치를, 연결되지 않으면 0으로 처리

G1=None
nameAry=['춘천', '서울', 속초', '대전', '광주', '부산']
춘천, 서울, 속초, 대전, 광주, 부산=0,1,2,3,4,5

gSize=6
G1=graph(gSize)
G1.graph[춘천][서울]=10; G1.graph[춘천][속초]=15
G1.graph[서울][춘천]=10; G1.graph[서울][속초]=40; G1.graph[서울][대전]=11; G1.graph[서울][광주]=50
G1.graph[속초][춘천]=15; G1.graph[속초][서울]=40; G1.graph[속초][대전]=12
G1.graph[대전][서울]=11; G1.graph[대전][속초]=12; G1.graph[대전][광주]=20; G1.graph[대전][부산]=30
G1.graph[광주][서울]=50; G1.graph[광주][대전]=20; G1.graph[광주][부산]=25
G1.graph[부산][대전]=30; G1.graph[부산][광주]=25

 

🤎가중치와 간선 목록 생성

edgeAry\[]
for i in rangE(gSize):
	for k in range(gSize):
    	if G1.graph[i][k]!=0:
        	edgeAry.append([G1.graph[i][k], i, k])

 

🤎간선 정렬

정렬할 항목: [가중치, 출발도시, 시작 도시]

operator 패키지에 있는 itemgetter()를 사용하여 정렬할 항목 위치를 선택

itemgette(위치)는 위치에 해당하는 값을 선택해서 정렬하도록 도와줌

sorted()함수는 첫 번째 매개변수인 edgeAry 배열을 정렬

key=itemgetter(0)은 정렬하는 기준을 0번째로 한다는 의미

edgeAry는 [가중치, 출발도시, 시작도시]로 되어 있으므로 가중치로 정렬

reverse=True는 낼미차순으로 정렬한다는 의미

가중치가 큰 간선부터 정렬되고 무방향임

from operator import itemgetter
edgeAry=sorted(edgeAry, key=itemgetter(0), reverse=True)

🤎중복 간선 제거

동일한 간선이 2개씩 배치되었으므로 짝수만 추출해서 새로운 배열에 저장

nesAry=[]
for i in range(0, len(edgeAry), 2):
	newAry.append(edgeAry[i])

🤎가중치가 높은 간선부터 제거

도시를 연결할 때 모든 도시는 서로 연결되어 서로 방문이 가능해야 함

①서울-광주 간선 제거

가중치 배열 newAry에서 제거할 위치를 가리키는 index변수를 서울-광주 간선이 있는 0으로 놓고, 서울-광주와 광주-서울 간선을 제거한 후 가중치 배열에서 완전히 제거

index=0

start=newAry[index][1] #서울
end=newAry[index][2] #광주

G1.graph[start][end]=0
G1.graph[end][start]=0

del(newAry[index])

②서울-속초 간선 제거

index=0
start=newary[index][1] #서울
end=newAry[idndex][2] #속초

G1.graph[start][end]=0
G1.graph[end][start]=0

del(newAry[index])

③대전-부산 간선 제거

index=0
start=newary[index][1] #대전
end=newAry[idndex][2] #부산

G1.graph[start][end]=0
G1.graph[end][start]=0

del(newAry[index])

④광주-부산 간선의 제거 시도와 원상 복구

광주-부산 간선은 제거함녀 부산이 동떨어진 정점이 됨

그러므로 광주-부산 간선 제거를 취소하고 index 변수를 다음 칸으로 옮겨야 함

가중치 배열 newAry에서 제거할 위치를 가리키는 index 변수는 현재 광주-부산 간선이 있는 0

복구를 대비하여 saveCost 변수에 기존 가중치를 저장

광주-부산, 부산-광주 간선을 제거한 후

findVertex()함수를 이용하여 제거도니 각 정점(광주, 부산)이 기존 그래프와 동떨어져 있는지 체크

둘 중 하나라도 그래프와 동떨어졌다면 저장해 놓은 가중치 saveCost로 간선을 복구

가중치 배열 newAry에서 index를 1증가시켜 제거할 위치를 배열의 다음 위치로 이동시킴

index=0

start=newAry[index][1] #광주
end=newAry[index][2] #부산
saveCost=newAry[index][0]

G1.graph[start][end]=0
G1.graph[end][start]=0

startYN=findVertex(G1, start)
endYN=findVertex(G1, end)

if startYN and endYN: #두 정점 모두 그래프와 연결되어 있다면
	del(newAry[index]) #가중치 배열에서 완전히 제거
else:
	G1.graph[start][end]=saveCost
    G1.graph[end][start]=saveCost
    index+=1

⑤대전-광주 간선의 제거 시도와 원상 복구

동떨어진 지점이 되므로 같은 방식 이용

index=1 #배열의 1번째 위치(대전-광주)ㅡ 앞 단계에서 index를 1증가시킴
#나머지는 앞코드와 동일

⑥춘천-속초 간선 제거

동떨어진 정점 없음

이제 남은 간선 5개고 최소 신장 트리 간선 개수랑 동일하므로 완성

 

🤎자전거 도로 건설을 위한 최소 비용 신장 트리의 전체 코드

#클래스와 함수 선언
class Graph():
	def __init__ (self, size):
    	slef.SIZE=size
        self.graph=[[0 for _ in range(size)] for _ in range(size)]
        
def printGraph(g):
#생략

def findVertex(g, findVtx):
#생략

#전역변수

G1=None
nameAry=['춘천', '서울', 속초', '대전', '광주', '부산']
춘천, 서울, 속초, 대전, 광주, 부산=0,1,2,3,4,5

#메인코드
gSize=6
G1=graph(gSize)
G1.graph[춘천][서울]=10; G1.graph[춘천][속초]=15
G1.graph[서울][춘천]=10; G1.graph[서울][속초]=40; G1.graph[서울][대전]=11; G1.graph[서울][광주]=50
G1.graph[속초][춘천]=15; G1.graph[속초][서울]=40; G1.graph[속초][대전]=12
G1.graph[대전][서울]=11; G1.graph[대전][속초]=12; G1.graph[대전][광주]=20; G1.graph[대전][부산]=30
G1.graph[광주][서울]=50; G1.graph[광주][대전]=20; G1.graph[광주][부산]=25
G1.graph[부산][대전]=30; G1.graph[부산][광주]=25


print('자전거 도로 건설을 위한 전체 연결도')
printGraph(G1)

#가중치 간선 목록
edgeAry=[]
for i in range(gSize(:
	for k in range(gSize):
    	if G1.graph[i][k]!=0:
        	edgeAry.append([G1.graph[i][k], i, k])
            
from operator import itemgetter
edgeAry=sorted(edgeAry, key=itemgetter(0), reverse=True)

newAry=[]
for i in range(0, len(edgeAry), 2):
	newAry.append(edgeAry[i])
    
index=0
while (len(newAry)>gSize-1): #간선 개수가 '정점개수-1'일 때까지 반복
	start=newAry[index][1]
    end=newAry[index][2]
    saveCost=newAry[index][0]
    
    G1.graph[start][end]=0
    G1.graph[end][start]=0
    
    startYN=findVertex(G1, start)
    endYN=findVertex(G1, end)
    
    if startYN and endYN:
    	del(newAry[index])
    else:
    	G1.graph[start][end]=saveCost
        G1.graph[end][start]=saveCost
        index+=1
        
print('최소 비용의 자전거 도로 연결도')
print(Graph(G1))

 

<연습문제>

1. 정답) 회사 조직도

 

2. 정답)4

 

3. 정답) 4

 

4. 정답) 문별->솔라->휘인->쯔위->선미->화사

 

5.

0111

1010

1101

1010

 

6. 정답)3스택

 

7. 정답)2