Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs, DFS, BFS - Coggle Diagram
Graphs
Paths and circles
-
A path from vertex u to vertex v of a graph G can be defined as a sequence of adjacent (connected by an edge) vertices that starts with u and ends with v
A cycle is a path of a positive length that starts and ends at the same vertex and does not traverse the same edge more than once
Graphs representation
Adjacency matrix
is an n × n boolean matrix with one row and one column for each of the graph’s vertices, in which the element in the i-th row and the j-th column is equal to 1 if there is an edge from the i-th vertex to the j-th vertex, and equal to 0 if there is no such edge
Adjacency lists
is a collection of linked lists, one for each vertex, that contain all the vertices adjacent to the list’s vertex
Weighted graphs
is a graph (or di- graph) with numbers assigned to its edges. These numbers are called weights or costs
Informally thought of as a collection of points in the plane called “vertices” or “nodes,” some of them connected by line segments called “edges” or “arcs.”
Formally, a graph G = ⟨V , E⟩ is defined by a pair of two sets: a finite nonempty set V of items called vertices and a set E of pairs of these items called edges
A graph with relatively few possible edges missing is called dense; a graph with few edges relative to the number of its vertices is called sparse
DFS
Starts a graph’s traversal at an arbitrary vertex by marking it as visited. On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in.
for the adjacency matrix representation, the traversal time is in (|V |2), and for the adjacency list representation, it is in (|V | + |E|) where |V | and |E| are the number of the graph’s vertices and edges, respectively
BFS
It proceeds in a concentric manner by visiting first all the vertices that are adjacent to a starting vertex, then all unvisited vertices two edges apart from it, and so on, until all the vertices in the same connected component as the starting vertex are visited