Graph Representation
![graph](https://cdncontribute.geeksforgeeks.org/wp-content/uploads/undirectedgraph.png)
Meeting Agenda
- Settle down whether to use adjacency list or adjacency matrix
- Writing the constructor
- Implementing basic graph operations
- Finding a weighted shortest path
- Finding the smallest connecting threshold
Unfinished Business
Last meeting, we didn't settle down on whether we should use adjacency matrix or adjacency list to represent a graph. Today's first goal is to choose between these two.
-
adjacency matrix
- data structure: 2D array
-
adjacency list
- data structure: unordered map
Recap
Adjacency matrix storage: O (|V|^2)Adjacency list storage: O (|V| + |E|)
![adjacency list](https://media.geeksforgeeks.org/wp-content/uploads/20200205134219/Untitled-Diagram72.png)
👆Adjacency list representation
![adjacency matrix](http://www.btechsmartclass.com/data_structures/ds_images/Graph%20Adjacency%20Matrix%201.jpg)
👆Adjacency matrix representation
New Business
Besides finishing what we've left from the last meeting, we need to start
working on the constructor after we've decided which data structure to use.
Then, we need to finish the methods about the basic graph properties.
After this, we need to tackle down the two most complicated methods:
finding a weighted shortest path using BFS and the smallest connecting threshold.
This is going to be a lot of work. Thus, carpe diem!
System.out.println("I'm possible!");
Concerns or Comments
Killua: runtime complexity, space complexityKyoya:
Senku:
Thanks for attending the meeting!
Here is the firework show from Disney!
Don't be frightened by all of this work. Listen to this fight song at the bottom right to cheer you up!
The meeting ends now! Have a good day!