Algorithm: Graph structure

graph-algorithm.md

Graph

It's a one kind of data structure, consists of Node(or Vertex) and Edge which connects between Vertexes. Represented as G = (V,E)

• Path: a path from specific Vertex to another
• Cycle: Starting from A and comes back to starting point
• Simple Path and Simple cycle: The cycle which does not visiting the already passed Vertexes
• Dierected Graph : Path with unidirectional path
• Undirected Graph: Path with bidirectional path, Called Bidirection Graph
• Weight: Could be understood as importance? The weights on the each edges.
• Degree: Connected number of edges on each Vertex

Representation of Graph

Adjacency-matrix

# n = 정점의 개수
# m = 간선의 개수
n, m = map(int, input().split())
print(n, m)
a = []
for i in range(n+1):
    a.append([0]*(n+1))
for i in range(m):
    u, v = map(int, input().split())
    print(u, v)
    a[u][v] = 1
    a[v][u] = 1
for x in a[1:]:
    print(' '.join(map(str,x[1:])))

Adjacency-list

# n = 정점의 개수
# m = 간선의 개수
n, m = map(int, input().split())
#print(n, m)
a = []
for i in range(n+1):
    a.append([])
for i in range(m):
    u, v = map(int, input().split())
    #print(u, v)
    a[u].append(v)
    a[v].append(u)
for (index, x) in enumerate(a[1:]):
    print('a[%d]: '%(index+1) + ' '.join(map(str,x)))

Graph search

Depth First Search & Breadth First Search

# n = 정점의 개수
# m = 간선의 개수
# start = 시작점
n, m, start = map(int, input().split())
#print(n, m)
a = []
for i in range(n+1):
    a.append([])
for i in range(m):
    u, v = map(int, input().split())
    #print(u, v)
    a[u].append(v)
    a[v].append(u)

for i in range(1, n+1):
    a[i].sort()

check = [False] * (n+1)

def dfs(a, check, now):
    # a : 인접리스트
    # check: 방문했는지 안했는지 확인하는 리스트
    # now: 현재 방문한 정점
    if check[now]:
        return
    check[now] = True
    print(now, end=' ')
    for nextVertex in a[now]:
        # now -> nextVertex
        dfs(a, check, nextVertex)

dfs(a, check, start)
print()

def bfs(a, start):
    # start 정점에서 시작
    check = [False] * (n+1)
    queue = []
    queue.append(start)
    check[start] = True
    while queue:
        now = queue[0]
        queue.pop(0)
        print(now, end=' ')
        for nextVertex in a[now]:
            # now -> nextVertex
            if check[nextVertex] == True:
                continue
            queue.append(nextVertex)
            check[nextVertex] = True

bfs(a, start)
print()