Graphs

Next tutorial: Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms implementation

In this tutorial we'll learn what are graphs and why we need them in our programming exercises.

We'll talk about graphs and graph theory from the point of view of the programmer. Graph theory is a study that deals with abstract objects and relations between them. Graph is a data structure that consists of nodes (objects, points, vertices). Nodes are connected by the edges (arcs, lines). In our programs nodes can be: cities, rooms, tiles and edges: roads, doors, walls.

Graph can be directed and undirected. For example one-way road on the street between crossroads A and B is an example of directed graph - there is way from first node A to the second node B, but not from the second to the first. If there is two-way road between crossroads A and B, this still be directed graph, but in this case there will be two edges between A and B: from A to B and from B to A. Example of undirected graph: single-track railroad - trains can move in both directions on one track.

Graph implementation in Python

In Python we can easily implement graphs with built-in data types. Let's see example:

graph = { "a": ["c"], "b": ["a", "f"], "c": ["a", "d", "e"], "d": ["b"], "e": ["f", "c"], "f": ["e", "g"], "g": ["h","i"], "h": ["j"], "i": ["f", "e"], "j": ["i"]}

Here we are using dictionary of lists to implement graph. The next step would be to put such structure in a separate class which can represent graphs. This is directed graphs. We can make graph undirected by adding edges to both ends:

graph = { "a": ["b", "c"], "b": ["a", "d", "f"], "c": ["a", "d", "e"], "d": ["b", "c"], "e": ["c", "f", "i"], "f": ["b", "e", "g", "i"], "g": ["f", "h","i"], "h": ["g", "j"], "i": ["f", "g", "e", "j"], "j": ["i"]}

Two nodes are adjacent when they directly connected by edge (not through other node).

Path in a graph is a sequence of nodes whose edges connect any two nodes. For example, path between nodes ai could be ["a","b", "f", "i", "j"]. Or ["a", "c", "e", "i", "j"]. There can be many paths between two nodes.

If there are no repeated nodes, such path is called simple.
The text passage provides an introduction to graphs and graph theory, explaining the basic concepts and providing an example of how graphs can be implemented in Python. It does not contain any mathematical questions or answers.
no_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
Graphs

Next tutorial: Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms implementation

In this tutorial we'll learn what are graphs and why we need them in our programming exercises.

We'll talk about graphs and graph theory from the point of view of the programmer. Graph theory is a study that deals with abstract objects and relations between them. Graph is a data structure that consists of nodes (objects, points, vertices). Nodes are connected by the edges (arcs, lines). In our programs nodes can be: cities, rooms, tiles and edges: roads, doors, walls.

Graph can be directed and undirected. For example one-way road on the street between crossroads A and B is an example of directed graph - there is way from first node A to the second node B, but not from the second to the first. If there is two-way road between crossroads A and B, this still be directed graph, but in this case there will be two edges between A and B: from A to B and from B to A. Example of undirected graph: single-track railroad - trains can move in both directions on one track.

Graph implementation in Python

In Python we can easily implement graphs with built-in data types. Let's see example:

graph = { "a": ["c"], "b": ["a", "f"], "c": ["a", "d", "e"], "d": ["b"], "e": ["f", "c"], "f": ["e", "g"], "g": ["h","i"], "h": ["j"], "i": ["f", "e"], "j": ["i"]}

Here we are using dictionary of lists to implement graph. The next step would be to put such structure in a separate class which can represent graphs. This is directed graphs. We can make graph undirected by adding edges to both ends:

graph = { "a": ["b", "c"], "b": ["a", "d", "f"], "c": ["a", "d", "e"], "d": ["b", "c"], "e": ["c", "f", "i"], "f": ["b", "e", "g", "i"], "g": ["f", "h","i"], "h": ["g", "j"], "i": ["f", "g", "e", "j"], "j": ["i"]}

Two nodes are adjacent when they directly connected by edge (not through other node).

Path in a graph is a sequence of nodes whose edges connect any two nodes. For example, path between nodes ai could be ["a","b", "f", "i", "j"]. Or ["a", "c", "e", "i", "j"]. There can be many paths between two nodes.

If there are no repeated nodes, such path is called simple.
user
The text passage provides an introduction to graphs and graph theory, explaining the basic concepts and providing an example of how graphs can be implemented in Python. It does not contain any mathematical questions or answers.

TYPE: NO_QUESTION