Trying to understand a c++ list

Question

Please pardon my noobishness but I am having trouble trying to understand the following:

class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // A dynamic array of adjacency lists
    void bridgeUtil(int v, bool visited[], int disc[], int low[], int parent[]);

  public:
    Graph(int V);   // Constructor
    void addEdge(int v, int w);   // function to add an edge to graph
    void bridge();    // prints all bridges
};

  Graph::Graph(int V)
  {
      this->V = V;
      adj = new list<int>[V];
  }

  void Graph::addEdge(int v, int w)
  {
     adj[v].push_back(w);
     adj[w].push_back(v);  // Note: the graph is undirected
  }

Can anybody explain how this data structure works and what would be the result when initialize it with:

  Graph g1(5);
  g1.addEdge(1, 0);
  g1.addEdge(0, 2);
  g1.addEdge(2, 1);
  g1.addEdge(0, 3);
  g1.addEdge(3, 4);

Thanks alot!

Answer 1

enter code here

// Program to print BFS traversal from a given 
// source vertex. BFS(int s) traverses vertices 
// reachable from s. 
#include<iostream> 
#include <list> 

using namespace std; class Graph 
    { 
        int V; // No. of vertices 
    
        // Pointer to an array containing adjacency 
        // lists 
        list<int> *adj; 
    public: 
        Graph(int V); // Constructor 
    
        // function to add an edge to graph 
        void addEdge(int v, int w); 
    
        // prints BFS traversal from a given source s 
        void BFS(int s); 
    }; 
    
    Graph::Graph(int V) 
    { 
        this->V = V; 
        adj = new list<int>[V]; 
    } 
    
    void Graph::addEdge(int v, int w) 
    { 
        adj[v].push_back(w); // Add w to v’s list. 
    } 
    
    void Graph::BFS(int s) 
    { 
        // Mark all the vertices as not visited 
        bool *visited = new bool[V]; 
        for(int i = 0; i < V; i++) 
            visited[i] = false; 
    
        // Create a queue for BFS 
        list<int> queue; 
    
        // Mark the current node as visited and enqueue it 
        visited[s] = true; 
        queue.push_back(s); 
    
        // 'i' will be used to get all adjacent 
        // vertices of a vertex 
        list<int>::iterator i; 
    
        while(!queue.empty()) 
        { 
            // Dequeue a vertex from queue and print it 
            s = queue.front(); 
            cout << s << " "; 
            queue.pop_front(); 
    
            // Get all adjacent vertices of the dequeued 
            // vertex s. If a adjacent has not been visited, 
            // then mark it visited and enqueue it 
            for (i = adj[s].begin(); i != adj[s].end(); ++i) 
            { 
                if (!visited[*i]) 
                { 
                    visited[*i] = true; 
                    queue.push_back(*i); 
                } 
            } 
        } 
    } 
    
    // Driver program to test methods of graph class 
    int main() 
    { 
        // Create a graph given in the above diagram 
        Graph g(5); 
        g.addEdge(1, 0); 
        g.addEdge(0, 2); 
        g.addEdge(2, 1); 
        g.addEdge(0, 3); 
        g.addEdge(3, 4);
        
    // g.addEdge(3, 3); 
    
        cout << "Following is Breadth First Traversal "
            << "(starting from vertex 2) \n"; 
        g.BFS(2); 
    
        return 0; 
    } 

Answer 2

The Underlying Data Structures

The std::list is a doubly linked list, which behaves similarly to the std::vector except the vector is basically a dynamic array management system.

The Graph

When you create the graph, you specify the total number of nodes the graph is going to have. Every node has its own list.

When you call the function add_edge it grabs the node (which is a list) at the index v. Then it adds the number w to that list signifying there is a link from node v to node w. The same happens again in the next statement except in reverse. It grabs the list at index w and adds the number v to the list signifying there is a link from node w to node v.

It is due to this nature we find the comment // Note: the graph is undirected, because it draws a path from both nodes to the other.

The Result

Since each node has its own list. We can choose one at random and find all of the nodes that are connected to it by using a function like the one below.

list<int> Graph::getNodes(int v)
{
   return(adj[v]);
}

What your code does

//Creates 5 lists, each one representing a node with possible id [0 - 4]
Graph g1(5);       
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);

//Results in 5 lists that look like this
/*
  (NODE) | (NODE) | (NODE) | (NODE) | (NODE)
  adj[0] | adj[1] | adj[2] | adj[3] | adj[4]
---------------------------------------------
    1    |    0   |    0   |    0   |   3
    2    |    2   |    1   |    4   |
    3    |        |        |        |
*/

Based on the lists, I can conclude that from Node 0, I can get to Nodes 1, 2 and 3

Answer 3

It keeps track of a graph, possible with an adjacency map or linked lists. After adding the 5 edges the graph would contain the following vertex: {0, 1, 2, 3, 4} and would have edges from {1-0, 0-2, 2-1, 0-3, 3-4} Are you looking for more detail?

Im not sure how it is actully stored but two posible ways are adjacency map or linked lists.

adjacency map:

\ 0 1 2 3 4 
0| 0 1 1 1 0 
1| 1 0 1 0 0 
2| 1 1 0 0 0
3| 1 0 0 0 1
4| 0 0 0 1 0 

a 0 means that the vertices are not connected and a 1 means they are.

linked lists:

0 > 1, 2, 3
1 > 0, 2
2 > 0, 1
3 > 0, 4
4 > 3

meaning that 0 goes to 1, 2 and 3 while 4 only goes to 3.

Answer 4

A graph is a set of nodes and edges between nodes. Here, each node is a number. The edges for each node are represented in lists (each entry in the list is the node at the other end of an edge). The adjacencies for node 0 are in list 0 in the adjacencies array. After adding an edge between two nodes, you'll, well...have an edge between those two nodes. It might help to draw it out. Your graph will look like this:

0--1
|\ |
| \|
3--2
|
4

Answer 5

Take a look at Wikipedia's article. In short, a graph is made up of nodes and vertices. Nodes are "places" or "things", while vertices are the connections between. Your code is representing this with a list of lists. List x has all the nodes that node x connects to.

Your example graph will look like this:

Answer 6

There are a fixed number of std::list's in each Graph instance. In your example there are 5 in the array. That number doesn't change.

Each entry in the array is a double-linked list of int's.

Adding an edge between X and Y changes two std::lists. The array index at X is the list of nodes for X, and gets T added to it. The array index at Y is the list of nodes for Y, and gets X added to it.

If you want a walkthrough... ask your teacher since it's obviously homework. :-)