graphs

Question 1

Draw Eulerian Cycle, if Exists 1

Answer 1

Figure at 8:15

Question 2

directed graph

Answer 2

The edges between any two vertices in a “directed graph” graph are directional.

Question 3

What are entry and exit vertices in Eulerian Path graph

Answer 3

Start and end at two different vertices

Question 4

If number of vertices with odd degree is more than 2, will there be any Eulerian cycle or path?

Answer 4

No. There can only be Eulerian cycle when all vertices are of even degree, and Eulerian path only when 2 of the vertices are odd degree

Question 5

Is graph has to be connected if it needs to have Eulerian cycle?

Answer 5

Not true. One connected component within the graph may be eulerian cycle on it’s own.

Sample picture attached

Question 6

Degree of Vertx

Answer 6

the term “degree” applies to unweighted graphs. The degree of a vertex is the number of edges connecting the vertex. In Figure 1, the degree of vertex A is 3 because three edges are connecting it.

Question 7

Rule of Thumb for “Eulerian Cycle” to exist in a graph

Answer 7

Every degree of the vertex in the connected component must be even to have valid Eulerian Cycle.

Question 8

Connected Component

Answer 8

A piece of graph, within which we can reach from one vertex to other. However we can not move the vertices into one from other connected component without loosing it’s connectedness property

Question 9

If can we draw diagram without lifting pen even once & do not retrace the same line again, and end at the same starting point within a Graph

Answer 9

We call that graph has Eulerian Cycle in it

Question 10

How to draw Eulerian Cycle within given graph?

Answer 10

1) Start walking randomly
2) Keep going until we can walk
3) When there are no choices and no Eulerian cycle exists - back track from final position until where we would have done wrong turn.
4) Start walking randomly again
5) Anytime make sure we have even number of unused vertices, during this back track and mini walks
6) Repeat process

Question 11

Draw Eulerian Cycle, if Exists

Answer 11

picture at 1:11/Eulerian Cycle Construction

Question 12

Eulerian Cycle also known as

Answer 12

Eulerian circuit
Eulerian Tour
Euler Circuit
Euler Tour

Question 13

Path Length

Answer 13

the number of edges in a path. In Figure 1, the path lengths from person A to C are 2, 3, and 5, respectively.

Question 14

Cycle

Answer 14

A path where the starting point and endpoint are the same vertex. In Figure 1, [A, B, D, F, E] forms a cycle. Similarly, [A, G, B] forms another cycle.

Question 15

Eulerian Path

Answer 15

Undirected graph has a non cyclic path that covers each edge exactly once. but doesn’t need to end at same vertex

Question 16

Path

Answer 16

the sequence of vertices to go through from one vertex to another. In Figure 1, a path from A to C is [A, B, C], or [A, G, B, C], or [A, E, F, D, B, C].
**Note**: there can be multiple paths between two vertices.

Question 17

If degree of any vertex in connected component is odd, will there be valid Eulerian Cycle

Answer 17

No. Because there will be no unused Edge to exit at some point in the tour.

Question 18

Is it possible for a graph to have odd number of vertices with odd degree?

Answer 18

No. It’s impossible

Question 19

If graph is connected, and degree of every vertex is even - Does it have Eulerian cycle?

Answer 19

Yes

Question 20

Eulerian Cycle

Answer 20

Undirected graph has a cycle, that covers each edge exactly once. And it comes to same vertex as it started

Question 21

Connectivity

Answer 21

If there exists at least one path between two vertices, these two vertices are connected. In Figure 1, A and C are connected because there is at least one path connecting them.

Question 22

What is the mathematical condition for a graph to have Eulerian Path

Answer 22

Every vertex in graph except only 2 of them should have even degree.
Always the path should start and end at Odd degree vertices.
All other vertices should have even degree, so tour will not be trapped.

Question 23

Negative Weight Cycle

Answer 23

