{"lesson":{"id":63,"title":"Implementing Graphs: Edge List, Adjacency List, Adjacency Matrix","slug":"implementing-graphs-edge-list-adjacency-list-adjacency-matrix","created_at":"2020-06-28T18:45:49.965Z","updated_at":"2023-08-18T00:50:45.236Z","image_url":"https://storage.googleapis.com/algodailyrandomassets/tutorials-optimized/implementing-graphs-adjacencylist.png","section_id":10,"sequence":2,"locked":false,"video":"https://player.vimeo.com/video/495589285","reading_time":"57","published":true,"newsletter_sequence":32,"video_thumbnail":"https://i.vimeocdn.com/filter/overlay?src0=https%3A%2F%2Fi.vimeocdn.com%2Fvideo%2F1025239794-b3d5fc9c0a97dfecfb11dbdb6804b399794ed91caf69267e4d4c41a987b73297-d_640x360\u0026src1=http%3A%2F%2Ff.vimeocdn.com%2Fp%2Fimages%2Fcrawler_play.png","video_duration":891,"excerpt":"\n\nFor many students, the `graph` data structure can be intimidating and difficult to learn. In fact, some of their properties can be baffling to even experienced developers and computer science graduates who haven't worked with them for a while. \n\nBut graphs are interesting and integral, as they are a vital way of modeling and displaying information"},"completed":null,"screens":[{"id":1385,"kind":"info screen","options":[],"content":"For many students, the `graph` data structure can be intimidating and difficult to learn. In fact, some of their properties can be baffling to even experienced developers and computer science graduates who haven't worked with them for a while. \n\nBut graphs are interesting and integral, as they are a vital way of modeling and displaying information in the world around us. We can use graphs to do incredible things with computers. As an example, social networks are simply huge graphs at their core. Companies like [LinkedIn](/companies/linkedin) and [Google](/companies/google) utilize many **graph algorithms** understand complex networks and relationships. \n\nBefore we dive into more theory, let us provide some motivation for learning graphs.\n\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/curriculum/graphs/implementing-graphs-adjacencylist.png\" class=\"img-fluid\" /\u003e","code":"0","full_screen":true,"solution":"0","lesson_id":63,"challenge_id":null,"sequence":1,"title":"Why Graphs Again?","slug":"introduction","created_at":"2020-06-28T18:48:02.297Z","updated_at":"2023-08-18T01:00:43.857Z","explanation":null,"summary":"The `graph` data structure, though often intimidating to students, is a crucial tool for modeling information, allowing for complex abilities like social networking, and is used by companies like **LinkedIn and Google** to understand networks and relationships through various **graph algorithms**."},{"id":1386,"kind":"info screen","options":[],"content":"## What are graphs and what can we do with them?\n\n_Much of this is review from [`The Simple Reference To Graphs`](/lessons/simple-reference-to-graphs). If you already have the basics down, feel free to skip to the implementation parts later in the guide._\n\nIn purely layman's terms, a `graph` is a group of dots connected by lines. You've seen them plenty of times. Programmatically, these \"dots\" represent _things_, and these lines are to demonstrate _connections between things_. We can use graphs to model relationships in the world. \n\nFor example:\n\n1. Facebook friend networks are a graph where each person is a \"dot\" or a `node`, and the friendships and connections between people are lines.\n\n2. Google Maps uses a series of nodes and lines to model the road network and give you directions to your final destination.\n\n3. The Internet is a really a giant graph where web pages are dots and the links between pages are lines.\n\nWe can meaningful model groups of relationships, find relations between people, find the shortest path between two points, model objects in space, and document structures all using this concept of **nodes** connected by **edges**.\n\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/curriculum/graphs/implementing-graphs-graph.png\" class=\"img-fluid\" /\u003e","code":"","full_screen":true,"solution":"","lesson_id":63,"challenge_id":null,"sequence":2,"title":"What Can We Do With Graphs?","slug":"what-can-we-do-with-graphs","created_at":"2020-06-28T19:28:56.247Z","updated_at":"2023-08-18T01:00:50.512Z","explanation":null,"summary":"A `graph` is a **programmatic representation of connected things or entities**, which uses **nodes** (dots) to represent items and connections (lines) between them known as **edges**, allowing us to model and document structures or relationships, such as those in social networks or internet web pages."},{"id":1387,"kind":"info screen","options":[],"content":"## Understanding the Concepts\n\nSome quick refreshers:\n\n### Terminology\nWhen people talk about graphs, they don't use the terms `dots` and `lines`. Instead, each dot is called a `node` or `vertex`, and each line is called an `edge`.\n\n### Formal Definition\nA formal definition of a graph is a \"data structure that consists of a finite collection of vertices and edges that represents relationships\".\n\n### Edges\nThe edges of a graph are represented as ordered or unordered pairs depending on whether or not the graph is `directed` or `undirected`.\n\nEdges of a graph might have weights indicating the strength of that link between vertices.\n\n\u003cimg src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/5/58/Weighted_Graph.svg/1280px-Weighted_Graph.svg.png\" class=\"img-fluid\" /\u003e","code":"","full_screen":true,"solution":"","lesson_id":63,"challenge_id":null,"sequence":3,"title":"Understanding the Concepts","slug":"understanding-the-concepts","created_at":"2020-06-28T19:33:20.348Z","updated_at":"2023-08-18T01:00:58.529Z","explanation":null,"summary":"In graph terminology, **dots** are referred to as `nodes` or `vertices`, **lines** are called `edges`, and the graph itself is a **data structure** representing relationships; `edges` can be ordered or unordered depending on if the graph is `directed` or `undirected`, and may have **weights** signifying the link strength between vertices."},{"id":1388,"kind":"multiple choice","options":["Nodes/Vertices and Edges","Lines","Nodes and dots","Array and lists"],"content":"What are the basic components of a graph?","code":null,"full_screen":false,"solution":"0","lesson_id":63,"challenge_id":null,"sequence":4,"title":"Basic Components of a Graph","slug":"basic-components-of-a-graph","created_at":"2020-06-28T19:36:22.276Z","updated_at":"2023-08-18T01:01:23.674Z","explanation":"A graph, in computer science and mathematics, is made up of two key components: `Nodes/Vertices` and `Edges`. \n\nA **Node**, also known as a `Vertex`, is a distinctive point on a graph. It often symbolizes a certain entity within a network such as an intersection on a map or an individual in a social network. \n\nAn **Edge**, on the other hand, is the connection or line that links two nodes together. This essentially signifies some kind of `relationship` or `interaction` between the two nodes it is connecting. \n\nThese two components, nodes and edges, are fundamentally what form a graph. The **nodes** represent distinct entities, while the **edges** symbolize the relationships or interactions between such entities. \n\nFurthermore, these relationships can have specific attributes such as `direction`, in the case of directed graphs where an edge goes from one node to another in a specific direction, or `weight` which indicates the strength or cost associated with that particular interaction. \n\nGiven this, it becomes clear why `nodes/vertices` and `edges` are the basic components of a graph. They create the framework that allows for complex data relationships to be visually represented and understood.","summary":"A **graph** in computer science and mathematics consists of two essential components, `nodes/vertices` representing distinct entities, and `edges` depicting the relationships or interactions between these entities, with attributes like `direction` and `weight` indicating specific aspects of these relationships."},{"id":1389,"kind":"info screen","options":[],"content":"Let's revisit our graph examples. One of them was the concept of a **social network** being a graph. In a social network, users can be represented with vertices. Edges denote friendship relations between them.\n\nHere is a graph/social network where members `Peter`, `Kevin`, `Jake`, and `Daniel` are the four vertices of this social network. The edges between any two members corresponding to a friendship between these members.\n\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/curriculum/graphs/implementing-graphs-friendship.png\" class=\"img-fluid\" /\u003e","code":"0","full_screen":true,"solution":"0","lesson_id":63,"challenge_id":null,"sequence":5,"title":"Social Network","slug":"social-network","created_at":"2020-06-28T19:39:56.820Z","updated_at":"2023-08-18T01:01:29.116Z","explanation":null,"summary":"The concept of a **social network** can be modeled as a graph, where **users are represented as vertices** and **friendship relations are represented as edges**, as demonstrated with a graph containing `Peter`, `Kevin`, `Jake`, and `Daniel`."},{"id":1390,"kind":"info screen","options":[],"content":"Last concept to revisit, and we'll move on to implementation!\n\n## Undirected Graphs\n\nUndirected graphs have edges that do not have a direction. With undirected graphs, we can represent two-way relationships so an edge can be traversed in both directions.\n\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/curriculum/graphs/implementing-graphs-undirected.png\" class=\"img-fluid\" /\u003e\n\nIn theory, an undirected graph could be used at Facebook, since both users have to friend each other to build a friendship.\n\n### Directed Graphs\n\nDirected graphs have edges with direction. With directed graphs, we can represent one-way relations so an edge can be traversed in a single direction.\n\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/curriculum/graphs/implementing-graphs-directed.png\" class=\"img-fluid\" /\u003e\n\nA directed graph would be used at Twitter, since the relationship can be one-sided, and you don't need to follow each of your followers.","code":"0","full_screen":true,"solution":"0","lesson_id":63,"challenge_id":null,"sequence":6,"title":"Types of Graphs","slug":"types-of-graphs","created_at":"2020-06-28T19:42:26.186Z","updated_at":"2023-08-18T01:01:33.558Z","explanation":null,"summary":"**Undirected graphs** represent **two-way relationships** with edges that can be traversed in both directions, while **directed graphs** represent **one-way relations** with edges that can be traversed in a single direction."},{"id":1391,"kind":"fill in","options":[],"content":"What is the type of graph that represents two-way relationships? In this type, an edge can be traversed in both directions.","code":null,"full_screen":false,"solution":"undirected","lesson_id":63,"challenge_id":null,"sequence":7,"title":"Fill In","slug":"type-of-graph-quiz","created_at":"2020-06-28T19:39:56.820Z","updated_at":"2023-08-18T01:02:07.267Z","explanation":"In **graph theory**, a branch of mathematics, there are two general types of graphs: `undirected` and `directed`. The type of graph that represents two-way relationships is the `undirected` graph. \n\nIn an `undirected` graph, the edges connecting the nodes do not have any direction. This lack of directionality means that an edge represents a two-way relationship — it can be traversed in **both directions**. In other words, if there is a connection between two nodes (A and B), you can go from A to B, and also from B to A. The relationship is mutual. \n\nThis characteristic makes undirected graphs suitable for representing situations where relationships are always reciprocal, such as Facebook friendships where both users have to agree to become friends.\n\nIn contrast, in `directed` graphs, edges have a direction indicating a one-way relationship which means these edges can only be traversed in one direction. For instance, in Twitter, one user can follow another without the need for the followee to follow back, making it a one-sided relationship - a characteristic of directed graphs.\n\nHence, we can say that the type of graph that represents two-way relationships, where an edge can be traversed in both directions, is an `undirected` graph.","summary":"In **graph theory**, there are two types of graphs: `undirected` graphs, which represent **two-way relationships** and can be traversed in both directions, and `directed` graphs, which represent one-way relationships and can only be traversed in one direction."},{"id":1392,"kind":"info screen","options":[],"content":"## Problems For Graphs\n\nThe applications of `graph`s are overwhelming in nature! No wonder they're so important. Here's but a few more examples.\n\n1) Finding the shortest path.\n\n2) Finding the best starting point.\n\n3) Breadth-first and depth-first traversal. \n\n4) Searching, inserting, deleting from a tree or linked list.\n\n5) Graph classification to discriminate between graphs of different classes.\n\n6) Finding the missing relationships between entities through link prediction.\n\n7) Node classification.","code":"","full_screen":true,"solution":"","lesson_id":63,"challenge_id":null,"sequence":8,"title":"Problems For Graphs","slug":"problems-for-graphs","created_at":"2020-06-28T19:51:03.584Z","updated_at":"2023-08-18T01:02:12.701Z","explanation":null,"summary":"The **applications of `graph`s** include **finding the shortest path**, **finding the best starting point**, **breadth-first and depth-first traversal**, **searching, inserting, deleting from a tree or linked list**, **graph classification**, **finding missing relationships through link prediction**, and **node classification**."},{"id":1393,"kind":"swipe","options":[],"content":"**Breadth-first** and **depth-first traversals** are two kinds of search algorithms for trees and graphs.","code":null,"full_screen":false,"solution":"true","lesson_id":63,"challenge_id":null,"sequence":9,"title":"Swipe","slug":"swipe-90ka0sd","created_at":"2020-06-28T19:52:23.416Z","updated_at":"2023-08-18T01:02:40.140Z","explanation":"The statement is **true** because **breadth-first** and **depth-first traversals** are indeed **search algorithms** often used for tree and graph data structures. \n\nA **search algorithm** is a method used to locate specific nodes or paths in a data structure. Using these algorithms, you can find and retrieve data in an efficient manner. For data structures like `trees` and `graphs`, the order in which the algorithm visits the nodes can markedly affect the outcome.\n\n**Breadth-first traversal**, also known as **breadth-first search (BFS)**, is a technique where you visit all the nodes of a given level before going on to the next level. When BFS traverses through the structure, it visits nodes in a `horizontal manner`. Starting from the root, it visits each node at a level before moving to the next level. \n\nOn the other hand, **depth-first traversal** or **depth-first search (DFS)**, is an algorithm that dives deep into the structure, visiting nodes on higher depth, before visiting the siblings of the current node. In other words, it explores the structure in a `vertical manner`. DFS visits a path as deep as possible, then if it cannot go any further, it backtracks and continues visiting the unvisited siblings. \n\nIn summary, both breadth-first and depth-first traversals are indeed kinds of search algorithms specifically designed to efficiently navigate through `graph` and `tree` data structures. The key difference is the order in which they visit the nodes.","summary":"The statement affirms that **breadth-first** and **depth-first traversals** are **search algorithms** used for navigating 'tree' and 'graph' `data structures` in a `horizontal` and `vertical manner` respectively."},{"id":1394,"kind":"info screen","options":[],"content":"### Edge Lists\n\nNow that we're all caught up on the fundamentals of graphs, let's talk **implementation**!\n\nThe first implementation strategy is called an `edge list`. An edge list is a `list` or `array` of all the edges in a graph. Edge lists are one of the easier representations of a graph. \n\nIn this implementation, the underlying data structure for keeping track of all the nodes and edges i**s a single list of pairs**. Each pair represents a single edge and is comprised of the *two unique IDs* of the nodes involved. Each `line`/`edge` in the graph gets an entry in the edge list, and that single data structure then encodes all nodes and relationships.\n\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/curriculum/graphs/implementing-graphs-edgelist.png\" class=\"img-fluid\" /\u003e\n\nIn the graph above, we have three nodes: `1`, `2`, and `3`. Each edge is given an index and represents a reference from one node to another. There isn't any particular order to the edges as they appear in the edge list, but every edge must be represented. For this example, the edge list would look like the attached snippet:\n\n```java\nint[][] edgeList = {\n\t{1,2},\n\t{2,3},\n\t{3,1}\n};\n```\n```javascript\nconst edgeList = [\n\t[1,2],\n\t[2,3],\n\t[3,1]\n];\n```\n```python\nedge_list = [\n\t[1,2],\n\t[2,3],\n\t[3,1]\n]\n```\n```cpp\nint edgeList[3][2] = {\n\t{1,2},\n\t{2,3},\n\t{3,1}\n};\n```\n```go\nvar edgeList = [][2]int{\n\t{1, 2},\n\t{2, 3},\n\t{3, 1},\n}\n```","code":"","full_screen":true,"solution":"","lesson_id":63,"challenge_id":null,"sequence":10,"title":"Edge Lists","slug":"edge-lists","created_at":"2020-06-28T19:55:39.032Z","updated_at":"2023-08-18T01:02:44.130Z","explanation":null,"summary":"An `edge list` is an **implementation strategy** for graphs where all the edges are stored in a `single list of pairs`, each pair representing an edge through the two unique IDs of the nodes involved."},{"id":1395,"kind":"info screen","options":[],"content":"Due to the fact that an edge list is really just an array, the only way to find something in this array is by iterating through it. \r\n\r\nFor example, if we wanted to see if vertex `1` was connected to vertex `2`, we'd need to iterate through the previous array and look for the existence of a pair `[1,2]` or `[2,1]`.\r\n\r\nThis is fine for this specific graph since it only has three vertices and three edges. But as you can imagine, having to iterate through a much larger array would increase complexity.\r\n\r\nChecking to see if a particular `edge` existed in a large array isn't guaranteed to have a sense of order, and the edge could be at the very end of the list. Additionally, there may not be any edge at all, and we'd still have to iterate through the whole thing to check for it. This would take linear time, `O(E)` (E being the number of edges) to get it done.\r\n\r\nPlease find the implementation of an edge list attached.","code":"```java\nimport java.util.HashSet;\nimport java.util.LinkedList;\n\nclass Node {\n    private String name;\n    private LinkedList \u003c Edge \u003e edgeList;\n\n    public Node(String name) {\n        this.name = name;\n        edgeList = new LinkedList \u003c \u003e ();\n    }\n\n    public String getName() {\n        return name;\n    }\n\n    public LinkedList \u003c Edge \u003e getEdges() {\n        return edgeList;\n    }\n}\n\nclass Edge {\n    private int weight;\n    private Node destVertex;\n\n    public Edge(Node dest, int w) {\n        this.destVertex = dest;\n        this.weight = w;\n    }\n\n    public Edge(Node dest) {\n        this.destVertex = dest;\n        this.weight = 1;\n    }\n\n    public int getWeight() {\n        return weight;\n    }\n\n    public Node getDestVertex() {\n        return destVertex;\n    }\n}\n\nclass Graph {\n    private HashSet \u003c Node \u003e nodes;\n\n    public Graph() {\n        nodes = new HashSet \u003c \u003e ();\n    }\n\n    public boolean AddEdge(Node v1, Node v2, int weight) {\n        return v1.getEdges().add(new Edge(v2, weight)) \u0026\u0026 v2.getEdges().add(new Edge(v1, weight));\n    }\n\n    public boolean AddVertex(Node v) {\n        return nodes.add(v);\n    }\n\n    public void printGraph() {\n        for (Node v: nodes) {\n            System.out.print(\"vertex name: \" + v.getName() + \":\\n\");\n            for (Edge e: v.getEdges()) {\n                System.out.print(\"destVertex: \" + e.getDestVertex().getName() + \", weight: \" + e.getWeight() + \"\\n\");\n            }\n            System.out.print(\"\\n\");\n        }\n    }\n}\n\npublic class Main {\n    public static void main(String[] args) {\n        Graph ourGraph = new Graph();\n\n        // nodes\n        Node v0 = new Node(\"0\");\n        Node v1 = new Node(\"1\");\n        Node v2 = new Node(\"2\");\n        Node v3 = new Node(\"3\");\n\n        ourGraph.AddVertex(v0);\n        ourGraph.AddVertex(v1);\n        ourGraph.AddVertex(v2);\n        ourGraph.AddVertex(v3);\n\n        // edges\n        ourGraph.AddEdge(v0, v1, 2);\n        ourGraph.AddEdge(v1, v2, 3);\n        ourGraph.AddEdge(v2, v0, 1);\n        ourGraph.AddEdge(v2, v3, 1);\n        ourGraph.AddEdge(v3, v2, 4);\n\n        ourGraph.printGraph();\n    }\n}\n```\n```javascript\nclass Node {\n    constructor(name) {\n        this.name = name;\n        this.edgeList = [];\n    }\n\n    getName() {\n        return this.name;\n    }\n\n    getEdges() {\n        return this.edgeList;\n    }\n}\n\nclass Edge {\n    constructor(dest, w = 1) {\n        this.destVertex = dest;\n        this.weight = w;\n    }\n\n    getWeight() {\n        return this.weight;\n    }\n\n    getDestVertex() {\n        return this.destVertex;\n    }\n}\n\nclass Graph {\n    constructor() {\n        this.nodes = new Set();\n    }\n\n    AddEdge(v1, v2, weight) {\n        return v1.getEdges().push(new Edge(v2, weight)) \u0026\u0026 v2.getEdges().push(new Edge(v1, weight));\n    }\n\n    AddVertex(v) {\n        return this.nodes.add(v);\n    }\n\n    printGraph() {\n        this.nodes.forEach(v =\u003e {\n            console.log(\"vertex name: \" + v.getName() + \":\");\n            v.getEdges().forEach(e =\u003e {\n                console.log(\"destVertex: \" + e.getDestVertex().getName() + \", weight: \" + e.getWeight());\n            });\n            console.log(\"\");\n        });\n    }\n}\n\nconst ourGraph = new Graph();\n\n// nodes\nconst v0 = new Node(\"0\");\nconst v1 = new Node(\"1\");\nconst v2 = new Node(\"2\");\nconst v3 = new Node(\"3\");\n\nourGraph.AddVertex(v0);\nourGraph.AddVertex(v1);\nourGraph.AddVertex(v2);\nourGraph.AddVertex(v3);\n\n// edges\nourGraph.AddEdge(v0, v1, 2);\nourGraph.AddEdge(v1, v2, 3);\nourGraph.AddEdge(v2, v0, 1);\nourGraph.AddEdge(v2, v3, 1);\nourGraph.AddEdge(v3, v2, 4);\n\nourGraph.printGraph();\n```\n```python\nclass Node:\n    def __init__(self, name):\n        self.name = name\n        self.edge_list = []\n\n    def get_name(self):\n        return self.name\n\n    def get_edges(self):\n        return self.edge_list\n\nclass Edge:\n    def __init__(self, dest, weight=1):\n        self.dest_vertex = dest\n        self.weight = weight\n\n    def get_weight(self):\n        return self.weight\n\n    def get_dest_vertex(self):\n        return self.dest_vertex\n\nclass Graph:\n    def __init__(self):\n        self.nodes = set()\n\n    def add_edge(self, v1, v2, weight):\n        return v1.get_edges().append(Edge(v2, weight)) and v2.get_edges().append(Edge(v1, weight))\n\n    def add_vertex(self, v):\n        return self.nodes.add(v)\n\n    def print_graph(self):\n        for v in self.nodes:\n            print(\"vertex name:\", v.get_name())\n            for e in v.get_edges():\n                print(\"destVertex:\", e.get_dest_vertex().get_name(), \", weight:\", e.get_weight())\n            print()\n\nour_graph = Graph()\n\n# nodes\nv0 = Node(\"0\")\nv1 = Node(\"1\")\nv2 = Node(\"2\")\nv3 = Node(\"3\")\n\nour_graph.add_vertex(v0)\nour_graph.add_vertex(v1)\nour_graph.add_vertex(v2)\nour_graph.add_vertex(v3)\n\n# edges\nour_graph.add_edge(v0, v1, 2)\nour_graph.add_edge(v1, v2, 3)\nour_graph.add_edge(v2, v0, 1)\nour_graph.add_edge(v2, v3, 1)\nour_graph.add_edge(v3, v2, 4)\n\nour_graph.print_graph()\n```\n```cpp\n#include \u003ciostream\u003e\n#include \u003cvector\u003e\n#include \u003cstring\u003e\n#include \u003cunordered_set\u003e\n\nclass Edge;\n\nclass Node {\nprivate:\n    std::string name;\n    std::vector\u003cEdge\u003e edgeList;\n\npublic:\n    Node(std::string name) : name(name) {}\n\n    std::string getName() {\n        return name;\n    }\n\n    std::vector\u003cEdge\u003e\u0026 getEdges() {\n        return edgeList;\n    }\n};\n\nclass Edge {\nprivate:\n    int weight;\n    Node* destVertex;\n\npublic:\n    Edge(Node* dest, int w) : destVertex(dest), weight(w) {}\n\n    Edge(Node* dest) : destVertex(dest), weight(1) {}\n\n    int getWeight() {\n        return weight;\n    }\n\n    Node* getDestVertex() {\n        return destVertex;\n    }\n};\n\nclass Graph {\nprivate:\n    std::unordered_set\u003cNode*\u003e nodes;\n\npublic:\n    Graph() {}\n\n    bool AddEdge(Node* v1, Node* v2, int weight) {\n        return v1-\u003egetEdges().emplace_back(v2,\n\n weight), v2-\u003egetEdges().emplace_back(v1, weight);\n    }\n\n    bool AddVertex(Node* v) {\n        return nodes.insert(v).second;\n    }\n\n    void printGraph() {\n        for (Node* v : nodes) {\n            std::cout \u003c\u003c \"vertex name: \" \u003c\u003c v-\u003egetName() \u003c\u003c \":\\n\";\n            for (Edge e : v-\u003egetEdges()) {\n                std::cout \u003c\u003c \"destVertex: \" \u003c\u003c e.getDestVertex()-\u003egetName() \u003c\u003c \", weight: \" \u003c\u003c e.getWeight() \u003c\u003c \"\\n\";\n            }\n            std::cout \u003c\u003c \"\\n\";\n        }\n    }\n};\n\nint main() {\n    Graph ourGraph;\n\n    // nodes\n    Node v0(\"0\");\n    Node v1(\"1\");\n    Node v2(\"2\");\n    Node v3(\"3\");\n\n    ourGraph.AddVertex(\u0026v0);\n    ourGraph.AddVertex(\u0026v1);\n    ourGraph.AddVertex(\u0026v2);\n    ourGraph.AddVertex(\u0026v3);\n\n    // edges\n    ourGraph.AddEdge(\u0026v0, \u0026v1, 2);\n    ourGraph.AddEdge(\u0026v1, \u0026v2, 3);\n    ourGraph.AddEdge(\u0026v2, \u0026v0, 1);\n    ourGraph.AddEdge(\u0026v2, \u0026v3, 1);\n    ourGraph.AddEdge(\u0026v3, \u0026v2, 4);\n\n    ourGraph.printGraph();\n}\n```\n```go\npackage main\n\nimport (\n\t\"fmt\"\n)\n\ntype Edge struct {\n\tweight     int\n\tdestVertex *Node\n}\n\nfunc NewEdge(dest *Node, w int) *Edge {\n\treturn \u0026Edge{destVertex: dest, weight: w}\n}\n\ntype Node struct {\n\tname     string\n\tedgeList []*Edge\n}\n\nfunc NewNode(name string) *Node {\n\treturn \u0026Node{name: name, edgeList: []*Edge{}}\n}\n\nfunc (n *Node) getName() string {\n\treturn n.name\n}\n\nfunc (n *Node) getEdges() []*Edge {\n\treturn n.edgeList\n}\n\ntype Graph struct {\n\tnodes map[*Node]bool\n}\n\nfunc NewGraph() *Graph {\n\treturn \u0026Graph{nodes: make(map[*Node]bool)}\n}\n\nfunc (g *Graph) AddEdge(v1 *Node, v2 *Node, weight int) bool {\n\tv1.getEdges() = append(v1.getEdges(), NewEdge(v2, weight))\n\tv2.getEdges() = append(v2.getEdges(), NewEdge(v1, weight))\n\treturn true\n}\n\nfunc (g *Graph) AddVertex(v *Node) bool {\n\tg.nodes[v] = true\n\treturn true\n}\n\nfunc (g *Graph) printGraph() {\n\tfor v := range g.nodes {\n\t\tfmt.Print(\"vertex name: \" + v.getName() + \":\\n\")\n\t\tfor _, e := range v.getEdges() {\n\t\t\tfmt.Print(\"destVertex: \" + e.destVertex.getName() + \", weight: \" + fmt.Sprint(e.weight) + \"\\n\")\n\t\t}\n\t\tfmt.Print(\"\\n\")\n\t}\n}\n\nfunc main() {\n\tourGraph := NewGraph()\n\n\t// nodes\n\tv0 := NewNode(\"0\")\n\tv1 := NewNode(\"1\")\n\tv2 := NewNode(\"2\")\n\tv3 := NewNode(\"3\")\n\n\tourGraph.AddVertex(v0)\n\tourGraph.AddVertex(v1)\n\tourGraph.AddVertex(v2)\n\tourGraph.AddVertex(v3)\n\n\t// edges\n\tourGraph.AddEdge(v0, v1, 2)\n\tourGraph.AddEdge(v1, v2, 3)\n\tourGraph.AddEdge(v2, v0, 1)\n\tourGraph.AddEdge(v2, v3, 1)\n\tourGraph.AddEdge(v3, v2, 4)\n\n\tourGraph.printGraph()\n}\n```","full_screen":false,"solution":null,"lesson_id":63,"challenge_id":null,"sequence":11,"title":"Edge List Limitations","slug":"edge-list-limitations","created_at":"2020-06-28T19:59:04.920Z","updated_at":"2023-08-18T01:02:48.094Z","explanation":null,"summary":"To find something in an **edge list**, an array-like data structure, one needs to **iterate through it** which is a linear time operation (`O(E)`), leading to increased complexity in the case of larger arrays."},{"id":1396,"kind":"info screen","options":[],"content":"### Adjacency Matrix\n\nWhile an `edge list` won't end up being the most efficient choice, we can move beyond a list and implement a matrix. For many, a `matrix` is a significantly better kinesthetic representation for a graph.\n\nAn `adjacency matrix` is a matrix that represents exactly which vertices/nodes in a graph have edges between them. It serves as a lookup table, where a value of `1` represents an edge that exists and a `0` represents an edge that does not exist. The indices of the matrix model the nodes.\n\nOnce we've determined the two nodes that we want to find an edge between, we look at the value at the intersection of those two nodes to determine whether there's a `link`.\n\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/curriculum/graphs/implementing-graphs-adjacencymatrix.png\" class=\"img-fluid\" /\u003e\n\nIn this illustration, we can see that the adjacency matrix has a chain of cells with value `0` diagonally. In fact, this is true of most graphs that we'll deal with, as most won't be self-referential. In other words, since node `2` does not (or can not) have a link to itself, if we were to draw a line from column `2` to row `2`, the value will be `0`. \n\nHowever, if we wanted to see if node `3` was connected to node `1`, we'd find there to be a relationship. We could find column `3`, row `1`, and see that the value is `1`, which means that there is an edge between these two nodes.\n\nAdjacency matrices are easy to follow and represent. Looking up, inserting and removing an edge can all be done in `O(1)` or `constant time`. However, they do have a downfall, which is that they can take up more space than is necessary. An adjacency matrix always consumes `O(V^2)` (`V` being vertices) amount of space.\n\nNevertheless, adjacency matrices are definitely a step up from an edge list. Their representation would look like this:","code":"```java\nint[][] matrix = {\n\t{0, 1, 1},\n\t{1, 0, 1},\n\t{1, 1, 0}\n};\n```\n```javascript\nconst matrix = [\n\t[0, 1, 1],\n\t[1, 0, 1],\n\t[1, 1, 0]\n];\n```\n```python\nmatrix = [\n\t[0, 1, 1],\n\t[1, 0, 1],\n\t[1, 1, 0]\n]\n```\n```cpp\nint matrix[3][3] = {\n\t{0, 1, 1},\n\t{1, 0, 1},\n\t{1, 1, 0}\n};\n```\n```go\nvar matrix = [3][3]int{\n\t{0, 1, 1},\n\t{1, 0, 1},\n\t{1, 1, 0},\n}\n```","full_screen":false,"solution":"","lesson_id":63,"challenge_id":null,"sequence":12,"title":"Adjacency Matrix","slug":"adjacency-matrix","created_at":"2020-06-28T20:05:59.181Z","updated_at":"2023-08-18T01:02:57.162Z","explanation":null,"summary":"An **adjacency matrix** is a type of `matrix` used to represent the vertices/nodes and connection/links in a graph, where `1` indicates an existing edge and `0` indicates a non-existing one, enabling lookup, insertion, and removal of an edge in `O(1)` or `constant time`, but consumes `O(V^2)` space, where `V` is the number of vertices."},{"id":1397,"kind":"fill in","options":[],"content":"The function below returns an object for the specified vertex. Fill in the missing snippet for the method. \n\n```java\npublic Vertex getVertex(int index) {\n    return vertices.get(___________);\n}\n```","code":null,"full_screen":false,"solution":"index","lesson_id":63,"challenge_id":null,"sequence":13,"title":"Fill In","slug":"fill-in-d1d82","created_at":"2020-06-28T20:08:13.773Z","updated_at":"2023-08-18T01:03:15.550Z","explanation":"The `get()` method takes an `index` as a parameter and returns the element at the specified position in the list. Therefore, in the context of the adjacency matrix graph representation, the missing snippet would be `index`. This is because we're trying to retrieve a specific vertex, and each vertex is located at a unique index in the `vertices` list. Thus, `index` is the integer that corresponds to the position of that vertex in the list. \n\nIn this specific method, each `vertex` (or `node` in a more general sense) in the adjacency matrix is represented by a `list`. To retrieve a vertex, you would pass the corresponding index in the list to the `get()` function. Filling in the blank with `index` means that this function now correctly retrieves the `vertex` at that particular `index` in the `vertices` list.","summary":"The `get()` method, used in the context of the adjacency matrix graph representation, takes an `index` as a parameter to return the `vertex` at that particular `index` in the `vertices` list, representing each `vertex` or `node` in the graph as a `list`."},{"id":1398,"kind":"info screen","options":[],"content":"Here's a complete implementation of an `adjacency matrix`.","code":"```java\nclass Graph {\n    private boolean adjMatrix[][];\n    private int numVertices;\n\n    // Initialize the matrix\n    public Graph(int numVertices) {\n        this.numVertices = numVertices;\n        adjMatrix = new boolean[numVertices][numVertices];\n    }\n\n    // Add edges\n    public void addEdge(int i, int j) {\n        adjMatrix[i][j] = true;\n        adjMatrix[j][i] = true;\n    }\n\n    // Remove edges\n    public void removeEdge(int i, int j) {\n        adjMatrix[i][j] = false;\n        adjMatrix[j][i] = false;\n    }\n\n    public String toString() {\n        StringBuilder s = new StringBuilder();\n        for (int i = 0; i \u003c numVertices; i++) {\n            s.append(i + \": \");\n            for (boolean j: adjMatrix[i]) {\n                s.append((j ? 1 : 0) + \" \");\n            }\n            s.append(\"\\n\");\n        }\n        return s.toString();\n    }\n}\n\nclass Main {\n    public static void main(String args[]) {\n        Graph g = new Graph(4);\n\n        g.addEdge(0, 1);\n        g.addEdge(0, 2);\n        g.addEdge(1, 2);\n        g.addEdge(2, 0);\n        g.addEdge(2, 3);\n\n        System.out.print(g.toString());\n    }\n\n}\n```\n```javascript\nclass Graph {\n    constructor(numVertices) {\n        this.numVertices = numVertices;\n        this.adjMatrix = Array.from({ length: numVertices }, () =\u003e Array(numVertices).fill(false));\n    }\n\n    addEdge(i, j) {\n        this.adjMatrix[i][j] = true;\n        this.adjMatrix[j][i] = true;\n    }\n\n    removeEdge(i, j) {\n        this.adjMatrix[i][j] = false;\n        this.adjMatrix[j][i] = false;\n    }\n\n    toString() {\n        let s = \"\";\n        for (let i = 0; i \u003c this.numVertices; i++) {\n            s += i + \": \";\n            for (const j of this.adjMatrix[i]) {\n                s += (j ? 1 : 0) + \" \";\n            }\n            s += \"\\n\";\n        }\n        return s;\n    }\n}\n\nconst g = new Graph(4);\n\ng.addEdge(0, 1);\ng.addEdge(0, 2);\ng.addEdge(1, 2);\ng.addEdge(2, 0);\ng.addEdge(2, 3);\n\nconsole.log(g.toString());\n```\n```python\n# Original code in Java\nclass Graph:\n    def __init__(self, num_vertices):\n        self.num_vertices = num_vertices\n        self.adj_matrix = [[False] * num_vertices for _ in range(num_vertices)]\n\n    def add_edge(self, i, j):\n        self.adj_matrix[i][j] = True\n        self.adj_matrix[j][i] = True\n\n    def remove_edge(self, i, j):\n        self.adj_matrix[i][j] = False\n        self.adj_matrix[j][i] = False\n\n    def __str__(self):\n        s = \"\"\n        for i in range(self.num_vertices):\n            s += str(i) + \": \"\n            s += \" \".join([\"1\" if j else \"0\" for j in self.adj_matrix[i]]) + \"\\n\"\n        return s\n\n\ng = Graph(4)\ng.add_edge(0, 1)\ng.add_edge(0, 2)\ng.add_edge(1, 2)\ng.add_edge(2, 0)\ng.add_edge(2, 3)\n\nprint(g)\n```\n```cpp\n#include \u003ciostream\u003e\n#include \u003cvector\u003e\n\nclass Graph {\nprivate:\n    std::vector\u003cstd::vector\u003cbool\u003e\u003e adjMatrix;\n    int numVertices;\n\npublic:\n    Graph(int numVertices) : numVertices(numVertices) {\n        adjMatrix.resize(numVertices, std::vector\u003cbool\u003e(numVertices, false));\n    }\n\n    void addEdge(int i, int j) {\n        adjMatrix[i][j] = true;\n        adjMatrix[j][i] = true;\n    }\n\n    void removeEdge(int i, int j) {\n        adjMatrix[i][j] = false;\n        adjMatrix[j][i] = false;\n    }\n\n    void printGraph() {\n        for (int i = 0; i \u003c numVertices; i++) {\n            std::cout \u003c\u003c i \u003c\u003c \": \";\n            for (bool j : adjMatrix[i]) {\n                std::cout \u003c\u003c (j ? 1 : 0) \u003c\u003c \" \";\n            }\n            std::cout \u003c\u003c \"\\n\";\n        }\n    }\n};\n\nint main() {\n    Graph g(4);\n\n    g.addEdge(0, 1);\n    g.addEdge(0, 2);\n    g.addEdge(1, 2);\n    g.addEdge(2, 0);\n    g.addEdge(2, 3);\n\n    g.printGraph();\n}\n```\n```go\n// Original code in Java\npackage main\n\nimport (\n\t\"fmt\"\n)\n\ntype Graph struct {\n\tadjMatrix   [][]bool\n\tnumVertices int\n}\n\nfunc NewGraph(numVertices int) *Graph {\n\tadjMatrix := make([][]bool, numVertices)\n\tfor i := range adjMatrix {\n\t\tadjMatrix[i] = make([]bool, numVertices)\n\t}\n\treturn \u0026Graph{adjMatrix: adjMatrix, numVertices: numVertices}\n}\n\nfunc (g *Graph) AddEdge(i int, j int) {\n\tg.adjMatrix[i][j] = true\n\tg.adjMatrix[j][i] = true\n}\n\nfunc (g *Graph) RemoveEdge(i int, j int) {\n\tg.adjMatrix[i][j] = false\n\tg.adjMatrix[j][i] = false\n}\n\nfunc (g *Graph) PrintGraph() {\n\tfor i := 0; i \u003c g.numVertices; i++ {\n\t\tfmt.Print(i, \": \")\n\t\tfor _, j := range g.adjMatrix[i] {\n\t\t\tfmt.Print(map[bool]int{false: 0, true: 1}[j], \" \")\n\t\t}\n\t\tfmt.Println()\n\t}\n}\n\nfunc main() {\n\tg := NewGraph(4)\n\n\tg.AddEdge(0, 1)\n\tg.AddEdge(0, 2)\n\tg.AddEdge(1, 2)\n\tg.AddEdge(2, 0)\n\tg.AddEdge(2, 3)\n\n\tg.PrintGraph()\n}\n```","full_screen":false,"solution":null,"lesson_id":63,"challenge_id":null,"sequence":14,"title":"Implementation of Adjacency Matrix","slug":"implementation-of-adjacency-matrix","created_at":"2020-06-28T20:09:41.903Z","updated_at":"2023-08-18T01:03:18.604Z","explanation":null,"summary":"This provides a **complete implementation** of an `adjacency matrix`."},{"id":1399,"kind":"multiple choice","options":["Finds the average of all the vertices in the matrix","Counts the total of all vertices in the matrix","Returns a String containing all the attributes of the matrix","Stores the name of the matrix in a String"],"content":"What does the `toString()` method do in the previous code?","code":null,"full_screen":false,"solution":"2","lesson_id":63,"challenge_id":null,"sequence":15,"title":"Previous Code Analysis","slug":"previous-code-analysis","created_at":"2020-06-28T20:11:31.759Z","updated_at":"2023-08-18T01:03:43.591Z","explanation":"The `toString()` method is a special method in Java, used for **string representation** of an object. It is called implicitly when an object is outputted in a string context (via `System.out.println()`, for example), or explicitly when `toString()` is called on an object. \n\nIn the context of the adjacency matrix code mentioned, the `toString()` method would most likely have been overridden (or redefined) in the **Matrix class definition** to create a more meaningful and useful string representation. Instead of merely returning a memory location or class @hash combination (which is the default behavior of `toString()` in Java's `Object` class), this implementation of `toString()` returns a `String` that contains **all of the attributes** of the matrix. \n\nThis could mean it's outputting the size of the matrix, as well as all the values held within the matrix, in an organized and readable format. To do this, the method would have loops that run through the matrix, append the values to a StringBuilder or String object, and then return the constructed `String`. The overridden `toString()` method thus provides a neat way of viewing all the data associated with a Matrix object without having to access and print each attribute individually.","summary":"The `toString()` method in Java, overridden in the **Matrix class definition**, creates a readable **string representation** of an object by returning a `String` that contains **all attributes** of the object, such as the size and values of a matrix, thereby providing an efficient way to view all data related to the object."},{"id":1400,"kind":"info screen","options":[],"content":"### Adjacency Lists\n\nLet's say both `edge lists` and `adjacency matrices` seem to fail our requirements, what do we do? Well, we combine them together and **create a hybrid implementation!**\n\nThis is what an `adjacency list` is-- a *hybrid between an adjacency matrix and an edge list*. An `adjacency list` is an array of linked lists that serves the purpose of representing a graph. What makes it unique is that its shape also makes it easy to see which vertices are adjacent to any other vertices. Each `vertex` in a graph can easily reference its neighbors through a linked list.\n\nDue to this, an adjacency list is the most common representation of a `graph`. Another reason is that graph traversal problems often require us to be able to easily figure out which nodes are the neighbors of another node. In most graph traversal interview problems, we don't really need to build the entire graph. Rather, it's important to know where we can travel (or in other words, who the neighbors of a node are).","code":"","full_screen":true,"solution":"","lesson_id":63,"challenge_id":null,"sequence":16,"title":"Intro To Adjacency List","slug":"intro-to-adjacency-list","created_at":"2020-06-28T20:16:14.242Z","updated_at":"2023-08-18T01:03:48.393Z","explanation":null,"summary":"An **`adjacency list`** is a **hybrid of an edge list and an adjacency matrix**, serving as the most common representation of a `graph` due to its linked list structure that makes it easy to identify neighboring vertices, which is crucial for graph traversal problems."},{"id":1401,"kind":"info screen","options":[],"content":"\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/curriculum/graphs/implementing-graphs-adjacencylist.png\" class=\"img-fluid\" /\u003e\r\n\r\nIn this illustration, each vertex is given an index in its `list`. The `list` has all of its neighboring vertices stored as a linked list (can also be an array) adjacent to it.\r\n\r\n*For example*, the last element in the list is the vertex `3`, which has a pointer to a linked list of its neighbors. The list that is adjacent to vertex `3` contains references to two other vertices (`1` and `2`), which are the two nodes that are connected to the node `3`.\r\n\r\nThus, just by **looking up the node** `3`, we can quickly determine who its neighbors are and, by proxy, realize that it has two edges connected to it.\r\n\r\nThis all results from the structure of an adjacency list making it easy to determine all the neighbors of one particular vertex. In fact, retrieving one node's neighbors takes `constant` or `O(1)` time, since all we  need to do is find the index of the node we're looking for and pull out its list of adjacent vertices.\r\n\r\nPlease see the implementation of adjacency list attached.","code":"```java\nimport java.util.ArrayList;\nimport java.util.Arrays;\nimport java.util.List;\n\n// data structure to store graph edges\nclass Edge {\n    int src, dest, weight;\n\n    Edge(int src, int dest, int weight) {\n        this.src = src;\n        this.dest = dest;\n        this.weight = weight;\n    }\n};\n\nclass Graph {\n\n    // data structure for adjacency list node\n    static class Node {\n        int value, weight;\n\n        Node(int value, int weight) {\n            this.value = value;\n            this.weight = weight;\n        }\n    };\n\n    // A list of lists to represent adjacency list\n    List \u003c List \u003c Node \u003e\u003e adj = new ArrayList \u003c \u003e ();\n\n    public Graph(List \u003c Edge \u003e edges) {\n        for (int i = 0; i \u003c edges.size(); i++)\n            adj.add(i, new ArrayList \u003c \u003e ());\n\n        // add edges to the undirected graph\n        for (Edge e: edges) {\n            adj.get(e.src).add(new Node(e.dest, e.weight));\n\n        }\n    }\n\n    // print adjacency list representation of graph\n    public static void printGraph(Graph graph) {\n        int src = 0;\n        int n = graph.adj.size();\n\n        while (src \u003c n) {\n            for (Node edge: graph.adj.get(src)) {\n                System.out.print(src + \" --\u003e \" + edge.value +\n                        \" (\" + edge.weight + \")\\t\");\n            }\n\n            System.out.println();\n            src++;\n        }\n    }\n}\n\nclass Main {\n    public static void main(String[] args) {\n\n        List \u003c Edge \u003e edges = Arrays.asList(new Edge(0, 1, 6), new Edge(1, 2, 7),\n                new Edge(2, 0, 5), new Edge(2, 1, 4),\n                new Edge(3, 2, 10), new Edge(4, 5, 1),\n                new Edge(5, 4, 3));\n\n        Graph graph = new Graph(edges);\n\n        // print adjacency list representation of the graph\n        graph.printGraph(graph);\n    }\n}\n\n\n```\n```py\n# Class representing a simple graph using an edge list converted to adjacency list\nclass Graph:\n    # Basic constructor method\n    def __init__(self, edge_list, num_of_nodes):\n        # Convert edge list to adjacency list,\n        # represented with a multi-dimensional array\n        self.adjacency_list = [[] for _ in range(num_of_nodes)]\n \n        # Add edges to corresponding nodes of the graph\n        for (origin, dest) in edge_list:\n            self.adjacency_list[origin].append(dest)\n \n \n# Helper method to print adjacency list representation\ndef print_graph(graph):\n    for origin in range(len(graph.adjacency_list)):\n        # print current vertex and all its neighboring vertices\n        for dest in graph.adjacency_list[origin]:\n            print(f'{origin} —\u003e {dest} ', end='')\n        print()\n \n \nif __name__ == '__main__':\n    # Set up an edge list and number of nodes\n    edge_list = [(0, 1), (1, 2), (2, 3), (0, 2), (3, 2), (4, 5), (5, 4)]\n    num_of_nodes = 6\n \n    graph = Graph(edge_list, num_of_nodes) \n    print_graph(graph)\n```\n```js\nclass Graph {\n  constructor() {\n    this.adjacencyList = new Map();\n  }\n\n  addVertex(nodeVal) {\n    this.adjacencyList.set(nodeVal, []);\n  }\n\n  addEdge(src, dest) {\n    this.adjacencyList.get(src).push(dest);\n    this.adjacencyList.get(dest).push(src);\n  }\n\n  removeVertex(val) {\n    if (this.adjacencyList.get(val)) {\n      this.adjacencyList.delete(val);\n    }\n\n    this.adjacencyList.forEach((vertex) =\u003e {\n      const neighborIdx = vertex.indexOf(val);\n      if (neighborIdx \u003e= 0) {\n        vertex.splice(neighborIdx, 1);\n      }\n    });\n  }\n\n  removeEdge(src, dest) {\n    const srcDestIdx = this.adjacencyList.get(src).indexOf(dest);\n    this.adjacencyList.get(src).splice(srcDestIdx, 1);\n\n    const destSrcIdx = this.adjacencyList.get(dest).indexOf(src);\n    this.adjacencyList.get(dest).splice(destSrcIdx, 1);\n  }\n\n  printNeighbors() {\n    const result = [];\n\n    for (let vertex of this.adjacencyList.keys()) {\n      const neighbors = [];\n\n      neighbors.push(`${vertex}:`);\n\n      this.adjacencyList.get(vertex).forEach((neighbor) =\u003e {\n        neighbors.push(neighbor);\n      });\n\n      result.push(neighbors.join(' '));\n    }\n\n    return result;\n  }\n}\n```\n```cpp\n#include \u003ciostream\u003e\n#include \u003cvector\u003e\n\n// data structure to store graph edges\nclass Edge {\npublic:\n    int src, dest, weight;\n\n    Edge(int src, int dest, int weight) : src(src), dest(dest), weight(weight) {}\n};\n\nclass Node {\npublic:\n    int value, weight;\n\n    Node(int value, int weight) : value(value), weight(weight) {}\n};\n\nclass Graph {\npublic:\n    // A list of lists to represent adjacency list\n    std::vector\u003cstd::vector\u003cNode\u003e\u003e adj;\n\n    Graph(std::vector\u003cEdge\u003e edges) {\n        adj.resize(edges.size());\n\n        // add edges to the undirected graph\n        for (Edge\u0026 e : edges) {\n            adj[e.src].emplace_back(e.dest, e.weight);\n        }\n    }\n\n    // print adjacency list representation of graph\n    static void printGraph(Graph graph) {\n        int src = 0;\n        int n = graph.adj.size();\n\n        while (src \u003c n) {\n            for (Node edge : graph.adj[src]) {\n                std::cout \u003c\u003c src \u003c\u003c \" --\u003e \" \u003c\u003c edge.value \u003c\u003c\n                        \" (\" \u003c\u003c edge.weight \u003c\u003c \")\\t\";\n            }\n\n            std::cout \u003c\u003c std::endl;\n            src++;\n        }\n    }\n};\n\nint main() {\n    std::vector\u003cEdge\u003e edges = {\n        {0, 1, 6}, {1, 2, 7}, {2, 0, 5}, {2, 1, 4},\n        {3, 2, 10}, {4, 5, 1}, {5, 4, 3}\n    };\n\n    Graph graph(edges);\n\n    // print adjacency list representation of the graph\n    Graph::printGraph(graph);\n}\n\n```\n```go\n// Original code in Java\npackage main\n\nimport (\n\t\"fmt\"\n)\n\ntype Edge struct {\n\tsrc, dest, weight int\n}\n\ntype Node struct {\n\tvalue, weight int\n}\n\ntype Graph struct {\n\tadj [][]Node\n}\n\nfunc NewGraph(edges []Edge) *Graph {\n\tadj := make([][]Node, len(edges))\n\n\tfor _, e := range edges {\n\t\tadj[e.src] = append(adj[e.src], Node{e.dest, e.weight})\n\t}\n\n\treturn \u0026Graph{adj: adj}\n}\n\nfunc printGraph(graph *Graph) {\n\tsrc := 0\n\tn := len(graph.adj)\n\n\tfor src \u003c n {\n\t\tfor _, edge := range graph.adj[src] {\n\t\t\tfmt.Printf(\"%d --\u003e %d (%d)\\t\", src, edge.value, edge.weight)\n\t\t}\n\n\t\tfmt.Println()\n\t\tsrc++\n\t}\n}\n\nfunc main() {\n\tedges := []Edge{\n\t\t{0, 1, 6}, {1, 2, 7}, {2, 0, 5}, {2, 1, 4},\n\t\t{3, 2, 10}, {4, 5, 1}, {5, 4, 3},\n\t}\n\n\tgraph := NewGraph(edges)\n\n\t// print adjacency list representation of the graph\n\tprintGraph(graph)\n}\n\n```","full_screen":false,"solution":null,"lesson_id":63,"challenge_id":null,"sequence":17,"title":"Implementation of an Adjacency List","slug":"implementation-of-an-adjacency-list","created_at":"2020-06-28T20:18:58.369Z","updated_at":"2023-08-18T01:03:53.922Z","explanation":null,"summary":"The illustration depicts an **adjacency list** where each `vertex` has an index in its `list` with neighboring vertices stored as a linked list or array, enabling quick determination of a node's neighbors and their connections, taking a `constant` or `O(1)` time to retrieve."},{"id":1402,"kind":"info screen","options":[],"content":"## Conclusion\n\nChances are if you build anything complex with computation, you'll use a graph whether you know it or not. Understanding the basics of implementing graphs and is fundamental to unpacking some of the most complicated and well-known computer science problems.","code":"","full_screen":true,"solution":"","lesson_id":63,"challenge_id":null,"sequence":18,"title":"Conclusion","slug":"conclusion","created_at":"2020-06-28T20:20:56.455Z","updated_at":"2023-08-18T01:03:56.619Z","explanation":null,"summary":"Understanding the **basics of implementing graphs** is fundamental to solving complex **computer science problems**, since **graphs** are likely utilized in any complex `computation`."},{"id":5631,"kind":"info screen","options":[],"content":"## One Pager Cheat Sheet\n\n- The `graph` data structure, though often intimidating to students, is a crucial tool for modeling information, allowing for complex abilities like social networking, and is used by companies like **LinkedIn and Google** to understand networks and relationships through various **graph algorithms**.\n- A `graph` is a **programmatic representation of connected things or entities**, which uses **nodes** (dots) to represent items and connections (lines) between them known as **edges**, allowing us to model and document structures or relationships, such as those in social networks or internet web pages.\n- In graph terminology, **dots** are referred to as `nodes` or `vertices`, **lines** are called `edges`, and the graph itself is a **data structure** representing relationships; `edges` can be ordered or unordered depending on if the graph is `directed` or `undirected`, and may have **weights** signifying the link strength between vertices.\n- A **graph** in computer science and mathematics consists of two essential components, `nodes/vertices` representing distinct entities, and `edges` depicting the relationships or interactions between these entities, with attributes like `direction` and `weight` indicating specific aspects of these relationships.\n- The concept of a **social network** can be modeled as a graph, where **users are represented as vertices** and **friendship relations are represented as edges**, as demonstrated with a graph containing `Peter`, `Kevin`, `Jake`, and `Daniel`.\n- **Undirected graphs** represent **two-way relationships** with edges that can be traversed in both directions, while **directed graphs** represent **one-way relations** with edges that can be traversed in a single direction.\n- In **graph theory**, there are two types of graphs: `undirected` graphs, which represent **two-way relationships** and can be traversed in both directions, and `directed` graphs, which represent one-way relationships and can only be traversed in one direction.\n- The **applications of `graph`s** include **finding the shortest path**, **finding the best starting point**, **breadth-first and depth-first traversal**, **searching, inserting, deleting from a tree or linked list**, **graph classification**, **finding missing relationships through link prediction**, and **node classification**.\n- The statement affirms that **breadth-first** and **depth-first traversals** are **search algorithms** used for navigating 'tree' and 'graph' `data structures` in a `horizontal` and `vertical manner` respectively.\n- An `edge list` is an **implementation strategy** for graphs where all the edges are stored in a `single list of pairs`, each pair representing an edge through the two unique IDs of the nodes involved.\n- To find something in an **edge list**, an array-like data structure, one needs to **iterate through it** which is a linear time operation (`O(E)`), leading to increased complexity in the case of larger arrays.\n- An **adjacency matrix** is a type of `matrix` used to represent the vertices/nodes and connection/links in a graph, where `1` indicates an existing edge and `0` indicates a non-existing one, enabling lookup, insertion, and removal of an edge in `O(1)` or `constant time`, but consumes `O(V^2)` space, where `V` is the number of vertices.\n- The `get()` method, used in the context of the adjacency matrix graph representation, takes an `index` as a parameter to return the `vertex` at that particular `index` in the `vertices` list, representing each `vertex` or `node` in the graph as a `list`.\n- This provides a **complete implementation** of an `adjacency matrix`.\n- The `toString()` method in Java, overridden in the **Matrix class definition**, creates a readable **string representation** of an object by returning a `String` that contains **all attributes** of the object, such as the size and values of a matrix, thereby providing an efficient way to view all data related to the object.\n- An **`adjacency list`** is a **hybrid of an edge list and an adjacency matrix**, serving as the most common representation of a `graph` due to its linked list structure that makes it easy to identify neighboring vertices, which is crucial for graph traversal problems.\n- The illustration depicts an **adjacency list** where each `vertex` has an index in its `list` with neighboring vertices stored as a linked list or array, enabling quick determination of a node's neighbors and their connections, taking a `constant` or `O(1)` time to retrieve.\n- Understanding the **basics of implementing graphs** is fundamental to solving complex **computer science problems**, since **graphs** are likely utilized in any complex `computation`.","code":null,"full_screen":true,"solution":null,"lesson_id":63,"challenge_id":null,"sequence":19,"title":"One Pager Cheat Sheet","slug":"algodaily-cheatsheet","created_at":"2023-01-07T13:34:25.352Z","updated_at":"2023-08-18T01:04:05.957Z","explanation":null,"summary":"**Graphs** are a vital tool in **modeling relationships and patterns**, consisting of `nodes` and `edges` that may be `weighted` to express connection strength. They are used in applications such as social networks, with `undirected graphs` representing two-way relationships like friendships, and **finding the shortest path**, **node classification**, and **link prediction** among its uses. Graphs can be represented using `edge lists`, `adjacency matrices`, and `adjacency lists`, each with distinct advantages and complexities. Understanding the **basics of implementing graphs** equips one to address `complex computer science problems`."}],"beforeArr":["Lesson","simple-reference-to-graphs"],"nextArr":["Lesson","basic-graph-algorithms"],"section":{"id":10,"title":"Draw a Graph","slug":"draw-a-graph","sequence":18,"description":"In programming, we use \u003ccode\u003egraph\u003c/code\u003es to model relationships between objects. Social media, map and GIS software, and the entire \u003cstrong\u003eWorld Wide Web\u003c/strong\u003e are built on top of these simple but foundational data structures.\n\nSo what exactly is a graph? A graph is a collection of nodes connected by edges (or lines). Nodes can be anything: people, places, things. Edges connect two or more nodes together. If you're familiar with social networking sites like Facebook or Twitter, you've already seen graphs in action.\n\nGraphs are an extremely powerful tool for understanding our world because they capture relationships between objects, or how those objects relate to one another. You can use them to represent everything from connections between friends on social networks, to road networks that criss-cross cities and countries around the world.","created_at":"2020-05-29T00:15:09.065Z","updated_at":"2022-08-29T16:11:51.148Z","image_url":"https://storage.googleapis.com/algodailyrandomassets/sections/draw-a-graph.png","course_id":3,"published":true,"locked":true,"time":"3.7 hours","code_snippets_count":45,"visuals_count":61,"free_tutorials":6,"videos_count":1},"course":{"id":3,"title":"Data Structures and Algorithms 🚀","image_url":"https://storage.googleapis.com/algodailyrandomassets/tutorials-optimized/find-duplicate-words-cover-image.png","description":"The _O.G._ of all of our material, this jam-packed course presents all the necessary data structures and algorithmic concepts you need to know for any whiteboard interview.\n\nWith our award-winning visual and interactive method, we break down tough and complex algorithms into simple steps you can follow. Data structures become your friend once you see them in action, and understand the beauty of their implementations.\n\nOver 25k developers have used this course to finally \"see\" algorithmic patterns and utilize them on interview game-day. Try it out for yourself, and de-mystify this cornerstone aspect of Computer Science.","slug":"data-structures-and-algorithms","mini_course":false,"sequence":4,"user_id":1,"created_at":"2021-06-18T21:19:08.152Z","updated_at":"2023-08-17T13:45:29.523Z","published":true,"time":"45.2 hours","author_details":null,"difficulty":6,"lessons_count":44,"challenges_count":141,"code_snippets_count":1334,"visuals_count":633,"free_tutorials":81,"users_taking":40245,"locked":true,"videos_count":46,"newsletter_title":"AlgoDaily DS \u0026 Algos","kind":"essentials","status":null,"user_background":null,"language":null,"interest_string":null},"screen_completions":[]}