Undirected Graph

Preview

1. What is an undirected graph and how it differs from a directed graph?
2. What is a spanning tree in an undirected graph and how it can be computed?
3. How do you detect if an undirected graph has a cycle, and how to remove cycles from the graph?
4. What are some common algorithms used for traversing an undirected graph, such as DFS and BFS?
5. How can you find the shortest path between two vertices in an undirected graph?

Explain

An undirected graph is a graph where edges do not have direction or arrows. In other words, the connection between two vertices is bi-directional. If vertex A is connected to vertex B, it means vertex B can also reach vertex A without any restrictions.

An example of an undirected graph is a social network. The individuals in the network can be represented as vertices, and each connection or friendship between two individuals can be represented as an undirected edge. The graph can also have edges representing groups, clubs or organizations that these individuals belong to. This type of graph is useful in understanding how people are connected and can help identify groups or sub-communities within a network.

Keypoint

• An undirected graph is a collection of vertices (or nodes) and edges, where each edge connects a pair of vertices.
• In an undirected graph, the edges are bidirectional, meaning that if there is an edge between vertex A and vertex B, there is also an edge between vertex B and vertex A.
• The degree of a vertex in an undirected graph is the number of edges incident to that vertex.
• A path in an undirected graph is a sequence of vertices where each pair of adjacent vertices is connected by an edge.
• A cycle in an undirected graph is a path that starts and ends at the same vertex, without repeating any other vertices or edges.
• An undirected graph can be connected or disconnected, depending on whether there is a path between every pair of vertices in the graph or not.
• A connected component in an undirected graph is a maximal set of vertices that are connected to each other by paths.
• The complement of an undirected graph is a graph with the same set of vertices, but with all the edges that are not present in the original graph.
• Many graph algorithms, such as depth-first search and breadth-first search, are commonly used on undirected graphs.

Review

1. What is the difference between an undirected graph and a directed graph?
   Answer: An undirected graph is a graph in which the edges do not have a direction, while a directed graph has edges with a specific direction.

2. What is the degree of a vertex in an undirected graph?
   Answer: The degree of a vertex in an undirected graph is the number of edges that connect to that vertex.

3. How do you find the shortest path between two vertices in an undirected graph?
   Answer: One common algorithm for finding the shortest path in an undirected graph is Dijkstra’s algorithm.

4. What is a connected component in an undirected graph?
   Answer: A connected component in an undirected graph is a subgraph in which every pair of vertices is connected by a path.

5. What is a cycle in an undirected graph?
   Answer: A cycle in an undirected graph is a sequence of vertices and edges that starts and ends at the same vertex, and in which there are no repeated edges.