In a “weighted graph”, if the sum of the weights of all edges of a cycle is a negative value, it is a negative weight cycle. In Figure 4, the sum of weights is -3.

Question 24

Draw Eulerian Cycle, if Exists 3

Answer 24

Figure at 8:15

Question 25

Types of graphs

Answer 25

Undirected Directed Unweighted Weighted

Question 26

If connected graph has exactly 2 odd degree vertices, does there a valid Eulerian path exist?

Answer 26

Yes

Question 27

Undirected Graph

Answer 27

The edges between any two vertices in an “undirected graph” do not have a direction, indicating a two-way relationship. Paste sample pic

Question 28

Connected Graph

Answer 28

An undirected graph is connected if we can start from any vertex & reach any other vertex Sample picture

Question 29

Graph

Answer 29

“Graph” is a non-linear data structure consisting of vertices and edges.

Question 30

Is it possible for a graph with single vertex with an odd degree?

Answer 30

No By Maths: sum of degrees = 2 \* number of edges. So it is always even

Question 31

Draw Eulerian Cycle

Answer 31

Sample pic attached from 3:25

Question 32

Weighted Graph

Answer 32

Each edge in a “weighted graph” has an associated weight. The weight can be of any metric, such as time, distance, size, etc. The most commonly seen “weighted map” in our daily life might be a city map.

Question 33

Out degree

Answer 33

“out-degree” is a concept in directed graphs. If the out-degree of a vertex is d, there are d edges incident from the vertex. In Figure 2, A’s outdegree is 3, i,e, the edges A to B, A to C, and A to G.

Question 34

Vertex

Answer 34

nodes such as A, B, and C are called vertices of the graph.

Question 35

Draw Eulerian Cycle, if Exists 2

Answer 35

Figure at 8:15

Question 36

In degree

Answer 36

“in-degree” is a concept in directed graphs. If the in-degree of a vertex is d, there are d directional edges incident to the vertex. In Figure 2, A’s indegree is 1, i.e., the edge from F to A.

Question 37

Edge

Answer 37

The connection between two vertices are the edges of the graph. In Figure 1, the connection between person A and B is an edge of the graph.

Question 38

Is Eulerian Cycle is an Eulerian Path?

Answer 38

Yes

Question 39

Is Eulerian Path is an Eulerian Cycle?

Answer 39

No

Question 40

Few popular ways to represent graphs

Answer 40

Edge Lists Adjacency Lists Adjacency Matrices Adjacency Maps

Question 41

``` Notation to represent number of Vertices in the graph #vertices ```

Answer 41

n or |v|

Question 42

``` Notation to represent number of Edges in the graph #edges ```

Answer 42

m or |E|

Question 43

Simple graph representation among all, but not very efficient

Answer 43

Edge Lists

Question 44

Edge List representation

Answer 44

vertex list = [A, B, C, D, E] - Each element is either object or reference to an object edge list = [a,b,c,d] - Each element is either edge object or reference to edge object Each vertex object Might have city information in it. Each edge object might have distance, source, destination etc., These are unordered lists

Question 45

Maximum number of vertices an undirected graph with n vertices can have? Assumption: Not a multi graph

Answer 45

n choose 2, n \* (n-1)/2, O(n\*2)

Question 46

What exactly is "n choose 2" in probability.

Answer 46

In short, it is the number of ways to choose two elements out of n elements. For example, '4 choose 2' is 6. If I have four elements - A, B, C and D - I can select two elements in the following ways - {A, B}, {A, C}, {A, D}, {B, C}, {B, D} and {C, D}. As for the formula for 'n choose 2'- We have n ways of selecting the first element, and (n - 1) ways of selecting the second element - as we cannot repeat the same element we already selected. So, it looks like the formula should be n(n - 1). However, this way, every subset would be counted twice over. That is, {A, B} and {B, A} would be counted separately, though are equivalent. So, 'n choose 2' is half this number - n(n - 1)/2

