GRAPHS & GRAPHS ALGORITHM
Instructor: Jollibee L. Lacsama
GRAPHS
- A nonlinear data structure that consists of vertices and edges (the vertices
are sometimes referred to as nodes and the edges are lines or arcs that
connect any two nodes in the graph.
- Formally a graphs is composed of a set of vertices(V) and set of edges(E). The
graph is denoted by G(E,V).
COMPONENTS OF A GRAPH:
Vertices – are fundamental units of a graph. Sometimes vertices are also
known as vertex or nodes. Every node/vertex can be labeled or unlabeled.
Edges – are drawn or used to connect two nodes of the graph. It can be
ordered pair od nodes in a directed graph. Edges can connect any two
nodes in any possible way. There are no rules. Sometimes edge can be
labeled or unlabeled.
DIRECTED GRAPH
- Also called digraph, is a graph in which the edges have a direction.
- This is usually indicated with an arrow on the edge; more formally, if v and
w are vertices, an edge is an unordered pair {v, w}, while a directed edge,
called an arc, is an ordered pair, {v, w} or {w, v}.
SEARCHING AND TRAVERSING
GRAPHS
There are two ways to traverse a graph:
1. Breadth First Search (BFS)
- It starts at the root of graph and visits all nodes at the current depth level before moving on to
the nodes at the next depth level.
- Queue data structure is used in BFS.
2. Depth First Search (DFS)
- The algorithm starts at the root(top) node of a tree and goes far as it can down a given
branch(path), then backtracks until it finds an unexplored path, and then explores it. The algorithm does this
until the entire graph has been explored.
- Stack data structure is used in DFS.
BFS VS DFS
