Graphs

G = ( Vertex, Edge )의 튜플

V : 정점(vertices, nodes)들의 집합 _ a finite, nonempty 해야함

E : 정점들 간의 연결(edges)

 

Directed vs Undirected graphs

방향성의 유무 차이.

Directed graph 를 줄여 digraph라고도 함.

방향성 있을 때는 순서쌍의 순서가 중요하다.

Directed Graph vs Undirected Graph

• 트리는 그래프의 특별한 경우.
• Adjacent nodes : 연결되있는 두 노드 [5 is adjacent to 7] & [7 is adjacent from 5]
• Path : 노드 A에서 B로 갈 때 지나가는 노드들의 집합 (순서가 중요하다)
• Complete graph : 어떠한 정점 2개를 골라도 두 정점 사이에 edge가 존재하는 그래프

•  

Graph Terminology

(a) Complete Directed graph

           edge 개수 : N(N-1) 

           시간복잡도 : O(N^2)

(b) Complete undirected graph

           edge 개수 : N(N-1)/2

           시간복잡도 : O(N^2)

 

Weight graph : 중요도 값(weight)을 가진 그래프

Adjacent Matrix 

- Array-Based implementation

- 1차원 : 정점 표기

- 2차원 : 정점끼리의 관계 유무, 중요도 표기

Adjacent List

- Linked-list implementation

- 1차원 : 정점 표기

- 2차원 : 정점마다 edge로 연결되있는 다른 정점 표기 (해당 노드가 가리키고 있는 노드들만)

 

Adjacent Matrix VS  Adjacent List

노드 수에 비해 edge가 적을 때 matrix로 표현하면 0으로 표기되는 부분이 많이 생긴다 = 메모리 낭비

Matrix

    - dense 한 그래프에 효율적

    - 메모리 : O(|V| + |E|) = O(|V^2|)      . . . |E| = |V^2|

List

    - sparse 한 그래프에 효율적

    - 메모리 : O(|V| + |E|) = O(|V|)      . . . |E| = |V|

 

GraphType

GraphType()

template <class VertexType>
GraphType::GraphType(int maxV){
	numVertices = 0;
    maxVertices = maxV;
    vertices = new VertexType [maxV];
    edges = new int* [maxV];
    for(int i = 0; i < numVertices; i++)
    	edges[i] = new int [maxV];
    marks = new bool [maxV];
}

~GraphType()

• vertices,marks는 일차원 배열이니 delete[]
• edges는 2차원 배열이므로 열부터 지워야한다.

template <class VertexType>
GraphType<VertexType>::~GraphType(){

	delete[] vertices;
    delete[] marks;
    for(int i = 0; i < maxVertices; i++)
    	delete[] edges[i];
    delete[] edges;
}

IndexIs(VertexType* vertices, VertexType vertex)

• 1차원 배열 vertices에서 vertex가 저장되어있는 index를 반환해주는 함수

template <class VertexType>
int IndexIs(VertexType* vertices, VertexType vertex){
	int index = 0;
    
    while(vertex != vertices[index])
    	index++;
    return index;
}

AddVertex(VertexType vertex)

• vertices array에 vertex를 저장해준다.
• 해당 vertex와 연결된 edges는 모두 0으로 초기화한다.
• 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_EDGES;
        edges[index][numVertices] = NULL_EDGES;
        }
    numVertices++;
}

AddEdge(VertexType fromVertex, VertexType toVertex, int weight)

template <class VertexType>
void GraphType<VertexType>::AddEgde(VertexType fromVertex, VertexType toVertex, 
									int weight){
                                    
        int row = IndexIs(vertices,fromVertex);
        int column = IndexIs(vertices,toVertex);
        
        edges[row][column] = weight;
    }

 

GetToVertices(VertexType vertex, QueType<VertexType>& adjvertexQ)

• vertex와 adjacent한 점들을 큐에 넣는 함수

template <class VertexType>
void GraphType<VertexType>::GetToVertices(VertexType vertex,QueType<VertexType>& adjvertexQ){
                                          
	int fromIndex,toIndex;
    fromIndex = IndexIs(vertices,vertex);
    for(toIndex= 0; toIndex < numVertices; toIndex++){
    	if(edges[fromIndex][toIndex] != NULL_EDGE)
        	adjvertexQ.Enqueue(vertices[toIndex]);
      }
}

ClearMarks()

• Travel 하면서 방문 여부 체크하는 마킹 초기화

template <class VertexType>
void GraphType<VertexType>::ClearMarks(){
	for(int i = 0; i < numVertices; i++){
    	marks[i] = false;
    }
}

