Graphs, DFS, BFS - Python

생성일: 2021년 11월 22일 오후 6:48

stack 과 queue는 이미 구현되어 있다고 가정

DFS와 BFS를 재귀로 구현해보는 것도 좋을 듯

GraphType.py

from QueType import *
from StackType import *

NULL_EDGE = 0

def index_is(vertices, vertex):
    index = 0

    while index < len(vertices) and vertex != vertices[index]:
        index += 1

    if not index < len(vertices):
        return -1
    else:
        return index

class GraphType:
    def __init__(self, maxV=50):
        self.numVertices = 0
        self.maxVertices = maxV
        self.vertices = [None] * maxV
        self.edges = [[NULL_EDGE] * maxV for _ in range(maxV)]
        self.marks = [None] * maxV

    def add_vertex(self, vertex):
        '''[1]'''
        self.vertices[self.numVertices] = vertex
        self.numVertices += 1

    def add_edge(self, fromVertex, toVertex, weight):
        '''[2]'''
        row = index_is(self.vertices, fromVertex)
        col = index_is(self.vertices, toVertex)
        self.edges[row][col] = weight

    def weight_is(self, fromVertex, toVertex):
        '''[3]'''
        row = index_is(self.vertices, fromVertex)
        col = index_is(self.vertices, toVertex)
        return self.edges[row][col]        

    def get_to_vertices(self, vertex, adjVertices):
        '''[4]'''
        fromIndex = index_is(self.vertices, vertex)
        for toIndex in range(0, self.numVertices):
            if (self.edges[fromIndex][toIndex] != NULL_EDGE):
                adjVertices.enqueue(self.vertices[toIndex])

    def clear_marks(self):
        '''[5]'''
        for i in range(0, self.numVertices):
            self.marks[i] = False

    def is_marked(self, vertex):
        '''[6]'''
        index = index_is(self.vertices, vertex)

        return self.marks[index] == True

    def mark_vertex(self, vertex):
        '''[7]'''
        index = index_is(self.vertices, vertex)
        self.marks[index] = True

    def delete_edge(self, fromVertex, toVertex):
        '''[8]'''
        row = index_is(self.vertices, fromVertex)
        col = index_is(self.vertices, toVertex)
        self.edges[row][col] = NULL_EDGE

testgraph.py

from GraphType import *

if __name__ == '__main__':
    graph = GraphType()

    graph.add_vertex("dog")
    graph.add_vertex("cat")
    graph.add_vertex("animal")
    graph.add_vertex("vertebrate")
    graph.add_vertex("oyster")
    graph.add_vertex("shellfish")
    graph.add_vertex("invertebrate")
    graph.add_vertex("crab")
    graph.add_vertex("poodle")
    graph.add_vertex("monkey")
    graph.add_vertex("banana")
    graph.add_vertex("dalmatian")
    graph.add_vertex("dachshund")

    graph.add_edge("vertebrate", "animal", 10)
    graph.add_edge("invertebrate", "animal", 20)
    graph.add_edge("dog", "vertebrate", 30)
    graph.add_edge("cat", "vertebrate", 40)
    graph.add_edge("monkey", "vertebrate", 50)
    graph.add_edge("shellfish", "invertebrate", 80)
    graph.add_edge("crab", "shellfish", 70)
    graph.add_edge("oyster", "invertebrate", 80)
    graph.add_edge("poodle", "dog", 90)
    graph.add_edge("dalmatian", "dog", 100)
    graph.add_edge("dachshund", "dog", 110)

    print("Weight of 'vertebrate to animal' is", graph.weight_is("vertebrate", "animal"))
    print("Weight of 'poodle to dog' is", graph.weight_is("poodle", "dog"))

    print()
    print("Delete edge(\"poodle\",\"dog\")")
    graph.delete_edge("poodle", "dog")
    print("Weight of 'poodle to dog' is", graph.weight_is("poodle", "dog"))

DFSearch.py

from GraphType import *

def depth_first_search(graph, startVertex, endVertex):
    stack = StackType()
    vertexQ = QueType()
    found = False

    '''[9]'''
    graph.clear_marks()
    stack.push(startVertex)

    while(True):
        vertex = stack.top()
        stack.pop()
        if(vertex == endVertex):
            print(vertex)
            found = True
        else:
            if (not graph.is_marked(vertex)):
                graph.mark_vertex(vertex)
                print(vertex)
                graph.get_to_vertices(vertex, vertexQ)

                while(not vertexQ.is_empty()):
                    item = vertexQ.dequeue()
                    if(not graph.is_marked(item)):
                        stack.push(item)
        
        if(stack.is_empty() or found):
            break

    if(not found):
        print("Path not found.")

BFSearch.py

from GraphType import *

def breadth_first_search(graph, startVertex, endVertex):
    queue = QueType()
    vertexQ = QueType()
    found = False

    '''[10]'''
    graph.clear_marks()
    queue.enqueue(startVertex)

    while(True):
        vertex = queue.dequeue()

        if(vertex == endVertex):
            print(vertex)
            found = True
        else:
            if(not graph.is_marked(vertex)):
                graph.mark_vertex(vertex)
                print(vertex)
                graph.get_to_vertices(vertex, vertexQ)

                while(not vertexQ.is_empty()):
                    item = vertexQ.dequeue()
                    if (not graph.is_marked(item)):
                        queue.enqueue(item)
        if(queue.is_empty() or found):
            break
    
    if(not found):
        print("Path not found.")

testsearch.py

from GraphType import *
from BFSearch import *
from DFSearch import *

if __name__ == '__main__':
    graph = GraphType()

    graph.add_vertex("dog")
    graph.add_vertex("cat")
    graph.add_vertex("animal")
    graph.add_vertex("vertebrate")
    graph.add_vertex("oyster")
    graph.add_vertex("shellfish")
    graph.add_vertex("invertebrate")
    graph.add_vertex("crab")
    graph.add_vertex("poodle")
    graph.add_vertex("monkey")
    graph.add_vertex("banana")
    graph.add_vertex("dalmatian")
    graph.add_vertex("dachshund")

    graph.add_edge("vertebrate", "animal", 10)
    graph.add_edge("invertebrate", "animal", 20)
    graph.add_edge("dog", "vertebrate", 30)
    graph.add_edge("cat", "vertebrate", 40)
    graph.add_edge("monkey", "vertebrate", 50)
    graph.add_edge("shellfish", "invertebrate", 80)
    graph.add_edge("crab", "shellfish", 70)
    graph.add_edge("oyster", "invertebrate", 80)
    graph.add_edge("poodle", "dog", 90)
    graph.add_edge("dalmatian", "dog", 100)
    graph.add_edge("dachshund", "dog", 110)

    print()
    print("DepthFirstSearch(graph, \"dalmatian\", \"animal\")")
    depth_first_search(graph, "dalmatian", "animal")

    print()
    print("BreadthFirstSearch(graph, \"dalmatian\", \"animal\")")
    breadth_first_search(graph, "dalmatian", "animal")