backtracking, graph DSA

Question 1

Backtracking

Answer 1

general algorithmic technique that considers searching every possible combination in order to solve a computational problem.

Question 2

Properties of backtracking

Answer 2

Incremental construction: Backtracking builds a solution incrementally by constructing a partial solution and expanding it until a complete solution is found or it becomes clear that no solution exists.

Reversibility: Backtracking is reversible, as it can backtrack to a previous state and try a different path when it reaches a dead end.

Optimal solution: Backtracking can guarantee an optimal solution if the problem has a well-defined goal and optimal solution, as it explores the entire search space.

Simplicity: Backtracking is a simple approach for solving problems, as it avoids the need for complex data structures or algorithms and can be easily implemented using a simple recursive approach.

Question 3

Advantages of backtracking

Answer 3

Flexibility: Backtracking can be used to solve a wide range of problems, from simple puzzles like the N-Queens problem to complex combinatorial optimization problems. It can be adapted to various constraints and problem-specific requirements.

Pruning: Backtracking can be optimized through pruning, which involves avoiding certain branches of the search tree that are not likely to lead to a solution. This can greatly reduce the search space and speed up the solution time.

Concurrent execution: Backtracking algorithms can be parallelized and executed in multiple threads, as each recursive call can be executed independently. This can greatly speed up the solution time

Question 4

Disadvantages of backtracking

Answer 4

Time complexity: Backtracking can be very slow for large problems, as it explores a large search space that may contain many dead ends. This can result in a high time complexity, especially if the problem has a large number of constraints and a complex search space.

Space complexity: Backtracking can also be memory-intensive, as it requires storing the state of the partial solution at each step of the search. This can result in a high space complexity, especially for problems with a large number of variables and constraints.

Inefficiency: Backtracking can be inefficient, as it may explore the same parts of the search space multiple times. This can result in a large number of redundant calculations, which can significantly slow down the solution time.

Limited applicability: Backtracking is not suitable for problems with real-time constraints, as it may take a long time to find a solution. Additionally, it may not be appropriate for problems with continuous variables, as it can only handle discrete variables and constraints.
Application of Backtracking:

Question 5

Five different field where backtracking can be used

Answer 5

Computer Science: Backtracking is commonly used in computer science to solve a wide range of problems, including search algorithms, constraint satisfaction problems, and combinatorial optimization problems.

Mathematics: Backtracking can be used in mathematics to solve a variety of problems, including those related to graph theory, number theory, and combinatorics.

Artificial Intelligence: Backtracking is a key technique used in artificial intelligence to solve problems related to planning, decision-making, and optimization. Examples include pathfinding, route planning, and constraint satisfaction problems in robotics and other AI applications.

Natural Language Processing: Backtracking can be used in natural language processing to solve problems related to parsing and semantic analysis.

Question 6

Component of a graph:
Vertices

Answer 6

Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertices or nodes. Every node/vertex can be labeled or unlabelled.

Question 7

Component of a graph:
Edges

Answer 7

Edges are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labeled/unlabelled.

Question 8

Graph

Answer 8

a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by G(E, V).

Question 9

Component of a graph:
Edges

Answer 9

Edges are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labeled/unlabelled.

Question 10

Null graph

Answer 10

A graph is known as a null graph if there are no edges in the graph.

Question 11

Trivial graph

Answer 11

Graph having only a single vertex, it is also the smallest graph possible.

Question 12

Undirected graph

Answer 12

A graph in which edges do not have any direction. That is the nodes are unordered pairs in the definition of every edge.

Question 13

Directed graph

Answer 13

A graph in which edge has direction. That is the nodes are ordered pairs in the definition of every edge.

Question 14

disconnected graph

Answer 14

The graph in which at least one node is not reachable from a node is known as a disconnected graph.

Question 14

Connected graph

Answer 14

The graph in which from one node we can visit any other node in the graph is known as a connected graph.

Question 15

complete graph

Answer 15

