YouTipGraph Structures | Tutorial
\\\\n\\\\nGraph Theory Structures
\\\\n\\\\nIn computer science, graphs are widely used to simulate social networks (users are nodes, friend relationships are edges), web links (webpages are nodes, hyperlinks are edges), communication networks, and even path planning problems.
\\\\n\\\\nGraphs are like a social network relationship map:
\\\\n\\\\n- \\\\n
- Nodes (Vertices): Every person in the social network \\\\n
- Edges: Relationships between people (friends, follows, etc.) \\\\n
- Weights: Strength of the relationship (intimacy, interaction frequency, etc.) \\\\n
Imagine the transportation network of your city: various locations (such as home, school, shopping mall) are points, and the roads connecting these locations are lines. A Graph is the mathematical abstraction of this point-and-line relationship; it is a data structure used to represent complex relationships between entities.
\\\\n\\\\nReal-life Examples:
\\\\n\\\\n- \\\\n
- Maps: Cities are nodes, roads are edges, distance is weight \\\\n
- Circuits: Components are nodes, wires are edges, resistance is weight \\\\n
- Internet: Websites are nodes, links are edges, traffic is weight \\\\n
- Transportation Networks: Stations are nodes, routes are edges, fare is weight \\\\n
| Scenario | \\\\nOther Structures | \\\\nGraph Structure | \\\\n
|---|---|---|
| Social Relationships | \\\\nDifficult to express complex relationships | \\\\nNaturally expresses many-to-many relationships | \\\\n
| Path Planning | \\\\nRequires complex data structures | \\\\nIntuitively represents networks and paths | \\\\n
| Dependency Relationships | \\\\nDifficult to represent cyclic dependencies | \\\\nEasily handles complex dependencies | \\\\n
| Network Analysis | \\\\nCannot express network topology | \\\\nPerfectly describes network structure | \\\\n
\\\\n\\\\n
Basic Terminology of Graphs
\\\\n\\\\n| Term | \\\\nDefinition | \\\\nReal-life Analogy | \\\\nSymbolic Representation | \\\\n
|---|---|---|---|
| Vertex | \\\\nThe basic unit in a graph | \\\\nA person in a social network | \\\\nV, u, v | \\\\n
| Edge | \\\\nA line connecting two vertices | \\\\nThe relationship between two people | \\\\nE, (u,v) | \\\\n
| Degree | \\\\nThe number of edges connected to a vertex | \\\\nThe number of friends a person has | \\\\ndeg(v) | \\\\n
| Path | \\\\nA sequence of vertices | \\\\nA route from A to B | \\\\nvββvβββ¦βvβ | \\\\n
| Cycle | \\\\nA path where the start and end points are the same | \\\\nLeaving home and eventually returning home | \\\\nvββvβββ¦βvβ | \\\\n
| Connected Graph | \\\\nThere is a path between any two points | \\\\nEveryone can contact each other | \\\\n\\\\n |
| Weight | \\\\nNumerical attribute of an edge | \\\\nDistance between two cities | \\\\nw(u,v) | \\\\n
Classification of Graphs
\\\\n\\\\n
\\\\n\\\\n| Classification Criteria | \\\\nType | \\\\nCharacteristics | \\\\nApplication Scenarios | \\\\n
|---|---|---|---|
| Directionality | \\\\nUndirected Graph | \\\\nEdges have no direction | \\\\nFriendship relationships, road networks | \\\\n
| \\\\n | Directed Graph | \\\\nEdges have direction | \\\\nFollow relationships, workflows | \\\\n
| Weight | \\\\nUnweighted Graph | \\\\nAll edges have the same weight | \\\\nSocial network relationships | \\\\n
| \\\\n | Weighted Graph | \\\\nEdges have different weights | \\\\nMap distances, network traffic | \\\\n
| Connectivity | \\\\nConnected Graph | \\\\nAny two points are reachable | \\\\nTransportation networks | \\\\n
| \\\\n | Disconnected Graph | \\\\nIsolated points exist | \\\\nSocial groups | \\\\n
| Cycle | \\\\nAcyclic Graph | \\\\nNo loops | \\\\nTask dependencies, family trees | \\\\n
| \\\\n | Cyclic Graph | \\\\nContains loops | \\\\nRoad networks | \\\\n
Representation Methods of Graphs
\\\\n\\\\nAdjacency Matrix
\\\\n\\\\n| Feature | \\\\nDescription | \\\\nTime Complexity | \\\\nSpace Complexity | \\\\n
|---|---|---|---|
| Storage Method | \\\\n2D Matrix | \\\\n\\\\n | \\\\n |
| Check Edge Existence | \\\\nmatrix != 0 | \\\\nO(1) | \\\\n\\\\n |
| Add Edge | \\\\nmatrix = weight | \\\\nO(1) | \\\\n\\\\n |
| Delete Edge | \\\\nmatrix = 0 | \\\\nO(1) | \\\\n\\\\n |
| Traverse Adjacent Points | \\\\nScan a row/column | \\\\nO(V) | \\\\n\\\\n |
| Space Usage | \\\\nVΓV Matrix | \\\\n\\\\n | O(VΒ²) | \\\\n
Adjacency List
\\\\n\\\\n| Feature | \\\\nDescription | \\\\nTime Complexity | \\\\nSpace Complexity | \\\\n
|---|---|---|---|
| Storage Method | \\\\nArray + Linked List | \\\\n\\\\n | \\\\n |
| Check Edge Existence | \\\\nSearch in linked list | \\\\nO(deg(v)) | \\\\n\\\\n |
| Add Edge | \\\\nAdd to linked list | \\\\nO(1) | \\\\n\\\\n |
| Delete Edge | \\\\nDelete from linked list | \\\\nO(deg(v)) | \\\\n\\\\n |
| Traverse Adjacent Points | \\\\nTraverse linked list | \\\\nO(deg(v)) | \\\\n\\\\n |
| Space Usage | \\\\nVertex Array + Edge Linked List | \\\\n\\\\n | O(V+E) | \\\\n
Basic Concepts of Graphs
\\\\n\\\\nA graph G consists of two sets:
- \\\\n
- Vertex Set V (Vertex Set): The set of all points in the graph. \\\\n
- Edge Set E (Edge Set): The set of lines connecting these points. An edge is represented by the two vertices
(u, v)it connects. \\\\n
Example
\\\\n\\\\n# A Simple Graph Example: Representing Social Network Friendships with Dictionary\\\\n\\\\n# Vertex: Alice, Bob, Charlie, Diana\\\\n\\\\n# EdgeοΌ represents the friend relationship between them\\\\n\\\\nsocial_graph ={\\\\n\\\\n'Alice': ['Bob','Charlie'],# Alice is Bob and Charlie friend\\\\n\\\\n'Bob': ['Alice','Charlie','Diana'],\\\\n\\\\n'Charlie': ['Alice','Bob'],\\\\n\\\\n'Diana': ['Bob']\\\\n\\\\n}\\\\n\\\\nprint(f"Vertex (User): {list(social_graph.keys())}")\\\\n\\\\nprint(f"Alice friend (Edge): {social_graph['Alice']}")\\\\nOutput:
\\\\n\\\\nVertex (User): ['Alice', 'Bob', 'Charlie', 'Diana']Alice friend (Edge): ['Bob', 'Charlie']
\\\\n\\\\n\\\\n\\\\n
Graph Classification and Important Concepts
\\\\n\\\\nGraphs can be divided into various types based on the characteristics of their edges. Understanding these is the foundation of mastering graph theory.
\\\\n\\\\nUndirected Graph vs Directed Graph
\\\\n\\\\n| Type | \\\\nCharacteristics of Edges (Edge) | \\\\nReal-life Analogy | \\\\nExample | \\\\n
|---|---|---|---|
| Undirected Graph | \\\\nEdges have no direction, (A, B) indicates A and B are mutually connected. | \\\\nMutual Friendship: If Alice is Bob's friend, then Bob must also be Alice's friend. | \\\\nFriendship relationships in social networks, connections in circuits. | \\\\n
| Directed Graph | \\\\nEdges have direction, A -> B indicates a one-way connection from A to B. | \\\\nWeibo Follow: You can follow someone, but they may not necessarily follow you back. | \\\\nWebpage hyperlinks, task dependencies, one-way streets. | \\\\n
\\\\n\\\\nWeighted Graph
\\\\n\\\\nIn a weighted graph, every edge is assigned a numerical value (weight), which can represent distance, cost, time, or relationship strength.
\\\\n\\\\nExample
\\\\n\\\\n# A Weighted Graph Representing Distances Between Cities (Adjacency List Form)\\\\n\\\\n weighted_graph ={\\\\n\\\\n'Beijing': {('Shanghai',1200),('Tianjin',100)},# BeijingtoShanghaidistance 1200, toTianjin distance 100\\\\n\\\\n'Shanghai': {('Beijing',1200),('Hangzhou',200)},\\\\n\\\\n'Tianjin': {('Beijing',100)},\\\\n\\\\n'Hangzhou': {('Shanghai',200)}\\\\n\\\\n}\\\\nKey Terms
\\\\n\\\\n- \\\\n
- Degree: The number of edges connected to a vertex. In directed graphs, it is divided into In-degree (number of edges pointing to the vertex) and Out-degree (number of edges pointing out from the vertex). \\\\n
- Path: A sequence of edges passed through from one vertex to another. e.g.,
A -> B -> C. \\\\n - Cycle: A path where the start and end points are the same vertex. \\\\n
- Connected Graph: In an undirected graph, there exists a path between any two vertices. \\\\n
- Strongly Connected Graph: In a directed graph, there exists a bidirectional path between any two vertices. \\\\n
\\\\n\\\\n
Storage Methods of Graphs
\\\\n\\\\nHow to represent a graph in a computer? There are mainly two mainstream methods.
\\\\n\\\\nAdjacency Matrix
\\\\n\\\\nUse a 2D array (matrix) matrix to represent the graph. The value of matrix represents the status of the edge from vertex i to vertex j.
- \\\\n
- For undirected graphs, the matrix is symmetric. \\\\n
- For weighted graphs, the matrix values store weights (use special values like
0orβto indicate no edge). \\\\n - Advantage: Checking if there is an edge between any two vertices is very fast (
O(1)). \\\\n - Disadvantage: Occupies large space (
O(V^2)), wasting space for "sparse graphs" with fewer edges. \\\\n
Example
\\\\n\\\\n# Representing an Undirected Graph Using Adjacency Matrix\\\\n\\\\n# Vertex: 0-A, 1-B, 2-C\\\\n\\\\n# EdgeοΌ A-B, A-C\\\\n\\\\nV =3# Number of Vertices\\\\n\\\\n adj_matrix =[ * V for _ in range(V)]\\\\n\\\\n# add Edge A-B (0-1)\\\\n\\\\n adj_matrix=1\\\\n\\\\n adj_matrix=1# Undirected Graph Requires Setting Symmetric Positions\\\\n\\\\n# add Edge A-C (0-2)\\\\n\\\\n adj_matrix=1\\\\n\\\\n adj_matrix=1\\\\n\\\\nprint("Adjacency Matrix:")\\\\n\\\\nfor row in adj_matrix:\\\\n\\\\nprint(row)\\\\n\\\\n# Output:\\\\n\\\\n# [0, 1, 1]\\\\n\\\\n# [1, 0, 0]\\\\n\\\\n# [1, 0, 0]\\\\nAdjacency List
\\\\n\\\\nMaintain a list (linked list, array, etc.) for each vertex, recording all vertices (and weights) directly connected to it.
\\\\n\\\\n- \\\\n
- Advantage: High space efficiency (
O(V + E)), especially suitable for sparse graphs. Can quickly find all neighbors of a vertex. \\\\n - Disadvantage: Slower to check if there is an edge between any two vertices (
O(degree(V))). \\\\n
Example
\\\\n\\\\n# Representing the Same Undirected Graph Using Adjacency List (Dictionary + List)\\\\n\\\\n adj_list ={\\\\n\\\\n'A': ['B','C'],# A connects B and C\\\\n\\\\n'B': ['A'],# B Connected to A\\\\n\\\\n'C': ['A']# C Connected to A\\\\n\\\\n}\\\\n\\\\nprint("Adjacency List:")\\\\n\\\\nfor vertex, neighbors in adj_list.items():\\\\n\\\\nprint(f"{vertex}: {neighbors}")\\\\n\\\\n\\\\n
Graph Traversal Algorithms
\\\\n\\\\nTraversal is the foundation of graph algorithms, meaning systematically visiting every vertex in the graph.
\\\\n\\\\nThere are mainly two strategies:
\\\\n\\\\nBreadth-First Search
\\\\n\\\\nBreadth-First Search (BFS) spreads like "water waves", starting from the origin, first visiting all direct neighbors, then neighbors' neighbors, and so on. It uses a Queue to implement.
\\\\n\\\\nAlgorithm Steps:
\\\\n\\\\n- \\\\n
- Add the starting point to the queue and mark it as visited. \\\\n
- While the queue is not empty:\\\\n<