Question 47

How do we store when vertices are integers & strings like city names

Answer 47

If it is integers, it can be saved as simple array and referenced by indexes in O(1) If it is something like city names, we can use the hash representation and save it in hash table to enable quick find which is in O(1)

Question 48

Amount of time takes to find all neighbors for given Vertex of graph using Edge List representation

Answer 48

O(m) which is Order of number of edges. As we need to check each and every edge element in Edge list representation to find the matches.

Question 49

Amount of time takes to find all neighbors for each vertex of graph using Edge List representation

Answer 49

O(m\*n) which is Order of m \* n. As we need to check each and every edge element in edge list representation to find matches for each Vertex. Repeat this process for every vertex in the graph. m can be n\*2, which turns out to be O(n\*3)

Question 50

Space complexity of Edge List representation

Answer 50

O(m+n) - m space for edges & n space for vertices

Question 51

Adjacency List Representation

Answer 51

Instead of maintaining Edge list, Maintain list of all neighbor for given vertex and attach it to the vertex. So rather than searching all Edge list, we need to only search Vertex list in O(n) to find it's Adjacency nodes in O(1). which is O(n) Space requirements - O(n) to save vertex & O(m) to save all adjacency lists.

Question 52

Irrespective of graph representation variation. Is vertices representation same?

Answer 52

Yes. And it is always O(n) space to maintain list of vertices.

Question 53

Object and pointers approach

Answer 53

Hash table -\> Keys & Values. Value as Vertex object. Each object points to it's adjacency list

Question 54

Adjacency matrix

Answer 54

Represented by n\*n matrix

Question 55

Matrix property for Adjacency matrix for undirected graph without self loops

Answer 55

Symmetric matrix. and All elements over diagonal are 0

Question 56

Matrix property for Adjacency matrix for directed graph without self loops

Answer 56

Asymmetric matrix and All elements over diagonal are 0

Question 57

Time complexity for Finding neighbors in adjacency matrix representation

Answer 57

O(n)

Question 58

Space complexity of adjacency matrix representation

Answer 58

O(n\*n) - Irrespective of weather there are edges are not, as irrespective of that we need to mark all those 0's

Question 59

adjacency matrix representation is good for dense or sparse graphs?

Answer 59

Dense graphs, in which |E| approx. equal to |v\*2|

Question 60

What is good representation for sparse graphs

Answer 60

Adjacency List. Eg:., Facebook friends graph. There are over billions of members(vertices) in the graph, but only few hundred friends on average ( which is nothing but few hundred edges)

Question 61

Most of the real world graphs in general are Dense or Sparse?

Answer 61

Sparse, so Adjacency list representation is common.

Question 62

How do we represent weights in Adjacency matrix

Answer 62

We can add weights in matrix instead of 0 and 1's

Question 63

How do we represent weights in Adjacency List

Answer 63

Within adjacency list , instead of storing simple edge information in we can store adjacency node & weight

Question 64

Adjacency Map

Answer 64

Used dictionary/hash table to store neighbors instead of list as adjacency list.

Question 65

Space and time complexity of Adjacency map

Answer 65

It combines, time complexity of Adjacency matrix representation and Space complexity of Adjacency List

Question 66

Which graph representations can answer the query “Is vertex i directly connected to vertex j” in O(1) time?

Answer 66

Adjacency map & Adjacency matrix

Question 67

Which graph representations can answer the query “Get all neighbors of vertex i” in O(degree(i)) time?

Answer 67

Adjacency map & Adjacency List

Question 68

Which graph representations use O(m+n) space for a graph with n vertices and m edges?

Answer 68

Adjacency Map, Adjacency Lists, Edge Lists

Question 69

A graph has 10,000 vertices and 20,000 edges, and it is important to use as little space as possible to represent it. Would you use an adjacency matrix or an adjacency list?

Answer 69