The graph in which from each node there is an edge to each other node.

Question 16

Cycle graph

Answer 16

The graph in which the graph is a cycle in itself, the degree of each vertex is 2.

Question 17

Directed Acyclic graph

Answer 17

A Directed Graph that does not contain any cycle.

Question 17

Cycle graph

Answer 17

The graph in which the graph is a cycle in itself, the degree of each vertex is 2.

Question 17

Cyclic graph

Answer 17

A graph containing at least one cycle is known as a Cyclic graph.

Question 17

Trivial graph

Answer 17

Graph having only a single vertex, it is also the smallest graph possible.

Question 18

Bipartite graph

Answer 18

A graph in which vertex can be divided into two sets such that vertex in each set does not contain any edge between them.

Question 19

Weighted graph

Answer 19

A graph in which the edges are already specified with suitable weight is known as a weighted graph. Weighted graphs can be further classified as:
directed weighted graphs and
undirected weighted graphs.

Question 20

Graph is a data structure that consists of the following two components:

Answer 20

A finite set of vertices also called nodes.

A finite set of ordered pair of the form (u, v) called edge. The pair is ordered because (u, v) is not the same as (v, u) in the case of a directed graph(di-graph). The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.

Question 21

Graphs are used to represent many real-life applications: Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex(or node). Each node is a structure and contains information like person id, name, gender, and locale.

Answer 21

In computer science, a graph is a data structure that is used to represent connections or relationships between objects. A graph consists of a set of vertices (also known as nodes) and a set of edges (also known as arcs) that connect the vertices. The vertices can represent anything from cities in a map to web pages in a network, and the edges can represent the relationships between them, such as roads or links.

A graph can be visualized as a collection of points (vertices) connected by lines (edges), where each vertex represents a point of interest and each edge represents a connection between two points. The edges can be directed or undirected, meaning they can either have a specific direction or be bidirectional. For example, a map of a city may have directed edges that represent the direction of one-way streets, while a social network may have undirected edges that represent friendships between individuals.

Question 22

Adjacency List:
An adjacency list is a simple way to represent a graph as a list of vertices, where each vertex has a list of its adjacent vertices. Here’s an example of an adjacency list for an undirected graph with 4 vertices:

Answer 22

makefile
Copy code
0: 1 3
1: 0 2
2: 1 3
3: 0 2
In this example, vertex 0 is adjacent to vertices 1 and 3, vertex 1 is adjacent to vertices 0 and 2, and so on.

Question 23

Adjacency Matrix:
An adjacency matrix is a two-dimensional array that represents the graph by storing a 1 at position (i,j) if there is an edge from vertex i to vertex j, and 0 otherwise. Here’s an example of an adjacency matrix for the same undirected graph:

Answer 23

Copy code
0 1 2 3
0 0 1 0 1
1 1 0 1 0
2 0 1 0 1
3 1 0 1 0
In this example, there is an edge from vertex 0 to vertex 1 (represented by a 1 in position (0,1)), an edge from vertex 1 to vertex 0 (represented by a 1 in position (1,0)), and so on.

Question 24

Incidence Matrix:
An incidence matrix is a two-dimensional array that represents the graph by storing a 1 at position (i,j) if vertex i is incident on edge j, and 0 otherwise. Here’s an example of an incidence matrix for the same undirected graph:

Answer 24

Copy code
0 1 2 3
0 0 1 0 1
1 1 0 1 0
2 0 1 0 1
3 1 0 1 0
In this example, vertex 0 is incident on edges 1, and 3 (represented by a 1 in positions (0,1), and (0,3)), vertex 1 is incident on edges 0, 2 (represented by a 1 in positions (1,0) and (1,2)), and so on.

Question 25

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. The adjacency matrix for an undirected graph is always symmetric.

Answer 25

Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

Question 26

Advantages of adjacency matrix

Answer 26

Representation is easier to implement and follow.

Removing an edge takes O(1) time.

Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done O(1).

