アルゴリズムの基礎-グラフィックとツリーについて

🌈 グラフィックとツリーについて

🔥 Graph&Treeとは?

🔥 グラフィックを表示

🔥 隣接リストのナビゲート(DFS、BFS)

🔥 グラフィックサンプル

1.Graph&Treeとは?

1)Graphとは?

パターンは、頂点(頂点、ノード)と幹線(エッジ)からなる振動子材料構造を指す、

.

の図形はG(V,E)と表す、対象との関係のみを表示し、同一の図形であるか否かを判断する

.

図形は無方向図と有方向図に分けられる

無方向図:エッジ(幹線)間無方向の一般図

方向図:エッジ(幹線)間に方向がある図形

を除き、重み付けパターンは、幹線に時間や距離などの重み付けがあるパターンを表す.

回数(度):回数は1つの頂点に接続する辺(幹線)の数

である.

パス(path):edgeとedgeを接続する一連の頂点

ループ:1つの頂点から別の頂点に戻るパスの1つです.

下図では、4->3->1->2が経路であるが、ループである

2)木とは何ですか。

ツリーはGraphであり、ループのない接続Graphであり、

すなわち、

は、経路のみであり、その点を返すことができない図形を表す.

木はedge = vertex -1条件を満たさなければならず、親と子供の関係

がある.

2.図形を表す

パターンの表示方法は、「隣接マトリクス」方法と「隣接リスト」方法に分けられる.

1）隣接行列

vertext(歩ける道があれば1、なければ0、構成行列を「隣接行列」

と呼ぶ.

1から1まではできないので、0(自分では0)、1から4となるので、1は

を表す.

の無方向図では双方向にできるので、隣接行列は対角線で

と互いに整合する.

隣接行列実施例

"""
      - 3 - 
1 - 0       4
      - 2 -
"""
n = 5 # node(vertex) 갯수
d = [ [ 0 for i in range(n) ] for j in range(n)] # 초기 세팅
# 연결된 행렬 위치에 1을 삽입
d[1][0] = d[0][1] = 1 # 1과 0은 연결, 0과 1은 연결되어 1
d[0][3] = d[3][0] = 1 # 0과 3은 연결, 3과 0은 연결되어 1
d[0][2] = d[2][0] = 1 # 0과 2은 연결, 2과 0은 연결되어 1
d[3][4] = d[4][3] = 1 # 3과 4은 연결, 4과 3은 연결되어 1
d[2][4] = d[4][2] = 1 # 2과 4은 연결, 4과 2은 연결되어 1
for i in range(n):
    print(d[i])
"""
[0, 1, 1, 1, 0]
[1, 0, 0, 0, 0]
[1, 0, 0, 0, 1]
[1, 0, 0, 0, 1]
[0, 0, 1, 1, 0]
"""

2）隣接表

個の頂点が接続する頂点リストを隣接リスト

と呼ぶ.

vertext 1に接続するvertextは2、3、4であり、vetext 2には1

のみが接続する.

隣接図実施例

"""
      - 3 - 
1 - 0       4
      - 2 -
"""
n = 5 # node(vertex) 갯수
d = [ [] for i in range(n) ]  # 초기 세팅(정점 갯수만큼 리스트 생성)
d[0].append(1) # 0번 정점을 1,2,3과 연결
d[0].append(2)
d[0].append(3)
d[1].append(0) # 1번 정점을 0과 연결
d[2].append(0) # 2번 정점을 0,4과 연결
d[2].append(4)
d[3].append(0) # 3번 정점을 0,4과 연결
d[3].append(4)
d[4].append(3) # 4번 정점을 2,3과 연결
d[4].append(2)
for i in range(n):
    print(i, d[i])
"""
0 [1, 2, 3]
1 [0]
2 [0, 4]
3 [0, 4]
4 [3, 2]
"""

3)隣接行列vs隣接リスト

隣接行列は、すべての接続(1および0)の2次元配列を含み、接続リストには接続された頂点のみが含まれます.

隣接行列の利点は、2つの頂点(頂点、ノード)の接続関係を直接見ることができる

である.

セグメント、隣接マトリクスの欠点は、隣接点を効率的に検索することが難しく、メモリの浪費が大きいことです.

の隣接テーブルを巡回する必要があるが、2つの頂点(vertext,node)の接続関係を決定できるという欠点があるが、メモリ使用量が少なく、隣接頂点を検索する際に隣接マトリクスよりも効率的である

である.

は、2つの頂点が接続関係を持つかどうかを調べる時間的複雑さ

隣接行列:O(1)

隣接リスト:O(V)

3.隣接リストのナビゲート（DFS、BFS）

1) DFS

"""
      - 3 - 
1 - 0       4
      - 2 -
"""
n = 5 # node(vertex) 갯수
d = [ [] for i in range(n) ]  # 초기 세팅(정점 갯수만큼 리스트 생성)
d[0].append(1) # 0번 정점을 1,2,3과 연결
d[0].append(2)
d[0].append(3)
d[1].append(0) # 1번 정점을 0과 연결
d[2].append(0) # 2번 정점을 0,4과 연결
d[2].append(4)
d[3].append(0) # 3번 정점을 0,4과 연결
d[3].append(4)
d[4].append(3) # 4번 정점을 2,3과 연결
d[4].append(2)
# """
# 0 [1, 2, 3]
# 1 [0]
# 2 [0, 4]
# 3 [0, 4]
# 4 [3, 2]
# """
def dfs(d, pos, vis):
    # d = 연결 리스트
    # pos = 현재 탐색하고 있는 정점 번호
    if vis[pos]:
        return
    print(pos)
    vis[pos] = True
    for i in range(len(d[pos])):
        # d[pos][i] = 현재 보고 있는 pos 정점의 연결되어이 있는 정점들
        dfs(d, d[pos][i], vis)
