An unweighted graph is a type of graph where each edge does not have any weight or value assigned to it. In other words, each edge is considered to have a uniform weight of 1. Unweighted graph data structure are commonly used in various applications, including social network analysis, game AI, and modeling relationships between objects or entities.

Creating an Unweighted Graph in Python

In Python, we can represent an unweighted graph using a dictionary and a list. The keys of the dictionary represent the vertices of the graph, and the values are lists of adjacent vertices. Here is an example of an unweighted graph represented as a dictionary:

pythonCopy codegraph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

In this example, the vertices of the graph are ‘A’, ‘B’, ‘C’, and ‘D’, and each vertex is associated with a list of adjacent vertices.

Traversing an Unweighted Graph

To traverse an unweighted graph, we can use various algorithms, such as Breadth-First Search (BFS) and Depth-First Search (DFS). Here is an example of a BFS implementation for an unweighted graph in Python:

pythonCopy codedef bfs(graph, start_vertex):
    visited = set()
    queue = [start_vertex]
    
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            neighbors = graph[vertex]
            for neighbor in neighbors:
                queue.append(neighbor)
    
    return visited

In this implementation, the bfs function takes an unweighted graph and a start vertex as input and returns a set of visited vertices in BFS order.

To use this function with the example graph we created earlier, we can do the following:

pythonCopy codevisited = bfs(graph, 'A')
print(visited)

This will output the following set of visited vertices in BFS order starting from vertex ‘A’:

arduinoCopy code{'A', 'B', 'C', 'D'}

Conclusion

In conclusion, an unweighted graph is a type of graph where each edge does not have any weight or value assigned to it. We can represent an unweighted graph using a dictionary and a list in Python. We can traverse an unweighted graph using various algorithms, such as BFS and DFS.

FAQs

1. What is the difference between a weighted graph and an unweighted graph?

• A weighted graph is a type of graph where each edge has a weight or value assigned to it, while an unweighted graph does not have any weights or values assigned to its edges.

2. What is BFS used for?

• BFS is a commonly used algorithm for traversing a graph in a breadth-first order and finding the shortest path between two vertices in an unweighted graph.

3. What is the time complexity of BFS?

• The time complexity of BFS is O(V + E), where V is the number of vertices in the graph and E is the number of edges.

4. Can an unweighted graph be cyclic?

• Yes, an unweighted graph can be cyclic, which means that there can be a path that starts and ends at the same vertex while traversing through one or more edges.

5. What are some real-world examples of unweighted graphs?

• Some real-world examples of unweighted graphs include social networks (where each relationship is represented by an unweighted edge) and website link structures (where each hyperlink between web pages is represented by an unweighted edge).