Question 27

Disadvantages of adjacency matrix

Answer 27

Consumes more space O(V2). Even if the graph is sparse(contains less number of edges), it consumes the same space.

Adding a vertex takes O(V2) time. Computing all neighbors of a vertex takes O(V) time (Not efficient).

Question 28

Adjacency list

Answer 28

An array of linked lists is used. The size of the array is equal to the number of vertices. Let the array be an array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex.

This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs.

Question 29

Advantages of adjacency list

Answer 29

Saves space. Space taken is O(|V|+|E|). In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V2) space.

Adding a vertex is easier.

Computing all neighbors of a vertex takes optimal time.

Question 30

Disadvantages of adjacency list

Answer 30

Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V).

Question 31

implementations of adjacency list

Answer 31

Note that in the below implementation, we use dynamic arrays (vector in C++/ArrayList in Java) to represent adjacency lists instead of the linked list. The vector implementation has the advantage of cache friendliness.

Question 32

edge

Answer 32

one of the two primary units used to form graphs. Each edge has two ends, which are vertices to which it is attached.

.If two vertices are endpoints of the same edge, they are adjacent. A vertex’s outgoing edges are directed edges that point to the origin.

.A vertex’s incoming edges are directed edges that point to the vertex’s destination.

.The total number of edges occurring to a vertex in a graph is its degree.

.A vertex with an in-degree of zero is referred to as a source vertex, while one with an out-degree of zero is known as sink vertex.

Question 33

path

Answer 33

set of alternating vertices and edges, with each vertex connected by an edge.

.The path that starts and finishes at the same vertex is known as a cycle.

.A path with unique vertices is called a simple path.

Question 34

A spanning subgraph that is also a tree is known as a ___ ____

Answer 34

spanning tree

Question 35

connected component

Answer 35

the unconnected graph’s most connected subgrap

Question 36

bridge

Answer 36

an edge of removal, would sever the graph.

Question 37

forest

Answer 37

graph without a cycle.

Question 38

set representation

Answer 38

Set representation of a graph involves two sets: Set of vertices V = {V1, V2, V3, V4} and set of edges E = {{V1, V2}, {V2, V3}, {V3, V4}, {V4, V1}}. This representation is efficient for memory but does not allow parallel edges.

Question 39

sequential representation

Answer 39

This representation of a graph can be represented by means of matrices: Adjacency Matrix, Incidence matrix and Path matrix.

Adjacency Matrix: This matrix includes information about the adjacent nodes. Here, aij = 1 if there is an edge from Vi to Vj otherwise 0. It is a matrix of order V×V.
I
ncidence Matrix: This matrix includes information about the incidence of edges on the nodes. Here, aij = 1 if the jth edge Ej is incident on ith vertex Vi otherwise 0. It is a matrix of order V×E.

Path Matrix: This matrix includes information about the simple path between two vertices. Here, Pij = 1 if there is a path from Vi to Vj otherwise 0. It is also called as reachability matrix of graph G.

Question 40

Linked representation

Answer 40

This representation gives the information about the nodes to which a specific node is connected i.e. adjacency lists. This representation gives the adjacency lists of the vertices with the help of array and linked lists. In the adjacency lists, the vertices which are connected with the specific vertex are arranged in the form of lists which is connected to that vertex.

Question 41

application of Graph

Answer 41

Social media analysis: Social media platforms generate vast amounts of data in real-time, which can be analyzed using graphs to identify trends, sentiment, and key influencers. This can be useful for marketing, customer service, and reputation management.

Network monitoring: Graphs can be used to monitor network traffic in real-time, allowing network administrators to identify potential bottlenecks, security threats, and other issues. This is critical for ensuring the smooth operation of complex networks.

Financial trading: Graphs can be used to analyze real-time financial data, such as stock prices and market trends, to identify patterns and make trading decisions. This is particularly important for high-frequency trading, where even small delays can have a significant impact on profits.