vis = [False for i in range(n)]
dfs(d,0,vis)

2) BFS

"""
      - 3 - 
1 - 0       4
      - 2 -
"""
from queue import deque
# push
def queue_push(q, value):
    q.append(value)
# pop
def queue_pop(q):
    return q.popleft()
n = 5 # node(vertex) 갯수
d = [ [] for i in range(n) ]  # 초기 세팅(정점 갯수만큼 리스트 생성)
d[0].append(1) # 0번 정점을 1,2,3과 연결
d[0].append(2)
d[0].append(3)
d[1].append(0) # 1번 정점을 0과 연결
d[2].append(0) # 2번 정점을 0,4과 연결
d[2].append(4)
d[3].append(0) # 3번 정점을 0,4과 연결
d[3].append(4)
d[4].append(3) # 4번 정점을 2,3과 연결
d[4].append(2)
# """
# 0 [1, 2, 3]
# 1 [0]
# 2 [0, 4]
# 3 [0, 4]
# 4 [3, 2]
# """
q = deque()
queue_push(q,0)
vis = [False for i in range(n)]
vis[0] = True
while len(q) != 0:
    front = queue_pop(q)
    print(front)
    for i in range(len(d[front])):
        # d[front][i] : 연결되어있는 정점들
        if vis[d[front][i]]:
            continue
        vis[d[front][i]] = True
        queue_push(q, d[front][i])

4.図面例の説明

1)boj 2606号:ウイルス(https://www.acmicpc.net/problem/2606 )

隣接表実施方法

"""
7
6
1 2
2 3
1 5
5 2
5 6
4 7
"""
import sys
n = int(sys.stdin.readline()) # 컴퓨터 수
m = int(sys.stdin.readline()) # 연결된 쌍의 수
d = [[] for i in range(n+1)]
for i in range(m): # 0,1,2,3,4,5
    s, e = list(map(int, sys.stdin.readline().split()))
    # 서로 연결하는 방법
    d[s].append(e)  
    d[e].append(s)
# d 상태 확인
for i in range(1, n+1):
    print(i, d[i])
"""
1 [2, 5]
2 [1, 3, 5]
3 [2]
4 [7]
5 [1, 2, 6]
6 [5]
7 [4]
"""

# boj 2606 : 바이러스
"""
7
6
1 2
2 3
1 5
5 2
5 6
4 7
"""
import sys
from queue import deque
# queue_push
def queue_push(q, v):
    q.append(v)
# queue_pop    
def queue_pop(q):
    return q.popleft()
n = int(sys.stdin.readline()) # 컴퓨터 수
m = int(sys.stdin.readline()) # 연결된 쌍의 수
d = [[] for i in range(n+1)]
for i in range(m): # 0,1,2,3,4,5
    s, e = list(map(int, sys.stdin.readline().split()))
    d[s].append(e)
    d[e].append(s)
ans = 0
visited = [False for i in range(n+1)]
q = deque()
queue_push(q, 1)
visited[1] = True
while len(q) != 0:
    ans += 1
    front = queue_pop(q)
    for i in range(len(d[front])):
        if visited[d[front][i]]:
            continue
        visited[d[front][i]] = True
        queue_push(q, d[front][i])
print(ans-1) # 4

2)boj 1260号:DFSとBFS(https://www.acmicpc.net/problem/1260 )

# boj 1260 : DFS와 BFS
"""
4 5 1
1 2
1 3
1 4
2 4
3 4
"""
import sys
N, M, V = map(int, sys.stdin.readline().split())
d = [ [] for i in range(N+1)]
for i in range(M):
    s,e = list(map(int, sys.stdin.readline().split()))
    d[s].append(e)
    d[e].append(s)
# 가장 작은것 부터 방문하기 위해, 첫번째를 제외하고 sort
for i in range(1, N+1):
	d[i].sort()
# for i in range(N+1):
#     print(i, d[i])
# DFS
def dfs(d, pos, vis):
    print(pos, end=' ')
    vis[pos] = True
    for i in range(len(d[pos])):
        if vis[d[pos][i]]:
            continue
        dfs(d, d[pos][i], vis)
# BFS
from queue import deque
def queue_push(q, value):
    q.append(value)
def queue_pop(q):
    return q.popleft()        
def bfs(N, d, V):
    vis = [False for i in range(N+1)]
    q = deque()
    queue_push(q, V)
    vis[V] = True
    while len(q) != 0:
        front = queue_pop(q)
        print(front, end=' ')
        for i in range(len(d[front])):
            if vis[d[front][i]]:
                continue
            vis[d[front][i]] = True
            queue_push(q, d[front][i])
vis = [False for i in range(N+1)]
dfs(d, V, vis)
print()
bfs(N, d, V)
"""
1 2 4 3
1 2 3 4
"""