MarkVertex(VertexType vertex)

• Travel 할 때 방문했음을 기록

template <class VertexType>
void GraphType<VertexType>::MarkVertex(VertexType vertex){
	
    int index = IndexIs(vertices,vertex);
    marks[index] = true;
}

IsMarked(VertexType vertex) const

• Travel 할 때 해당 노드 방문 여부를 묻는 함수

template <class VertexType>
bool GraphType<VertexType>::IsMarked(VertexType vertex) const{
	
    int index = IndexIs(vertices, vertex);
    return (marks[index] == true);
}

 

Graph Serching

DFS (Depth - First - Search)

• 가장 deepest 한 노드부터 시작 -> 모든 노드를 방문
• stack 으로 구현
• Pop하면서 직접 연결되어있는 노드들을(adjacent) Push한다.
• 이미 지나간 노드가 아닌지 확인해야한다.(marking)

#include <iostream>
#include "GraphType.h"
#include "StackType.h"
using namespace std;

template <class VertexType>
void DepthFirstSearch(GraphType<VertexType> graph, VertexType startVertex,
					  VertexType endVertex){
                     	
    StackType<VertexType> stack;         //vertex를 담을 스택
    QueType<VertexType> vertexQ;         //adjacent한 노드들을 저장할 큐
    
    bool found = false;
    VertexType vertex;
    VertexType item;
    
    graph.ClearMarks();                  //초기화 하고 시작
    stack.Push(startVertex);             //스택에 시작점을 push 한다.
    do{
    	stack.Pop(vertex);               //pop을 통해 나온 값을 vertex에 저장한다
        if(vertex == endVertex)          //찾고 있던 endVertex면 더이상 조사하지 않는다. 
        	found = true;
        else{
        	if(!graph.IsMarked(vertex){                   //이미 지나간 노드가 아니라면
            	graph.MarkVertex(vertex);                 //지나간 것을 표시하고
                graph.GetToVertices(vertex,vertexQ);      //해당 노드와 adjacent한 점들을 큐에 저장한다.
                }
            while(!vertexQ.IsEmpty()){                    //큐에 아무것도 없을 때까지
            	vertexQ.Dequeue(item);                    //Dequeue, item에 값 저장
                if(!graph.IsMarked(item)                  //지나가지 않은 노드일때만
                	stack.Push(item);                     //스택에 저장
                }
        	}
        }while(!stack.IsEmpty() && !found);
        
    if(!found)
    	cout << "Path not found" << endl;
}

첫 번째 graph.IsMarked(vertex)에서는 pop한 점이 마킹 되있는지 아닌지를 확인하고, 그 점과 adjacent한 노드들을 큐에 넣는다. 

두 번째 graph.IsMarked(vertex)에서는 큐에 넣은 (adjacent한) 점들이 마킹되어있는지 아닌지를 확인한다.

즉, 두 함수는 확인하는 대상이 다르다!

BFS (Breadth - First - Search)

• 같은 depth에 있는 노드들을 먼저 방문 -> deeper level
• queue로 구현
• Dequeue 하면서 직접 연결되있는 노드들을 Enqueue 한다. (DFS와 동일한 방식, FIFO만 다르다)

#include <iostream>
#include "GraphType.h"

template <class VertexType>
void BreadthFirstSearch(GraphType<VertexType> graph, VertexType startVertex,
						VertexType endVertex){
        
        QueType<VertexType> queue;          //vertex를 담을 큐
        QueType<VertexType> vertexQ;        //adjacent한 노드들을 저장할 큐
        
        bool found = false;
        VertexType vertex;
        VertexType item;
        
        graph.ClearMarks();
        queue.Enqueue(startVertex);
        do{
        	queue.Dequeue(vertex);
            if(vertex == endVertex)
            	found = true;
            else{
            	if(!graph.IsMarked(vertex){
                	graph.MarkVertex(vertex);
                    graph.GetToVertices(vertex,vertexQ);
                    }
                    
                while(!vertexQ.IsEmpty()){
                	vertexQ.Dequeue(item);
                    if(!graph.IsMarked(item)
                    	queue.Enqueue(item);
                    }
                }
            }while(!queue.IsEmpty() && !found);
            
        if(!found)
        	cout << "Path not found" << endl;
}

Single-source shortest-path problem

• 특정 노드까지 가는 path 중 가장 weight이 작은 것을 선택 => 알고리즘 시간에 배우자.
• 모든 노드의 weight가 똑같거나 weightless 한 경우, BFS를 이용하면 shortest path를 찾을 수 있다.