Graph theory

23 Feb 2018 | Algorithm

Graph

A grah is a collection of points (vertices, nodes) and line (edges, arcs) connectiong some subset of them. G(V,E)

Methods to store a graph

1. Adjacency Matrix: a square matrix - Matrix[i][j] = 1 , Matrix[i][j] = 0
2. Adjacency List: a collection of unordered list - Vector or List to store adjacency list

Directed and Undirected Graph

Directed = Unidirectional : <– or –>
Undirected = Bidirectional : <—>

Weighted and Unweighted Graph

Weighted Graph: a graph in which a number is assigned to each edge
Unweighted Graph: the weight of all edges are same (presumably 1)

Path

Path: a way of going from one to another.

Degree

Degree: degree of vertex is number of edgeds that are connected to it.

1. In-degree: the number of edgeds that point to the node
2. Out-degree: the number of edgeds the point from the node to other nodes

http://www.csie.ntnu.edu.tw/~u91029/index.html https://www.codechef.com/problems/school