Internet of Things (IoT) management: IoT devices generate vast amounts of data in real-time, which can be analyzed using graphs to identify patterns, optimize performance, and detect anomalies. This is important for managing large-scale IoT deployments.

Autonomous vehicles: Graphs can be used to model the real-time environment around autonomous vehicles, allowing them to navigate safely and efficiently. This requires real-time data from sensors and other sources, which can be processed using graph algorithms.

Disease surveillance: Graphs can be used to model the spread of infectious diseases in real-time, allowing health officials to identify outbreaks and implement effective containment strategies. This is particularly important during pandemics or other public health emergencies.
The best example of graphs in the real world is Facebook. Each person on Facebook is a node and is connected through edges. Thus, A is a friend of B. B is a friend of C, and so on.

Question 42

Advantages of graph

Answer 42

Representing complex data: Graphs are effective tools for representing complex data, especially when the relationships between the data points are not straightforward. They can help to uncover patterns, trends, and insights that may be difficult to see using other methods.

Efficient data processing: Graphs can be processed efficiently using graph algorithms, which are specifically designed to work with graph data structures. This makes it possible to perform complex operations on large datasets quickly and effectively.

Network analysis: Graphs are commonly used in network analysis to study relationships between individuals or organizations, as well as to identify important nodes and edges in a network. This is useful in a variety of fields, including social sciences, business, and marketing.
Pathfinding: Graphs can be used to find the shortest path between two points, which is a common problem in computer science, logistics, and transportation planning.

Visualization: Graphs are highly visual, making it easy to communicate complex data and relationships in a clear and concise way. This makes them useful for presentations, reports, and data analysis.

Machine learning: Graphs can be used in machine learning to model complex relationships between variables, such as in recommendation systems or fraud detection.

Graphs are used in computer science to depict the flow of computation.

Users on Facebook are referred to as vertices, and if they are friends, there is an edge connecting them. The Friend Suggestion system on Facebook is based on graph theory.

You come across the Resources Allocation Graph in the Operating System, where each process and resource are regarded vertically. Edges are drawn from resources to assigned functions or from the requesting process to the desired resources. A stalemate will develop if this results in the establishment of a cycle.

Web pages are referred to as vertices on the World Wide Web. Suppose there is a link from page A to page B that can represent an edge. this application is an illustration of a directed graph.

Graph transformation systems manipulate graphs in memory using rules, Graph databases store and query graph-structured data in a transaction-safe, perment manner.

Question 43

Breadth First Search (BFS) algorithm

Answer 43

used to search a graph data structure for a node that meets a set of criteria. It starts at the root of the graph and visits all nodes at the current depth level before moving on to the nodes at the next depth level.

Question 44

Depth-first search (DFS)

Answer 44

an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking

Question 45

Dijkstra’s algorithm

Answer 45

algorithms for solving many single-source shortest path problems having non-negative edge weight in the graphs i.e., it is to find the shortest distance between two vertices on a graph. It was conceived by Dutch computer scientist Edsger W. Dijkstra in 1956.

The algorithm maintains a set of visited vertices and a set of unvisited vertices. It starts at the source vertex and iteratively selects the unvisited vertex with the smallest tentative distance from the source. It then visits the neighbors of this vertex and updates their tentative distances if a shorter path is found. This process continues until the destination vertex is reached, or all reachable vertices have been visited.

Question 46

Basic steps of Dijkstra’s algorithm

Answer 46

Dijkstra’s algorithm starts at the node source node we choose and then it analyzes the graph condition and its paths to find the optimal shortest distance between the given node and all other nodes in the graph.
Dijkstra’s algorithm keeps track of the currently known shortest distance from each node to the source node and updates the value after it finds the optimal path once the algorithm finds the shortest path between the source node and destination node then the specific node is marked as visited.

Question 47

Basic requirements for implementing Dijkstra’s algorithm

Answer 47

