You are given a graph containing n vertices and m edges and given that the graph doesn’t contain cycle of odd length. Time Complexity of the best known algorithm to find out whether the graph is bipartite or not is ?a)O(m+n)b)O(1)c)O(mn)d)O(n2)Correct answer is option 'B'. Can you explain this answer?

Question

You are given a graph containing n vertices and m edges and given that the graph doesn&rsquo;t contain cycle of odd length. Time Complexity of the best known algorithm to find out whether the graph is bipartite or not is ?a)O(m+n)b)O(1)c)O(mn)d)O(n2)Correct answer is option 'B'. Can you explain this answer?

Answer

Is connected. You are also given a starting vertex s. Implement a function to perform a depth-first search (DFS) on the graph starting from the given vertex.

Here's the Python code to perform DFS on a given graph:

```python
def dfs(graph, start):
visited = set() # Set to keep track of visited vertices
stack = [start] # Stack to store the vertices to be visited

while stack:
vertex = stack.pop() # Pop the top vertex from the stack

if vertex not in visited:
visited.add(vertex) # Mark the vertex as visited

for neighbor in graph[vertex]:
stack.append(neighbor) # Add the neighbors of the current vertex to the stack

return visited
```

In this code, the `graph` is represented as a dictionary where the keys are the vertices and the values are lists of neighbors. The `start` parameter specifies the starting vertex for the DFS.

The algorithm starts by initializing an empty set `visited` to keep track of the visited vertices and a stack `stack` to store the vertices to be visited. The starting vertex is added to the stack.

The algorithm then enters a loop that continues until the stack is empty. In each iteration, it pops the top vertex from the stack. If the vertex has not been visited before, it is added to the `visited` set. Then, for each neighbor of the current vertex, it is added to the stack.

Finally, the algorithm returns the set of visited vertices.

To use this function, you can call it with your graph and the starting vertex as arguments:

```python
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D', 'E'],
'D': ['B', 'C', 'E'],
'E': ['C', 'D']
}

start_vertex = 'A'

result = dfs(graph, start_vertex)
print(result)
```

This will output the set of visited vertices during the DFS traversal.

Answer

It is by definition that a graph is bipartite iff it does not contain odd length cycles.
So the answer is O(1).

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company