Graphs

Question 1

Basics 1

Answer 1

• A collection of nodes that may or may not be connected between them
• Nodes are vertices and may be represented as integers, and relations between vertices are edges
• Cycles:
  * Occur in a graph when three or more vertices are connected to form a closed-loop
  * On interview questions must clarify what exactly constitutes a cycle

Question 2

Basics 2

Answer 2

• A graph can be represented by a list or hash table that contains two things: the list of nodes, and the list of the edges of every vertice
• Traversing a graph has two ways:
  * Depth-First Search: start traversing deep first by starting on one node and then going deep into that node
  * Breadth-First Search: start traversing wider first by starting on one node and then for all the edges of that node

Question 3

Types 1

Answer 3

• Connected graph:
  * When for every pair of vertices there’s a path of one or more edges that connect them. For example the graph of rooms of a house
• Types:
  * Strongly connected: if there are bidirectional connections between every pair of vertices
  * Weakly connected: if there are connections, not necessarily bidirectional, between every pair of vertices

Question 4

Types 2

Answer 4

• Directed graph: when the edges can only be traversed in one specific direction. For example a graph of airports and flights
• Undirected graph: when the edges can be traversed in every direction. For example a graph of friends
• Cyclic graph: when a graph has at least one cycle
• Acyclic graph: when a graph has no cycles

Question 5

Space-time complexities

Answer 5

• Initializing a graph is a linear operation. It’s O(V+E) S, where V is the number of vertices and E is the total number of edges for every node