Skip to content
Programming Fundamentals and Data Structures

Graphs

Graphs as a Data Structure

Section titled “Graphs as a Data Structure”

Use linked-list concepts to implement graphs. A graph is a collection of nodes in which each node can have several neighboring nodes.

An example graph is provided here.

  1. Define the structure of a graph node. It should have an int field for the node’s value and a dynamic buffer for its neighboring nodes. You can use code from static_buffer or dynamic_array.

    You can use std::vector, but then make sure you understand RAII.

  2. Implement one of the following graph configurations:

1
2
3
4
1
2
3
4

  1. In directed graphs, node A can be a neighbor of node B, while node B is not necessarily a neighbor of node A. In undirected graphs, nodes A and B are always neighbors of each other. Explain how this idea is reflected in the graph’s memory layout.

  2. Write a function that calculates the sum of the values of a given node’s neighbors.

  3. Implement the DFS and BFS traversal algorithms. You can add additional information to the nodes themselves.