curriculum/challenges/english/blocks/lecture-understanding-graphs-and-trees/68420c5ac17cf26ab2a4ca3c.md
Graphs are data structures used to represent the connections or relationships between objects or entities. They're often used to model networks.
The types of networks that you can model with a graph include social networks, transportation networks, communications networks, and even recommendation systems.
For example, graphs can represent connections between users on a social media platform, or connections between cities on a road network.
They're very versatile.
A graph is often represented as a collection of points or circles connected by lines.
These circles and lines represent the two main components of a graph: nodes and edges.
Nodes, also known as vertices, represent the objects or entities that are part of the network modeled by the graph. They could be users, products, stations, cities, or any other entities in the model.
In this example, nodes are represented as circles and labeled with the letters A, B, C, D, and E to distinguish them visually.
Edges are the connections between the nodes. If two nodes are connected by an edge, that means that they're somehow connected in the network.
In this example, there are five edges connecting the different pairs of nodes. Node A is connected to node B. node B is connected to nodes A, C, and D and so on.
The specific meaning of the connection will depend on the context. It may be physical, like a real road that connects two cities, or it could be more abstract, like the connection between two users on a social media platform.
If two nodes are directly connected by an edge, like nodes A and B in this example, they're known as adjacent nodes.
There are different types of graphs with different characteristics and applications. Let's go over some of them.
Undirected graphs are graphs where the edges don't have a specific direction. This type of edge is usually represented with a straight line between the nodes.
This means that, if there's an edge connecting nodes A and B, the connection works in both directions: from node A to node B and from node B to node A.
Depending on the network that is being modeled by the graph, this connection can have different meanings.
For example, if you're modeling connections between users of a social media platform, this means that user A is connected to user B and user B is connected to user A. The connection is bidirectional.
In contrast, directed graphs are graphs where the edges do have a specific direction.
If there is a connection from node A to node B, that doesn't necessarily imply that there is a connection from node B to node A.
The edges of a directed graph are often represented as straight lines that end with an arrow to indicate the direction.
Here's an example. In this graph, you can go from node A to node B but not from node B to node A because of the direction of the edge.
For example, if you are modeling a road network, this would be helpful to model one-way streets or roads. You can go from city A to city B through that road, but not from city B to city A. You'll need to take a different route.
If there is a two-way connection between the nodes of a directed graph, you can represent this with two directed edges between them.
Here you can see an example. You can go from node B to node D and from node D to node B because there are two edges connecting them, but each edge has a direction.
A vertex labeled graph is a graph in which each node is associated with a label or identifier in addition to its data. These labels are used to identify the nodes, represent them visually, and store additional information about them.
For example, in a transportation network graph, nodes could be cities and their labels could be their names, coordinates, or any other characteristic that would be helpful for the purposes of the model.
Cyclic graphs are directed graphs with at least one cycle.
A cycle is a path that you can follow through the edges of a graph that will take you back to the initial node where you started.
In this example, we have a directed graph. If you look more closely, you'll notice that it has a cycle. If we start at node B, go to node C, and then to node D, we can go back to node B again through the directed edges.
This is a cycle, so this is a cyclic graph.
In edge labeled graphs, edges are associated with labels. These labels are usually drawn next to their corresponding edges.
Weighted graphs are a specific type of edge labeled graph in which the labels on the edges represent values that can be compared and used to perform arithmetic operations.
Some edges have a higher weight, while others have a lower weight. These weights represent the "cost" of the edge.
For example, they may represent the distance between two cities or the time it takes to get from one city to the next.
This is an example of a weighted graph. We write each weight next to its corresponding edge. The "cost" of going from node B to node D is 3, and since this is an undirected graph, that's the same cost of going from node D back to node B.
Another very common type of graph in computer science is the directed acyclic graph, which is a directed graph with no cycles.
Here's an example. It's a directed graph because each edge has a direction.
It's acyclic because it doesn't have any cycles. Why? Notice that, if you start at a specific node, you cannot go back to it because of the direction of the edges.
And the last type of graph that we'll cover in this lesson is the disconnected graph.
A disconnected graph is a graph with two or more groups of nodes that are not connected by any edges.
A real-world example would be a social media network, where you have two or more groups of people who don't know each other and who have no friends in common.
This is an example. The first component has the nodes A, B, and C. The second component has the nodes D and E. These components don't have any edges between them, so this is a disconnected graph.
You can implement graphs in a variety of ways, including sets, functions, and arrays. You'll learn more about this in the coming lessons.
Understanding graphs and the characteristics of the different types of graphs is essential for solving a wide range of problems in computer science and other fields.
What is a graph in computer science?
A data structure used to represent relationships between objects.
A mathematical equation.
Think about how graphs are used to model connections and relationships.
A visual representation of data.
Think about how graphs are used to model connections and relationships.
A programming language.
Think about how graphs are used to model connections and relationships.
1
What are the two main components of a graph?
Points and lines
Think about the basic building blocks of a graph.
Vertices and nodes
Think about the basic building blocks of a graph.
Nodes and edges
Elements and vertices
Think about the basic building blocks of a graph.
3
What is a directed graph?
A graph where edges do not have a direction.
Think about whether the connections between nodes have a specific direction.
A graph where edges have a direction.
A graph with more nodes than edges.
Think about whether the connections between nodes have a specific direction.
A graph with more edges than nodes.
Think about whether the connections between nodes have a specific direction.
2