그래프

 

그래프의 기본 개념

1. 노드 (Node): 그래프의 정점(Vertex)
2. 간선 (Edge): 두 노드를 연결하는 선
3. 방향 그래프 (Directed Graph): 간선에 방향이 있는 그래프
4. 무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프
5. 가중치 그래프 (Weighted Graph): 간선에 가중치(Weight)가 부여된 그래프
6. 인접 행렬 (Adjacency Matrix): 그래프를 2차원 배열로 표현
7. 인접 리스트 (Adjacency List): 그래프를 리스트의 리스트로 표현

그래프 구조

 

 

코드들

#그래프 정점 집합
V(G1) = {A, B, C, D}
V(G2) = {A, B, C, D}

 

#그래프 간선
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}

 

#방향 그래프 간선
E(G3) = { <A, B>, <A, C>, <D, A>, <D, C> }
E(G4) = { <A, B>, <C, B>, <C, D> }

 

#그래프 생성
class Graph() :
    def __init__ (self, size) :
        self.SIZE = size
        self.graph = [[0 for _ in range(size)] for _ in range(size)]    #4 * 4 크기의 그래프

G1 = Graph(4)

 

#그래프의 정점 연결
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) 간선

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) 간선

 

#무방향 그래프 구현
#함수 선언 부분
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()

## G1 무방향 그래프 ##
0 1 1 1 
1 0 1 0 
1 1 0 1 
1 0 1 0 
## G3 방향 그래프 ##
0 1 1 0 
0 0 0 0 
0 0 0 0 
1 0 1 0

 

#그래프 개선
G1.graph[0][1] = 1; G1.graph[0][2] = 1
G1.graph[1][0] = 1; G1.graph[1][3] = 1

 

#그래프 개선 
문별, 솔라, 휘인, 쯔위 = 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()

  문별 솔라 휘인 쯔위 
문별 0 1 1 1 
솔라 1 0 1 0 
휘인 1 1 0 1 
쯔위 1 0 1 0

 

#무방향 그래프 개선
#클래스와 함수 선언 부분
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(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 = 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)

## G1 무방향 그래프##
    문별 솔라 휘인 쯔위 선미 화사 
문별 0    1    1    0    0    0    
솔라 1    0    0    1    0    0    
휘인 1    0    0    1    0    0    
쯔위 0    1    1    0    1    1    
선미 0    0    0    1    0    1    
화사 0    0    0    1    1    0

 

#깊이 우선 팀색 구현
stack = []
stack.append(값1)    #push(값1) 효과
data = stack.pop()   #data = pop() 효과

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

 

#스택 
visitiedAry = []
visitedAry.append(0)    #정덤 a(번호 0)를 방문했을 때
visitedAry.append(1)    #정점 b(번호 1)를 방문했을 때

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

 

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

 

#첫번째 정점 방문
current = 0    #시작 정점
stack.append(current)
visitedAry.append(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)

 

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()

 

#깊이 우선 탐색
#전역 변수 함수
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 = ' ')

## G1 무방향 그래프
0 0 1 1 
0 0 1 0 
1 1 0 1 
1 0 1 0 
방문 순서 --> A C B D