Graph Structure

Question 1

Bipartite Graph

Answer 1

Vertices can be divided into 2 sets A and B such that every edge has connection between A and B. And no edge connects the vertices of the same set
Use color code to differentiate. Use opposite color to the neighbours
E = O(V^2)

Question 2

Bipartite Graph - no cycles

Answer 2

Bipartite graphs do not contain odd length cycles.
If A->B-C forms a triangle then we can’t put B-C in other set as there shouldn’t be any connection between two vertices in one set

Question 3

Cycles

Answer 3

Starts and ends with same vertex

Question 4

Acyclic

Answer 4

no cycles

Question 5

Dense/Sparse tree

Answer 5

Dense: Number of edges close to Max.
Sparse: Number of edges close to Min

Question 6

Tree

Answer 6

E = V-1 edges.
Acyclic
Sparse tree. As max of V-1 edges. Has unique path between any of part of vertices

Question 7

Simple Graph

Answer 7

No self-loop edges
No multiple parallel edges
Num of edges : 0 to V^2

Question 8

Adjacent Vertices

Answer 8

Undirected:If edge exists between two vertices
Directed: 0 ->1 0 is adjacent to 1, but not otherwise

Question 9

Adjacent Edges

Answer 9

If the two edges have common node
(0,2) (2,4) 2 is common

Question 10

Degree of Vertex

Answer 10

Undirected: Number of connections
Directed: in-degree/out-degress: num of in / out connections

Question 11

Connected Graph

Answer 11

If there is a path between every pair of vertices. Meaning we should be able to reach any other node in a Graph.

Question 12

connected components

Answer 12

If graph has disjoint subgraphs and each subgraph is a component. See if deleting any edge forms connected components and that edge is called cut/bridge for vertex/edge

Question 13

Adjacency Matrix (AM)

Answer 13

2D array - 1 has connection 0 has no connection
Space: O(V^2)
Time: O(1) read/write
use for small number of edges

Question 14

Adjacency List (AL)

Answer 14

Create V number of rows and each row contains list of of connections.
For weighted use PAIR to store vertex and weight
Space: O(V+E)
Add Edge: O(1). just append to the list
Search/Check : O(degree(v))

Question 15

DFS

Answer 15

Time: O(V+E)
Space: O(V)

Question 16

BFS

Answer 16

Time: O(V+E)
Space: O(V)

Question 17

Topological sorting

Answer 17

Time: O(V+E)
Space: O(V)

Question 18

SSSP

Answer 18

https://anshika-bhargava0202.medium.com/revisiting-graph-algorithms-47b08f307255#:~:text=The%20space%20complexity%20for%20adjacency,v%20need%20to%20be%20traversed.

Question 19

EL

Answer 19

Edges sorted by vertex number ascending. In undirected marked both ways
Space: O(E)
more efficient than AM & AL
Krushal’s algorithms is sample

Question 20

Drawing

Answer 20

DAG -> use fish shape
Complete -> square

Question 21

Neighbours frequently enumerated

Answer 21

AM,AL.
Check for size and drop AM if bigger

Question 22

Frequently Asked

Answer 22

AM. Check for size

Question 23

Edges needs to be sorted

Answer 23

Edge List