Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

algorithms > graphs > Flashcards

graphs Flashcards

1
Q

Draw Eulerian Cycle, if Exists 1

A

Figure at 8:15

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

directed graph

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are entry and exit vertices in Eulerian Path graph

A

Start and end at two different vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

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

Sample picture attached

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Degree of Vertx

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Connected Component

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

We call that graph has Eulerian Cycle in it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How to draw Eulerian Cycle within given graph?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Draw Eulerian Cycle, if Exists

A

picture at 1:11/Eulerian Cycle Construction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Eulerian Cycle also known as

A

Eulerian circuit
Eulerian Tour
Euler Circuit
Euler Tour

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Path Length

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Cycle

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Eulerian Path

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Path

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

No. It’s impossible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

A

Yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Eulerian Cycle

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Connectivity

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Negative Weight Cycle

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Draw Eulerian Cycle, if Exists 3

A

Figure at 8:15

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Types of graphs

A

Undirected
Directed
Unweighted
Weighted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

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

A

Yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Undirected Graph

A

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

Paste sample pic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Connected Graph

A

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

Sample picture

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Graph

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Draw Eulerian Cycle

A

Sample pic attached from 3:25

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Weighted Graph

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Out degree

A

“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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Vertex

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Draw Eulerian Cycle, if Exists 2

A

Figure at 8:15

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

In degree

A

“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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Edge

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Is Eulerian Cycle is an Eulerian Path?

A

Yes

39
Q

Is Eulerian Path is an Eulerian Cycle?

A

No

40
Q

Few popular ways to represent graphs

A

Edge Lists
Adjacency Lists
Adjacency Matrices
Adjacency Maps

41
Q 
Notation to represent number of Vertices in the graph 
#vertices
A

n or |v|

42
Q 
Notation to represent number of Edges in the graph 
#edges
A

m or |E|

43
Q

Simple graph representation among all, but not very efficient

A

Edge Lists

44
Q

Edge List representation

A

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

45
Q

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

A

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

46
Q

What exactly is “n choose 2” in probability.

A

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

47
Q

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

A

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)

48
Q

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

A

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.

49
Q

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

A

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)

50
Q

Space complexity of Edge List representation

A

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

51
Q

Adjacency List Representation

A

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.

52
Q

Irrespective of graph representation variation. Is vertices representation same?

A

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

53
Q

Object and pointers approach

A

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

54
Q

Adjacency matrix

A

Represented by n*n matrix

55
Q

Matrix property for Adjacency matrix for undirected graph without self loops

A

Symmetric matrix. and All elements over diagonal are 0

56
Q

Matrix property for Adjacency matrix for directed graph without self loops

A

Asymmetric matrix and All elements over diagonal are 0

57
Q

Time complexity for Finding neighbors in adjacency matrix representation

A

O(n)

58
Q

Space complexity of adjacency matrix representation

A

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

59
Q

adjacency matrix representation is good for dense or sparse graphs?

A

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

60
Q

What is good representation for sparse graphs

A

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)

61
Q

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

A

Sparse, so Adjacency list representation is common.

62
Q

How do we represent weights in Adjacency matrix

A

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

63
Q

How do we represent weights in Adjacency List

A

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

64
Q

Adjacency Map

A

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

65
Q

Space and time complexity of Adjacency map

A

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

66
Q

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

A

Adjacency map & Adjacency matrix

67
Q

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

A

Adjacency map & Adjacency List

68
Q

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

A

Adjacency Map, Adjacency Lists, Edge Lists

69
Q

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?

A

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

70
Q

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?

A

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.

71
Q

Which representation is easier for Graph study

A

Adjacency List

72
Q

Adjacency List graph representation implementation

A

Write Graph class code

73
Q

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

A

Write code

74
Q

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

A

Write Code

75
Q

Fringe Edges

A

Boundary between two sets is called fringe edge

76
Q

How do we find if both vertices are connected in graph

A

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.

77
Q

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

A

Search Tree with the root as Source Vertex

78
Q

****Pseudo code for general graph traversal algorithm

A

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

79
Q

What is different in different graph traversal algorithms

A

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.

80
Q

Different Graph Algorithms

A

Breadth First Search (BFS)
Depth First Search (DFS)
Dijkstra’s
Prim’s
Best First Search
A*

*First 3 are important for interviews

81
Q

BFS Graph traversal Fringe edge selection policy

A

Choose the fringe edge that was seen FIRST

82
Q

BFS Graph traversal resultant tree

A

BFS Tree

83
Q

DFS Graph traversal Fringe edge selection policy

A

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

84
Q

DFS Graph traversal resultant tree

A

DFS Tree

85
Q

Dijkstra’s Graph traversal Fringe edge selection policy

A

Choose the fringe edge whose RHS vertex has smallest numerical label

86
Q

Dijkstra’s Graph traversal resultant tree

A

Shortest path tree

87
Q

Prim’s Graph traversal Fringe edge selection policy

A

Choose the fringe edge whose RHS vertex has smallest numerical label

88
Q

Prim’s Graph traversal resultant tree

A

Minimum Spanning Tree

89
Q

Best First Search Graph traversal Fringe edge selection policy

A

Choose the fringe edge whose RHS vertex has smallest numerical label

90
Q

Best first search Graph traversal resultant tree

A

Best first search tree

91
Q

A* Graph traversal Fringe edge selection policy

A

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

92
Q

A* Graph traversal resultant tree

A

A* Tree

93
Q

Breadth First Search Graph

A

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
94
Q
A

algorithms (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions