유향그래프 : 노드간 연결에 방향이 있는 그래프
먼저 유향 그래프에 대한 예제의 그래프 정보를 파악하자
위 그림과같은 노드간의 연결을 담은 그래프를 파이썬에서 구현하려면 아래와 같이 노드 번호와 해당 노드에서 갈 수 있는(간선이 존재하는) 노드에 대한 정보가 필요하다.
1번 노드에서 갈 수 있는 노드는 3, 4번 노드(화살표 주의)
2번 노드에서 갈 수 있는 노드는 3,4,5번 노드
…….
이를 아래와같은 구조로 저장해야한다.
graph_list = {1: set([3, 4]),
2: set([3, 4, 5]),
3: set([1, 5]),
4: set([1]),
5: set([2, 6]),
6: set([3, 5])}
root_node = 1
BFS 너비우선탐색 알고리즘
from collections import deque
def BFS_with_adj_list(graph, root):
visited = [] # 한번 방문한 노드는 다시 방문하지않도록
queue = deque([root])
while queue:
n = queue.popleft()
if n not in visited:
visited.append(n)
queue += graph[n] - set(visited)
return visited
print(BFS_with_adj_list(graph_list, root_node))
위의 코드는 조금 간략한 버전으로, 아래 코드를 돌려보면 출력문으로 BFS의 노드 방문 과정과, 어떤 판단을 거쳐 방문하는지, 방문하지않는지 알아볼 수 있다.
BFS알고리즘 이해용 코드
from collections import deque
def BFS_with_adj_list(graph, root):
visited = []
queue = deque([root])
iterCountForTest = 1
while queue:
print(f'iteration{iterCountForTest}')
n = queue.popleft()
print(f'popleft result = {n}')
if n not in visited:
visited.append(n)
queue += graph[n] - set(visited)
print(f'visited is = {visited}')
print(f'queue is = {queue}')
iterCountForTest += 1
print('\\n')
return visited
print(BFS_with_adj_list(graph_list, root_node))
DFS
def DFS_with_adj_list(graph, root):
visited = []
stack = [root]
while stack:
n = stack.pop()
if n not in visited:
visited.append(n)
stack += graph[n] - set(visited)
return visited
print(DFS_with_adj_list(graph_list, root_node))
네트워크 개수 문제 다른 두 풀이
# 내 풀이 인데, mylist 선언 후 remove 하는 idea 보다 node visit 아이디어가 더 좋은 것 같아
def solution(n, computers):
answer = 0
mylist = [i for i in range(n)]
def connected_set(node_num):
mylist.remove(node_num)
for i in range(n):
if i in mylist:
if computers[node_num][i] == 1:
connected_set(i)
return 1
for i in range(n):
if i in mylist:
answer += connected_set(i)
return answer
def solution(n, computers):
answer = 0
visited = [0 for i in range(n)] # = [0] * n
def dfs(computers, visited, start):
stack = [start]
while stack:
j = stack.pop()
if visited[j] == 0:
visited[j] = 1
# for i in range(len(computers)-1, -1, -1):
for i in range(0, len(computers)):
if computers[j][i] ==1 and visited[i] == 0:
stack.append(i)
i=0
while 0 in visited:
if visited[i] ==0:
dfs(computers, visited, i)
answer +=1
i+=1
return answer