m = 20,000 = 2n = O(n), so the graph is sparse. Adjacency lists are preferable for sparse graphs.

Question 70

A graph has 10,000 vertices and 20,000,000 edges, and it is important to use as little space as possible to represent it. Assume that edges have no auxiliary data. Would you use an adjacency matrix or an adjacency list?

Answer 70

m = 20,000,000 = 0.2 x 10^8 = 0.2(n^2) = O(n^2), so the graph is dense. Adjacency matrices are preferable for dense graphs. The presence or absence of an edge can be recorded using 1 bit. Adjacency lists will need several bytes to store each neighbor id and pointer to the next neighbor. So the constant of proportionality can be much smaller for an adjacency matrix.

Question 71

Which representation is easier for Graph study

Answer 71

Adjacency List

Question 72

Adjacency List graph representation implementation

Answer 72

Write Graph class code

Question 73

Adjacency List graph representation implementation with function to find if there is an Eulerian cycle in it

Answer 73

Write code

Question 74

Adjacency List graph representation implementation with function to find if there is an Eulerian path in it

Answer 74

Write Code

Question 75

Fringe Edges

Answer 75

Boundary between two sets is called fringe edge

Question 76

How do we find if both vertices are connected in graph

Answer 76

Try to capture Vertices from graph using fringe edge one by one. If both of them end up being in captured set, we can conclude they are connected.

Question 77

When we try to capture vertices from using fringe edges one by one, what would be the end data structure

Answer 77

Search Tree with the root as Source Vertex

Question 78

\*\*\*\*Pseudo code for general graph traversal algorithm

Answer 78

def search(s): captured[s] = 1 while there exist a fringe edge: pick one of them -\> (u,v) captured[v] = 1 parent[v] = u # This itself is not required for traversal

Question 79

What is different in different graph traversal algorithms

Answer 79

Policy by which to pull the fringe edge. Selection of this fringe edge is going to give us different graph algorithms.. Be it DFS, BFS, Dijkstra, A\*, etc., Selection of this fringe edge lead to different algorithms and different out put search trees.

Question 80

Different Graph Algorithms

Answer 80

Breadth First Search (BFS) Depth First Search (DFS) Dijkstra's Prim's Best First Search A\* \*First 3 are important for interviews

Question 81

BFS Graph traversal Fringe edge selection policy

Answer 81

Choose the fringe edge that was seen FIRST

Question 82

BFS Graph traversal resultant tree

Answer 82

BFS Tree

Question 83

DFS Graph traversal Fringe edge selection policy

Answer 83

Choose the fringe edge that was seen LAST(Most recent)

Question 84

DFS Graph traversal resultant tree

Answer 84

DFS Tree

Question 85

Dijkstra's Graph traversal Fringe edge selection policy

Answer 85

Choose the fringe edge whose RHS vertex has smallest numerical label

Question 86

Dijkstra's Graph traversal resultant tree

Answer 86

Shortest path tree

Question 87

Prim's Graph traversal Fringe edge selection policy

Answer 87

Choose the fringe edge whose RHS vertex has smallest numerical label

Question 88

Prim's Graph traversal resultant tree

Answer 88

Minimum Spanning Tree

Question 89

Best First Search Graph traversal Fringe edge selection policy

Answer 89

Choose the fringe edge whose RHS vertex has smallest numerical label

Question 90

Best first search Graph traversal resultant tree

Answer 90

Best first search tree

Question 91

A\* Graph traversal Fringe edge selection policy

Answer 91

Similar to Dijkstra's, Prim's and Best first search, that choose the fringe edge whose RHS vertex has smallest label, but there will be two labels as against one in above algorithms

Question 92

A\* Graph traversal resultant tree

Answer 92

A\* Tree

Question 93

Breadth First Search Graph

Answer 93

Explore graph in increasing order of distance from source S * First capture immediate neighbors of S (One hop away) * Then capture their neighbors (Two hops away) * Repeat the process