Graph: Dijkstra’s Algorithm can be implemented on any graph but it works best with a weighted Directed Graph with non-negative edge weights and the graph should be represented as a set of vertices and edges.

Source Vertex: Dijkstra’s Algorithm requires a source node which is starting point for the search.

Destination vertex: Dijkstra’s algorithm may be modified to terminate the search once a specific destination vertex is reached.

Non-Negative Edges: Dijkstra’s algorithm works only on graphs that have positive weights this is because during the process the weights of the edge have to be added to find the shortest path. If there is a negative weight in the graph then the algorithm will not work correctly. Once a node has been marked as visited the current path to that node is marked as the shortest path to reach that node.

Question 48

Can Dijkstra’s algorithm work on both Directed and Undirected graphs?

Answer 48

Yes, Dijkstra’s algorithm can work on both directed graphs and undirected graphs as this algorithm is designed to work on any type of graph as long as it meets the requirements of having non-negative edge weights and being connected.

In a directed graph, each edge has a direction, indicating the direction of travel between the vertices connected by the edge. In this case, the algorithm follows the direction of the edges when searching for the shortest path.

In an undirected graph, the edges have no direction, and the algorithm can traverse both forward and backward along the edges when searching for the shortest path.

Question 49

Algorithm for Dijktra’s algorithm

Answer 49

Mark the source node with a current distance of 0 and the rest with infinity.

Set the non-visited node with the smallest current distance as the current node.

For each neighbor, N of the current node adds the current distance of the adjacent node with the weight of the edge connecting 0->1. If it is smaller than the current distance of Node, set it as the new current distance of N.

Mark the current node 1 as visited.

Go to step 2 if there are any nodes are unvisited.

Question 50

Kruskal’s algorithm

Answer 50

sort all edges of the given graph in increasing order. Then it keeps on adding new edges and nodes in the MST if the newly added edge does not form a cycle. It picks the minimum weighted edge at first at the maximum weighted edge at last. Thus we can say that it makes a locally optimal choice in each step in order to find the optimal solution. Hence this is a Greedy Algorithm.

Question 51

How to find MST using Kruskal’s algorithm?

Answer 51

Sort all the edges in non-decreasing order of their weight.

Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If the cycle is not formed, include this edge. Else, discard it.

Repeat step#2 until there are (V-1) edges in the spanning tree.

Question 52

Prim’s algorithms for minimum spanning tree (MST)

Answer 52

Prim’s algorithm is also a Greedy algorithm. This algorithm always starts with a single node and moves through several adjacent nodes, in order to explore all of the connected edges along the way.

The algorithm starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, and the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST.

A group of edges that connects two sets of vertices in a graph is called cut in graph theory. So, at every step of Prim’s algorithm, find a cut, pick the minimum weight edge from the cut, and include this vertex in MST Set (the set that contains already included vertices).

Question 53

Advantages of Prim’s algorithm

Answer 53

Prim’s algorithm is guaranteed to find the MST in a connected, weighted graph.

It has a time complexity of O(E log V) using a binary heap or Fibonacci heap, where E is the number of edges and V is the number of vertices.

It is a relatively simple algorithm to understand and implement compared to some other MST algorithms.

Question 54

Disadvantages of Prim’s algorithm

Answer 54

Like Kruskal’s algorithm, Prim’s algorithm can be slow on dense graphs with many edges, as it requires iterating over all edges at least once.

Prim’s algorithm relies on a priority queue, which can take up extra memory and slow down the algorithm on very large graphs.

The choice of starting node can affect the MST output, which may not be desirable in some applications.

Question 55

Topological sorting for Directed Acyclical Graph (DAG)

Answer 55

linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering.

Question 56

Applications of Topological Sorting

Answer 56

Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs.

In computer science, applications of this type arise in:

Instruction scheduling

Ordering of formula cell evaluation when recomputing formula values in spreadsheets

Logic synthesis

Determining the order of compilation tasks to perform in make files

Data serialization

Resolving symbol dependencies in linkers