CH 9 Priority Queues, Heaps, and Graphs
Priority Queues
Priority Queue
- Queue의 item들 사이에 우선 순위가 존재하는 것
- ex1) item 값이 클수록 우선 순위가 높다
- ex2) item 값이 작을수록 우선 순위가 높다
- 높은 우선 순위를 가진 요소가 언제라도 접근 가능한 위치에 존재하는 Queue
- Dequeue를 실행했을 때 우선 순위가 높은 순서대로 Dequeue
Implementation Level
- Unsorted List
- 우선 순위가 높은 item 찾기 O(N)
- 우선 순위가 높은 item Dequeue O(1)
- item이 삭제된 자리가 비어 있기 때문에 뒤에 존재하는 item들 한 칸씩 앞으로 Shift O(N)
- Array-Based Sorted List
- 우선 순위로 정렬돼 있기 때문에 item 삭제는 O(1) 삭제된 부분을 메꾸기 위해 Shift O(N)
- Enqueue 진행하면 우선 순위에 따른 item 위치 찾기 O(N), Insert O(1), 넣을 자리 마련하기 위해 item들 뒤로 한 칸씩 Shift O(N)
- Linked Sorted List
- Enqueue 시에 new item의 우선 순위에 따른 위치를 찾기 위해 O(N)
- Binary Tree
- 평균적으로 item의 위치를 찾는 데 O(log N)
- 정렬 리스트를 tree로 구현한 것처럼 tree가 선형이라면 item 위치 탐색에 O(N)
- Enqueue와 Dequeue 모두 평균적으로 O(log N)
- Heap
- Priority Queue를 저장하기에 제일 자연스러운 방식
- 찾기, Enqueue, Dequeue 모두 O(log N)
PQType.h
class FullPQ {};
class EmptyPQ {};
#include "Max_Heap.h"
template<class ItemType>
class PQType
{
public:
PQType(int max);
~PQType();
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void Enqueue(ItemType newItem);
void Dequeue(ItemType& item);
private:
int length;
HeapType<ItemType> items;
int maxItems;
};
PQType Method
- Enqueue
- length ++
- element 마지막에 newitem 넣기
- ReHeapUp으로 우선 순위로 정렬
template<class ItemType>
void PQType<ItemType>::Enqueue(ItemType newItem)
{
if (length == maxItems)
throw FullPQ();
else
{
length++;
items.elements[length - 1] = newItem;
items.ReheapUp(0, length - 1);
}
}
- Dequeue
- item에 제일 우선 순위가 높은 elements[0] 저장
- elements[0] 자리에 우선 순위가 낮은 length-1 번째 item 덮어씌우기
- length-1 번째 아이템 삭제 (length --)
- ReHeapDown
template<class ItemType>
void PQType<ItemType>::Dequeue(ItemType& item)
{
if (length == 0)
throw EmptyPQ();
else
{
item = items.elements[0];
items.elements[0] = items.elements[length - 1];
length--;
items.ReheapDown(0, length - 1);
}
}
PQType.cpp
template<class ItemType>
PQType<ItemType>::PQType(int max)
{
maxItems = max;
items.elements = new ItemType[max];
length = 0;
}
template<class ItemType>
void PQType<ItemType>::MakeEmpty()
{
length = 0;
}
template<class ItemType>
PQType<ItemType>::~PQType()
{
delete[] items.elements;
}
template<class ItemType>
void PQType<ItemType>::Dequeue(ItemType& item)
{
if (length == 0)
throw EmptyPQ();
else
{
item = items.elements[0];
items.elements[0] = items.elements[length - 1];
length--;
items.ReheapDown(0, length - 1);
}
}
template<class ItemType>
void PQType<ItemType>::Enqueue(ItemType newItem)
{
if (length == maxItems)
throw FullPQ();
else
{
length++;
items.elements[length - 1] = newItem;
items.ReheapUp(0, length - 1);
}
}
template<class ItemType>
bool PQType<ItemType>::IsFull() const
{
return length == maxItems;
}
template<class ItemType>
bool PQType<ItemType>::IsEmpty() const
{
return length == 0;
}
Time Complexcity
Implementation | Enqueue | Dequeue |
---|---|---|
Heap | O(logN) | O(logN) |
Linked-List | O(N) | O(N) |
BST (Balanced) | O(logN) | O(logN) |
BST (Skewed) | O(N) | O(N) |
Heaps
Heap
- 조건 1 모양, 조건 2 순서
- 모양: Complete Binary Tree
- 어떤 node가 child node를 하나만 가지는 경우 left child에만 존재해야 함
- Max heap
- 모든 node에 대해 그 값이 children보다 크거나 같아야 함
- 최대값이 root에 존재
- Min heap
- 모든 node에 대해 그 값이 children보다 작거나 같아야 함
- 최소값이 root에 존재
- Array Representation
- Heap은 Complete tree이기 때문에 array 구현이 간편
- Binary Search Tree와 다르게 Array 중간이 비는 경우가 없음
- 다음 depth로 내려가기 위해서는 해당 depth의 모든 칸이 채워져야 하는 Complete tree이기 때문
- Linked list보다 Array 구현이 간편
- 실제 Heap은 Array로 구현되어 있고 Complete tree 모양은 관념적으로 기억
ReHeapDown
- node를 delete했을 때 중간 부분이 비어 complete tree가 되지 않음
- 위에서 heap이 깨졌을 때 밑으로 가면서 heap으로 다시 만들어 주는 함수
- 자신과 자신의 Child랑 비교했을 때 Child 중에 자기 자신보다 큰 애가 있는 경우
- 해당 node와 child node 중 큰 node랑 swap
- Recursive
template<class ItemType>
void HeapType<ItemType>::ReheapDown_re(int root, int bottom)
{
int maxChild;
int leftChild = root * 2 + 1;
int rightChild = root * 2 + 2;
if (leftChild <= bottom)
{
if (leftChild == bottom)
maxChild = leftChild;
else
{
if (elements[leftChild] <= elements[rightChild])
maxChild = rightChild;
else
maxChild = leftChild;
}
if (elements[maxChild] > elements[root])
{
swap(elements[maxChild], elements[root]);
ReheapDown_re(maxChild, bottom);
}
}
}
- Iterative
template<class ItemType>
void HeapType<ItemType>::ReheapDown(int root, int bottom)
{
int maxChild, leftChild, rightChild;
bool reheaped = false;
leftChild = root * 2 + 1;
while (leftChild <= bottom && !reheaped) {
if (leftChild == bottom)
maxChild = leftChild;
else {
rightChild = root * 2 + 2;
maxChild = (elements[leftChild] <= elements[rightChild]) ? elements[rightChild] : elements[leftChild];
}
if (elements[root] < elements[maxChild]) {
Swap(elements[root], elements[maxChild]);
root = maxChild;
leftChild = root * 2 + 1;
}
else
reheaped = true;
}
}
- maxChild: root 기준 child node 중에 최대값을 가진 node의 위치
- elements[leftChild] == elements[bottom]: root가 하나의 child node만 가지는 경우
- ReHeapDown(maxChild, bottom): swap된 위치 기준으로 위에서 Heap을 깼던 item이 바뀐 위치에서도 Heap을 깨고 있을 경우 다시 정렬
ReHeapUp
- node를 insert 했을 때 Array의 마지막에 삽입되는데, 새로운 node 때문에 Heap이 깨짐
- child 중 right most (가장 오른쪽에 있는 item) 때문에 Heap이 깨지는 경우
- Heap을 깨는 item을 root 방향으로 올림
- Recursive
template<class ItemType>
void HeapType<ItemType>::ReheapUp(int root, int bottom)
{
int parent;
if (bottom > root)
{
parent = (bottom - 1) / 2;
if (elements[parent] < elements[bottom])
{
swap(elements[parent], elements[bottom]);
ReheapUp(root, parent);
}
}
}
- Iterative
template<class ItemType>
void HeapType<ItemType>::ReheapUp(int root, int bottom)
{
int parent;
bool reheaped = false;
while (bottom > root && !reheaped) {
parent = (bottom - 1) / 2;
if (elements[parent] < elements[bottom]) {
Swap(elements[parent], elements[bottom]);
bottom = parent;
}
else
reheaped = true;
}
}
DeleteItem
- Heap의 가장 마지막 아이템 (right most item)을 삭제하려는 item의 위치에 덮어씀
- Heap의 마지막 아이템 삭제
- 삭제하려는 item의 위치에 덮어씌워진 heap의 right most item 때문에 위에서 heap이 깨짐
- ReHeapDown
InsertItem
- 새로운 item을 Heap의 가장 마지막에 넣어 줌
- 새로 넣은 item 때문에 아래에서 Heap이 깨짐
- ReHeapUp
Graphs
Graphs
- graph = (Vertex, Edge)의 튜플
- Vertex: 노드
- Edge: 연결
- Ected graph
- edge(연결)끼리의 방향성이 존재하지 않는 graph
- edge(연결)끼리의 방향성이 존재하지 않는 graph
- Directed graph
- edge(연결)끼리의 방향성이 존재하는 graph
- edge(연결)끼리의 방향성이 존재하는 graph
- Tree는 graph의 특이 케이스 중 하나
Terminology
- Adjacent node: edge로 연결된 이웃 노드
- Path: node A에서 node B로 갈 때 지나가는 vertex들의 집합 (순서를 가짐)
- Complete graph: 어떤 vertex 쌍을 골라도 edge가 존재하는 graph
- Ected일 경우 연결만 존재하면 됨
- nC2개의 edge 존재 n * (n-1) / 2
- Directed일 경우 양방향으로 존재
- nP2개의 edge 존재 n * (n-1)
- Ected일 경우 연결만 존재하면 됨
- Weighted graph: edge마다 weight 존재해서 중요도를 다르게 부여한 graph
Graph Implementation
-
Adjacency Matrix: Array 기본으로 구현
-
Vertices: Vertex에 해당하는 index를 알려 주는 1차원 배열
-
Adjacency Matrix: Vertex끼리의 edge 존재 유무와 weight를 알려 주는 2차원 배열
-
Array Based이기 때문에 충분한 크기를 설정해 둬야 함
-
Vertices의 index를 정렬해 놓으면 Searching 시간을 줄일 수 있음
- Sorted O(logN), Unsorted O(N)
-
-
Adjacency List: Linked-List로 구현
- Vertices: Vertex에 해당하는 index를 알려 주는 1차원 배열
- Vertex list: Vertex 마다 edge로 연결된 다른 노드들을 Linked list로 표현
- 해당 노드에서 뻗어나가는 edge만
- 해당 노드에서 뻗어나가는 edge만
-
Compare
- Adjacency Graph
- dense한 graph에 효과적
- vertex에 비해 edge가 적으면 adjacency matrix 메모리를 많이 낭비하기 때문
- 두 node 사이의 연결성을 빠르게 찾을 수 있음
- Memory = Vertex (N) + Adjacency Matrix (N^2) = N^2
- Adjacency List
- sparse한 graph에 효과적
- vertex에 연결된 edge가 많을수록 edge node라는 공간을 쓸데없이 많이 잡기 때문
- 한 Vertex에 연결된 다른 Vertex를 빠르게 찾을 수 있음
- Memory = Vertex (N) + Adjacency List (N) = N
- Adjacency Graph
Adjacency Matrix Graph
- Adjacency Matrix Graph ADT
template<class VertexType>
class GraphType
{
public:
GraphType();
GraphType(int maxV);
~GraphType();
void AddVertex(VertexType vertex);
void AddEdge(VertexType fromVertex, VertexType toVertex, int weight);
int WeightIs(VertexType fromVertex, VertexType toVertex);
void ClearMarks();
bool IsMarked(VertexType vertex);
void MarkVertex(VertexType vertex);
void GetToVertices(VertexType vertex, QueType<VertexType>& adjVertices);
private:
int numVertices;
int maxVertices;
VertexType* vertices;
int edges[50][50];
bool* marks;
};
- Constructor
- vertices라는 vertex 저장하는 1차원 array 생성
template<class VertexType>
GraphType<VertexType>::GraphType()
{
numVertices = 0;
maxVertices = 50;
vertices = new VertexType[50];
marks = new bool[50];
}
- Destructor
- for 문 돌면서 vertex에 해당하는 edge들도 삭제
template<class VertexType>
GraphType<VertexType>::~GraphType()
{
delete[] vertices;
for (int i - 0; i < maxVertices; i++)
delete[] edges[i];
delete[] marks;
}
- AddVertex
- vertex array에 새로운 vertex 넣어 주기
- 새로운 vertex와 연결된 edge는 모두 NULL 값으로 초기화
- numVertices 수 1 증가
template<class VertexType>
void GraphType<VertexType>::AddVertex(VertexType vertex)
{
vertices[numVertices] = vertex;
for (int index = 0; index < numVertices; index++)
{
edges[numVertices][index] = NULL_EDGE;
edges[index][numVertices] = NULL_EDGE;
}
numVertices++;
}
- AddEdges
- IndexIs: vertex의 index 정보를 저장하는 1차원 배열 vertices와 찾고자 하는 vertex 정보를 입력하면 해당 vertex의 index를 반환해 주는 함수
- row에는 edge가 뻗어나가는 vertex index 저장
- col에는 edge가 들어오는 vertex index 저장
- adjacenct matrix에서 row, col 위치에 해당하는 곳에 edge 삽입
template<class VertexType>
int IndexIs(VertexType* vertices, VertexType vertex)
{
int index = 0;
while (!(vertex == vertices[index]))
index++;
return index;
}
template<class VertexType>
void GraphType<VertexType>::AddEdge(VertexType fromVertex, VertexType toVertex, int weight)
{
int row;
int col;
row = IndexIs(vertices, fromVertex);
col = IndexIs(vertices, toVertex);
edges[row][col] = weight;
}
- WeightIs
- IndexIs: vertex의 index 정보를 저장하는 1차원 배열 vertices와 찾고자 하는 vertex 정보를 입력하면 해당 vertex의 index를 반환해 주는 함수
- row에는 edge가 뻗어나가는 vertex index 저장
- col에는 edge가 들어오는 vertex index 저장
- adjacenct matrix에서 row, col 위치에 해당하는 곳의 edge 반환
template<class VertexType>
int GraphType<VertexType>::WeightIs (VertexType fromVertex, VertexType toVertex)
{
int row;
int col;
row = IndexIs(vertices, fromVertex);
col = IndexIs(vertices, toVertex);
return edges[row][col];
}
- ClearMarks
- travel 시에 방문했는 기록을 남기는 marks Array 초기화
template<class VertexType>
void GraphType<VertexType>::ClearMarks()
{
for (int i = 0; i < numVertices; i++)
marks[i] = false;
}
- IsMarked
- 해당 vertex가 방문한 기록이 있는지 물어보는 메소드
template<class VertexType>
bool GraphType<VertexType>::IsMarked(VertexType vertex)
{
index = IndexIs(vertices, vertex);
return (marks[index] == true);
}
- MarkVertex
- 해당 vertex를 방문했다고 기록하는 메소드
template<class VertexType>
void GraphType<VertexType>::MarkVertex(VertexType vertex)
{
index = IndexIs(vertices, vertex);
marks[index] = true;
}
- GetToVertices
- vertex에서 뻗어나간 edge랑 연결된 vertex를 adjVertices에 Enqueue하는 메소드
template<class VertexType>
void GraphType<VertexType>::GetToVertices(VertexType vertex, QueType<VertexType>& adjVertices)
{
int fromIndex;
int toIndex;
fromIndex = IndexIs(vertices, vertex);
for (toIndex = 0; toIndex < numVertices; toIndex++)
if (edges[fromIndex][toIndex] != NULL_EDGE)
adjVertices.Enqueue(vertices[toIndex]);
}
Adjacency List
Graph Searching
DFS (Depth-First-Search)
- 가장 깊이 있는 노드부터 travel하는 방법
- stack으로 구현 가능
- 원하는 것 찾을 때까지 stack에서 Pop
- Pop method 결과로 나온 item과 직접 연결된 node들 다시 push
- stack의 last in, first out 방식이 가장 얕은 곳에 있는 item이 먼저 pop 되도록 해 줌
template<class VertexType>
void GraphType<VertexType>::DepthFirstSearch(VertexType startVertex, VertexType endVertex)
{
StackType<VertexType> stack;
QueType<VertexType> vertexQ;
bool found = false;
VertexType vertex;
VertexType item;
ClearMarks();
stack.Push(startVertex);
while (!stack.IsEmpty() && !found)
{
stack.Pop(vertex);
if (vertex == endVertex)
{
std::cout << vertex << std::endl;
found = true;
}
else
{
if (!IsMarked(vertex))
{
MarkVertex(vertex);
std::cout << vertex << std::endl;
GetToVertices(vertex, vertexQ);
while (!vertexQ.IsEmpty())
{
vertexQ.Dequeue(item);
if (!IsMarked(item))
stack.Push(item);
}
}
}
}
if (!found)
std::cout << "Path not found." << std::endl;
}
BFS (Breadth-First-Search)
- same depth를 다 둘러보고 다음 level의 노드들을 살피는 travel 방식
- queue로 구현 가능
- 원하는 것 찾을 때까지 queue에서 Dequeue
- Dequeue의 결과로 나온 item과 직접 연결된 node들 다시 Enqueue
- queue의 first in, first out 방식이 같은 depth에 있는 item들부터 나오도록 해 줌
template<class VertexType>
void GraphType<VertexType>::BreathFirstSearch(VertexType startVertex, VertexType endVertex)
{
QueType<VertexType> queue;
QueType<VertexType> vertexQ;
bool found = false;
VertexType vertex;
VertexType item;
ClearMarks();
queue.Enqueue(startVertex);
while (!queue.IsEmpty() && !found)
{
queue.Dequeue(vertex);
if (vertex == endVertex)
{
std::cout << vertex << std::endl;
found = true;
}
else
{
if (!IsMarked(vertex))
{
MarkVertex(vertex);
std::cout << vertex << std::endl;
GetToVertices(vertex, vertexQ);
while (!vertexQ.IsEmpty())
{
vertexQ.Dequeue(item);
if (!IsMarked(item))
queue.Enqueue(item);
}
}
}
}
if (!found)
std::cout << "Path not found." << std::endl;
}
LAP
DeleteEdge
- Edge를 삭제해 주는 method
template<class VertexType>
void GraphType<VertexType>::DeleteEdge(VertexType fromVertex, VertexType toVertex)
{
int row;
int col;
row = IndexIs(vertices, fromVertex);
col = IndexIs(vertices, toVertex);
edges[row][col] = NULL_EDGE;
}
DepthFirstSearch_Recursive
- stack을 사용하지 않고 재귀적 방법으로 DFS 하는 방법
- base case: 시작 위치와 종료 위치가 같을 때
- vertexQ에 시작 위치와 연결된 노드들 Enqueue
- 하나씩 Dequeue하여 startVertex와 비교 (Marked 검사)
- 같지 않을 경우 꺼낸 item을 start로 하여 DFS 실행
template<class VertexType>
bool GraphType<VertexType>::DepthFirstSearch_re(VertexType startVertex, VertexType endVertex)
{
QueType<VertexType> vertexQ;
VertexType vertex;
if (startVertex == endVertex)
{
std::cout << endVertex << std::endl;
return true;
}
GetToVertices(startVertex, vertexQ);
while (!vertexQ.IsEmpty())
{
vertexQ.Dequeue(vertex);
if (vertex != startVertex)
{
if (DepthFirstSearch_re(vertex, endVertex))
{
std::cout << startVertex << std::endl;
return true;
}
}
else
continue;
}
return false;
}
PP
Max_Heap
class HeapType:
elements = []
numElemnents = 0
def ReHeapUp(self, root, bottom):
reheaped = False
while(bottom > root and not reheaped):
parent = (bottom - 1) / 2
if (self.elements[parent] < self.elements[bottom]):
self.elements[parent], self.elements[bottom] = self.elements[bottom], self.elements[parent]
bottom = parent
else:
reheaped = True
def ReHeapDown(self, root, bottom):
reheaped = False
leftChild = root * 2 + 1
while(leftChild <= bottom and not reheaped):
if(leftChild == bottom):
maxChild = leftChild
else:
rightChild = root * 2 + 2
if (self.elements[leftChild] <= self.elements[rightChild]):
maxChild = rightChild
else:
maxChild = leftChild
if(self.elements[root] < self.elements[maxChild]):
self.elements[root], self.elements[maxChild] = self.elements[maxChild], self.elements[root]
root = maxChild
leftChild = root * 2 + 1
else:
reheaped = True
Min_Heap
class HeapType:
elements = []
numElemnents = 0
def ReHeapUp(self, root, bottom):
reheaped = False
while(bottom > root and not reheaped):
parent = (bottom - 1) / 2
if (self.elements[parent] > self.elements[bottom]):
self.elements[parent], self.elements[bottom] = self.elements[bottom], self.elements[parent]
bottom = parent
else:
reheaped = True
def ReHeapDown(self, root, bottom):
reheaped = False
leftChild = root * 2 + 1
while(leftChild <= bottom and not reheaped):
if(leftChild == bottom):
minChild = leftChild
else:
rightChild = root * 2 + 2
if (self.elements[leftChild] >= self.elements[rightChild]):
minChild = rightChild
else:
minChild = leftChild
if(self.elements[root] > self.elements[minChild]):
self.elements[root], self.elements[minChild] = self.elements[minChild], self.elements[root]
root = minChild
leftChild = root * 2 + 1
else:
reheaped = True
PQType
from Max_Heap import *
MAX_ITEMS = 100
class PQType():
def __init__(self):
self.items = HeapType()
self.length = 0
def make_empty(self):
self.length = 0
def enqueue(self, newitem):
if(not self.length == MAX_ITEMS):
self.length += 1
self.items.elements[self.length-1] = newitem
self.items.ReHeapUp(0, self.length-1)
def dequeue(self):
if(not self.length == 0):
item = self.items.elements[0]
self.items.elements[0] = self.items.elements[self.length-1]
self.length -= 1
self.items.ReHeapDown(0, self.length -1)
return item
def is_full(self):
return self.length == MAX_ITEMS
def is_empty(self):
return self.length == 0
Graph
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):
self.vertices[self.numVertices] = vertex
for index in range(self.numVertices):
self.edges[self.numVertices][index] = NULL_EDGE
self.edges[index][self.numVertices] = NULL_EDGE
self.numVertices += 1
def add_edge(self, fromVertex, toVertex, weight):
row = index_is(self.vertices, fromVertex)
col = index_is(self.vertices, toVertex)
self.edges[row][col] = weight
def weight_is(self, fromVertex, toVertex):
row = index_is(self.vertices, fromVertex)
col = index_is(self.vertices, toVertex)
return self.edges[row][col]
def get_to_vertices(self, vertex, adjVertices):
fromIndex = index_is(self.vertices, vertex)
for toIndex in range(self.numVertices):
if(self.edges[fromIndex][toIndex] != NULL_EDGE):
adjVertices.enqueue(self.vertices[toIndex])
def clear_marks(self):
for index in range(self.numVertices):
self.marks[index] = False
def is_marked(self, vertex):
index = index_is(self.vertices, vertex)
return self.marks[index]
def mark_vertex(self, vertex):
index = index_is(self.vertices, vertex)
self.marks[index] = True
def delete_edge(self, fromVertex, toVertex):
row = index_is(self.vertices, fromVertex)
col = index_is(self.vertices, toVertex)
self.edges[row][col] = NULL_EDGE
DepthFistSearch
from GraphType import *
def depth_first_search(graph, startVertex, endVertex):
stack = StackType()
vertexQ = QueType()
found = False
graph.clear_marks()
stack.push(startVertex)
while(not stack.is_empty() and not found):
vertex = stack.top()
stack.pop()
if(vertex == endVertex):
print(endVertex)
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(not found):
print("Path not found.")
BreathFirstSearch
from GraphType import *
def breadth_first_search(graph, startVertex, endVertex):
queue = QueType()
vertexQ = QueType()
found = False
graph.clear_marks()
queue.enqueue(startVertex)
while(not queue.is_empty() and not found):
vertex = queue.dequeue()
if(vertex == endVertex):
print(endVertex)
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(not found):
print("Path not found.")
Author And Source
이 문제에 관하여(CH 9 Priority Queues, Heaps, and Graphs), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@morion002/CH-9-Priority-Queues-Heaps-and-Graphs저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)