BFS Algorithm¶

First, we specify a vertex (called the root) and place it in group \(A_0\). Then we place all its neighbors in group \(A_1\). In \(A_2\), we place all neighbors of vertices in groups \(A_0\) and \(A_1\) that haven't been placed in any group yet. This process continues such that group \(A_i\) contains all vertices adjacent to vertices in groups \(A_j\) (where \(0 \leqslant j < i\)) that haven't been assigned to any group yet.

Let \(Dis_i\) denote the group number of vertex \(i\) (e.g., \(Dis_{root} = 0\)). Clearly, this method assigns all vertices in the connected component containing the root to groups. For simplicity, we assume the graph is connected, but all statements actually apply to the root's connected component.

First, we prove that for any two adjacent vertices \(i\) and \(j\), \(|Dis_{i} - Dis_{j}| \leqslant 1\).

Proof: By contradiction. Suppose there exist adjacent vertices \(i\) and \(j\) with \(Dis_{j} - Dis_{i} > 1\). Consider the moment we were filling group \(A_{Dis_{i}+1}\). At that time, \(j\) hadn't been placed in any group and was adjacent to \(i\), so it should have been placed in \(A_{Dis_{i}+1}\). This contradiction proves the theorem. Thus, we can confirm that group \(A_i\) contains all vertices adjacent to those in \(A_{i-1}\) that haven't been assigned yet.

def bfs(graph, start):  # BFS using a queue
    queue = [start]
    visited = set()
    visited.add(start)
    while queue:
        vertex = queue.pop(0)
        print(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

ماتریس همسایگی (Adjacency Matrix)¶

یک گراف کامل با ۴ رأس را در نظر بگیرید. ماتریس همسایگی این گراف به صورت زیر خواهد بود:

# raveshe aval: estefade az matrix hamishegi
adjacency_matrix = [
    [0, 1, 1, 0],  # ras 0
    [1, 0, 0, 1],  # ras 1
    [1, 0, 0, 1],  # ras 2
    [0, 1, 1, 0],  # ras 3
]

# تابع baraye chap matris
def print_matrix(matrix):
    for row in matrix:
        print(row)

نمایش ماتریس وقوع (Incidence Matrix)¶

برای گراف ساده بدون حلقه، ماتریس وقوع به این صورت تعریف میشود:

ماتریس نمونه برای گراف شکل بالا:

# matrise voghu: satr=ras ha, sotoon=yall ha
incidence_matrix = [
    [1, 1, 0, 0],  # yal 0
    [1, 0, 1, 0],  # yal 1
    [0, 1, 1, 0],  # yal 2
    [0, 0, 0, 1],  # yal 3
]

مزایا و معایب¶

• مزایای ماتریس همسایگی: - پیاده‌سازی آسان - بررسی وجود یال بین دو رأس در (O(1

• معایب ماتریس همسایگی: - مصرف حافظه (O(n² - ناکارآمد برای گراف‌های تُنُک (sparse)

Here is the translated text with the requested format preserved:

ویژگی‌های درخت‌ها¶

• هر دو رأس در درخت با دقیقاً یک مسیر ساده به هم وصل می‌شوند.

• اگر یالی از درخت حذف شود، ناهمبند می‌شود.

• تعداد یال‌ها همیشه یک واحد کمتر از تعداد رأس‌هاست: |E| = |V| - 1

# درخت رو ساخته و یال‌ها رو اضافه می‌کنیم
tree = Graph()
tree.add_edge('A', 'B')  # درخت ریشه‌دار با ریشه A
tree.add_edge('A', 'C')
tree.add_edge('B', 'D')
tree.add_edge('B', 'E')

درخت پوشا¶

یک درخت پوشا زیرگرافی است که تمام رأس‌های گراف اصلی را می‌پوشاند و خود یک درخت است. الگوریتم‌های معروف برای یافتن درخت پوشا شامل پریم و کروسکال می‌شوند.

In graph theory, a tree is a connected graph without cycles. Trees model hierarchical structures and are used in numerous algorithms.

Properties of Trees¶

• Every pair of vertices in a tree is connected by exactly one simple path.

• If any edge is removed, the tree becomes disconnected.

• The number of edges is always one less than the number of vertices: |E| = |V| - 1

# Build the tree and add edges
tree = Graph()
tree.add_edge('A', 'B')  # Rooted tree with root A
tree.add_edge('A', 'C')
tree.add_edge('B', 'D')
tree.add_edge('B', 'E')

Spanning Tree¶

A spanning tree is a subgraph that covers all vertices of the original graph and is itself a tree. Well-known algorithms for finding spanning trees include Prim's and Kruskal's.

Here is the translated RST content with code blocks and images preserved, and only Persian text translated:

Adjacency List Representation¶

1# Directed graph representation
2digraph = {
3    'A': ['B', 'C'],  # Outgoing edges from A
4    'B': ['C'],       # Outgoing edges from B
5    'C': ['A']        # Outgoing edges from C
6}

Matrix Representation¶

For a directed graph with \(n\) vertices, the adjacency matrix is an \(n \times n\) matrix where:

Example matrix:

A  B  C

A [0, 1, 1] B [0, 0, 1] C [1, 0, 0]

Graph Properties¶

• Out-degree: Number of outgoing edges from a vertex

• In-degree: Number of incoming edges to a vertex

• Path: Sequence of vertices where consecutive vertices are connected by directed edges

def in_degree(graph, node):
    count = 0
    for key in graph:  # Iterate over all vertices
        if node in graph[key]:  # Check if node is in neighbors
            count += 1
    return count

A directed graph is strongly connected if there's a path from every vertex to every other vertex.

Algorithm Steps: 1. Perform DFS from arbitrary vertex 2. Reverse all edge directions 3. Perform DFS again from same vertex 4. If both visits reach all vertices → graph is strongly connected

All code blocks and image references remain unchanged from original. Only Persian text has been translated while preserving: - Original RST structure and formatting - Code indentation and whitespace - Mathematical notation - Image directives - Code comments (only Finglish comments were translated)

Adjacency List Representation¶

In the adjacency list representation, each vertex has a list of adjacent vertices. For undirected graphs, each edge is represented twice: once in each vertex's list.

1class Graph:
2    def __init__(self, num_vertices):
3        self.num_vertices = num_vertices
4        self.adj_list = [[] for _ in range(num_vertices)]  # Create adjacency lists
5
6    def add_edge(self, u, v):
7        # Add edge between u and v (undirected)
8        self.adj_list[u].append(v)  # Add v to u's list
9        self.adj_list[v].append(u)  # Add u to v's list

Note: In the code above, line 8 and line 9 add the edge in both directions to maintain the undirected property.

Edge List Representation¶

In the edge list representation, all edges are stored as a list of pairs. For undirected graphs, each edge is typically stored once, but algorithms must treat (u, v) and (v, u) as equivalent.

1edges = [
2    (0, 1),  # Edge between 0 and 1
3    (0, 2),  # Edge between 0 and 2
4    (1, 3),  # Edge between 1 and 3
5    (2, 3)   # Edge between 2 and 3
6]

Important: When using edge lists, ensure your algorithm handles unordered pairs correctly, as the order of u and v does not matter in undirected graphs.

Connected Components¶

A connected component in an undirected graph is a subgraph where every pair of vertices is connected via a path. Disconnected graphs consist of multiple connected components.

Application: Identifying connected components helps in solving problems like network segmentation or friend group detection in social networks.

Here is the translated text with preserved RST formatting and unchanged code/images:

There are three common methods to represent graphs in computer memory:

1. Adjacency Matrix

2. Adjacency List

3. Edge List

Each method has advantages and disadvantages depending on the problem context.

Adjacency Matrix¶

In this method, we use a two-dimensional array (matrix) where the rows and columns represent graph vertices. If vertex i is connected to vertex j, we place the number 1 (or edge weight in weighted graphs) at position [i][j].

Example code for creating an adjacency matrix:

int main() {
    int n = 5;  // number of vertices
    int adjMatrix[n][n]; // adjacency matrix

    // Initialize with 0
    for(int i=0; i<n; i++) {  // loop through rows
        for(int j=0; j<n; j++) {  // loop through columns
            adjMatrix[i][j] = 0;
        }
    }

    // Adding edges
    adjMatrix[0][1] = 1;  // edge from 0 to 1
    adjMatrix[1][0] = 1;  // edge from 1 to 0
    adjMatrix[1][2] = 1;  // edge from 1 to 2
    return 0;
}

Advantages: - Simple implementation - Edge existence check in O(1) - Suitable for dense graphs

Disadvantages: - Memory usage of O(n²) - Inefficient for sparse graphs

Adjacency List¶

In this method, we use an array of linked lists where each array index represents a vertex, and its linked list contains adjacent vertices.

ماتریس مجاورت (Adjacency Matrix)¶

ساده‌ترین روش نمایش گراف با استفاده از یک ماتریس دو بعدی است که در آن سطرها و ستون‌ها نشان‌دهنده رأس‌ها هستند.

public class Graph
{
    private int[,] adjacencyMatrix; // ماتریس مجاورت
    private int numVertices; // تعداد رأس‌ها

    public Graph(int numVertices)
    {
        this.numVertices = numVertices;
        adjacencyMatrix = new int[numVertices, numVertices];
    }

    // اضافه کردن یال بین رأس i و j
    public void AddEdge(int i, int j)
    {
        adjacencyMatrix[i, j] = 1;
        adjacencyMatrix[j, i] = 1; // برای گراف نا‌جهت‌دار
    }
}

لیست مجاورت (Adjacency List)¶

در این روش برای هر رأس، لیستی از همسایه‌هایش ذخیره می‌شود. این روش برای گراف‌های پراکنده کارآمدتر است.

public class Graph
{
    private LinkedList<int>[] adjacencyList; // لیست مجاورت

    public Graph(int numVertices)
    {
        adjacencyList = new LinkedList<int>[numVertices];
        for (int i = 0; i < numVertices; i++)
        {
            adjacencyList[i] = new LinkedList<int>();
        }
    }

    public void AddEdge(int src, int dest)
    {
        adjacencyList[src].AddLast(dest);
        // برای گراف جهت‌دار فقط یک خط کافی است
    }
}

جدول یال‌ها (Edge List)¶

این روش تمام یال‌های گراف را به صورت لیستی از جفت رأس‌ها ذخیره می‌کند. مناسب برای الگوریتم‌هایی مانند Kruskal که نیاز به دسترسی به تمام یال‌ها دارند.

public struct Edge
{
    public int Source; // رأس مبدأ
    public int Destination; // رأس مقصد
    public int Weight; // وزن یال (برای گراف وزن‌دار)
}

public class Graph
{
    public List<Edge> Edges = new List<Edge>();
}

مقایسه پیچیدگی زمانی¶

Example Code¶

The following C++ code implements DFS using recursion:

Input: The graph and a starting node Output: A list of nodes in the order traversed

Notes:

• The graph is represented using an adjacency list (adj).

• The visited array tracks visited nodes.

• The order of traversal depends on the order of neighbors in the adjacency list.

Iterative Implementation Using a Stack¶

Important Observations:

• The iterative version uses an explicit stack instead of recursion.

• Neighbors are pushed in reverse order to simulate the same traversal order as the recursive version.

تحلیل پیچیدگی:¶

• زمانی: \(O(|V| + |E|)\) - در بدترین حالت تمام رأسها و یالها بررسی میشوند

• فضا: \(O(|V|)\) - به دلیل استفاده از پشته و لیست دیدهشدهها

Representation of Directed Graphs¶

Directed graphs can be represented using adjacency matrices or adjacency lists, similar to undirected graphs, but with attention to direction.

Example: Adjacency list representation of a directed graph:

1class Graph:
2    def __init__(self, vertices):
3        # Get the vertices
4        self.V = vertices
5        self.graph = []
6
7    # Add an edge
8    def add_edge(self, u, v, w):
9        self.graph.append([u, v, w])

Example: Creating a directed graph and adding edges to it:

g = Graph(4)
g.add_edge(0, 1, 5)
g.add_edge(1, 2, 3)
g.add_edge(2, 3, 7)
g.add_edge(3, 0, 2)

Applications of Directed Graphs¶

• Network routing: Modeling data paths in communication networks.

• Dependency resolution: Such as task scheduling or package dependencies.

• Social networks: Modeling follower-followee relationships.

مراحل اجرای الگوریتم¶

1. رأس شروع رو علامت بزن به عنوان دیده شده.

2. تمام رأسهای مجاور که دیده نشدن رو به صورت بازگشتی بررسی کن.

3. این پروسه رو تا پیمایش کامل همه رئوس تکرار کن.

مثال پیاده‌سازی در پایتون:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # چاپ رأس فعلی
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
# ravesh e DFS
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
dfs(graph, 'A')

خروجی الگوریتم:

A
B
D
E
F
C

ویژگی‌های الگوریتم DFS¶

• پیچیدگی زمانی: \(O(V + E)\) تو حالت کلی

• حافظه مصرفی: \(O(V)\) به خاطر ذخیره رأسهای بازدید شده

• کاربردها: تشخیص اجزای همبندی، حل مازها، تحلیل وابستگی

مقایسه با BFS¶

Here's the translated RST section with Persian text translated to English, code/images preserved, and Finglish comments translated:

 1def is_bipartite(graph):
 2    # Check if graph is bipartite using BFS
 3    color = {}
 4    for node in graph:
 5        if node not in color:
 6            queue = [node]
 7            color[node] = 0
 8            while queue:
 9                current = queue.pop(0)
10                for neighbor in graph[current]:
11                    if neighbor not in color:
12                        color[neighbor] = color[current] ^ 1
13                        queue.append(neighbor)
14                    elif color[neighbor] == color[current]:
15                        return False
16    return True

Properties of Bipartite Graphs¶

1. A graph is bipartite if and only if it contains no odd-length cycles

2. All trees are bipartite

3. The adjacency matrix of a bipartite graph has a specific block structure

Complete Bipartite Graphs¶

A complete bipartite graph \(K_{m,n}\) is a bipartite graph where: - Partition \(A\) has \(m\) vertices - Partition \(B\) has \(n\) vertices - Every vertex in \(A\) is connected to all vertices in \(B\)

1def complete_bipartite(m, n):
2    # Generate complete bipartite graph K_{m,n}
3    return {
4        **{i: [m+j for j in range(n)] for i in range(m)},
5        **{m+j: [i for i in range(m)] for j in range(n)}
6    }

Applications¶

Bipartite graphs are used in: - Matching problems (e.g., job assignments) - Recommendation systems - Network flow modeling - Biological interaction networks

Preserved code formatting, image references, mathematical notation, and RST structure while translating: - Maintained Python code indentation and line numbers - Kept mathematical expressions in LaTeX format - Preserved image directive syntax - Translated Finglish comments in code blocks - Maintained RST headers and formatting symbols

Rooted Tree¶

A rooted tree is a tree in which one vertex is designated as the root. In rooted trees, vertices can have parent-child relationships. Each vertex (except the root) has exactly one parent, and the root has no parent.

Properties of rooted trees:

• The path from root to any node is unique

• Number of edges = Number of vertices - 1

• Height of tree = Length of longest path from root to leaf

A binary tree is a rooted tree where each node has at most two children, called left child and right child.

1class Node:
2    def __init__(self, value):
3        self.value = value
4        self.left = None   # farzand-e chap
5        self.right = None  # farzand-e rast

Traversal Algorithms¶

Common tree traversal methods:

1. Pre-order (Parent → Left → Right)

2. In-order (Left → Parent → Right)

3. Post-order (Left → Right → Parent)

1def pre_order(node):
2    if node:
3        print(node.value)  # chap-e parent
4        pre_order(node.left)
5        pre_order(node.right)

Spanning Tree¶

A spanning tree of a connected graph G is a subgraph that includes all vertices of G and is a tree. Minimum spanning trees have important applications in network design.

Kruskal's algorithm implementation:

 1def kruskal(graph):
 2    parent = {node: node for node in graph.nodes}  # zakhireye pedar
 3    mst = []
 4
 5    # Edges should be sorted by weight
 6    for edge in sorted(graph.edges, key=lambda x: x.weight):
 7        u_root = find(parent, edge.u)
 8        v_root = find(parent, edge.v)
 9        if u_root != v_root:
10            mst.append(edge)
11            parent[v_root] = u_root  # ettehad-e do derakht
12    return mst

In this section, we examine an algorithm to detect the existence of a cycle in an undirected graph. The main idea is to perform a Depth-First Search (DFS) traversal and check if there is a back edge during the traversal.

Algorithm Steps:

1. For each unvisited vertex u: a. Mark u as visited. b. For every adjacent vertex v of u:

   • If v is not visited:

     • Set u as the parent of v.

     • Recursively check for cycles starting from v.

   • Else if v is visited and is not the parent of u:

     • A cycle exists in the graph.

2. If no such back edge is found after traversing all vertices, the graph is acyclic.

def has_cycle(G):
    marked = {u: False for u in G.vertices()}  # Initialize all vertices as unvisited
    parent = {u: None for u in G.vertices()}   # Track parent of each vertex

    for u in G.vertices():  # Iterate over all vertices
        if not marked[u]:   # Check unvisited vertices
            if dfs_cycle(G, u, marked, parent):
                return True
    return False

def dfs_cycle(G, u, marked, parent):
    marked[u] = True  # Mark current vertex as visited

    for v in G.neighbors(u):  # Visit all adjacent vertices
        if not marked[v]:     # If adjacent vertex is unvisited
            parent[v] = u     # Set parent
            if dfs_cycle(G, v, marked, parent):
                return True
        elif parent[u] != v:  # If visited and not parent, cycle exists
            return True

    return False  # No cycle found in this component

Important Notes:

• This algorithm only works for undirected graphs. For directed graphs, the approach differs due to edge directionality.

• Time complexity is \(O(|V| + |E|)\), same as standard DFS.

الگوریتم جستجوی عمق اول (DFS)¶

در مقابل BFS، الگوریتم DFS از ساختار پشته (Stack) استفاده میکند. پیاده‌سازی بازگشتی DFS:

# Bakhsh khanee graph
def dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(reversed(graph[vertex]))
    return visited

فرمول زیر زمان اجرای BFS را نشان میدهد:

1

در صورت وجود وزن منفی، الگوریتم‌های دیگری مانند Bellman-Ford پیشنهاد میشود.

در این بخش، روشهای مختلف نمایش گرافها در حافظه کامپیوتر را بررسی میکنیم. انتخاب ساختار داده مناسب بستگی به نوع گراف و عملیات مورد نیاز دارد.

BFS Tree¶

Consider when the BFS algorithm finishes (i.e., when each vertex is assigned to its group). For vertex i, we arbitrarily choose a neighbor j such that \(Dis_i = Dis_j + 1\) and set \(par_i\) to j (note that par is undefined for the root and is defined for all other vertices). We then keep the edge between i and \(par_i\) for every vertex except the root and remove all other edges. The remaining graph has n-1 edges, and every vertex has a path to the root (why?). Thus, the new graph is connected and therefore a tree.

In fact, the BFS tree can be considered a spanning subtree of the graph rooted at the root and has the following properties:

• For every vertex i, \(dis(root, i) = h_i\) (where \(h_i\) is the height of vertex i when the tree is rooted at *root`).

• For every edge in the original graph, the height difference between its two endpoints is at most one.

Beyond its applications in programming (which may be useful in problem-solving), the BFS tree can also illuminate solutions to theoretical problems, as demonstrated in the following two examples.

BFS (جستجوی سطحی)¶

BFS (Breadth-First Search) یک الگوریتم پیمایش گراف است که برای جستجوی سطحی از یک گراف یا درخت استفاده میشود. این الگوریتم از یک ریشه شروع شده و تمام گرههای همسایه را قبل از رفتن به لایههای عمیقتر بررسی میکند.

مراحل الگوریتم BFS:

1. BFS از یک ریشه شروع میشود.

2. ریشه به صف اضافه میشود و به عنوان گره بازدیدشده علامتگذاری میشود.

3. تا زمانی که صف خالی نباشد:

   1. گره ابتدای صف خارج میشود.

   2. تمام همسایههای بازدیدنشده این گره به صف اضافه و علامتگذاری میشوند.

مثال کد برای BFS:

# BFS method
def bfs(graph, root):
    visited, q = set(), Queue()
    q.enqueue(root)
    while not q.is_empty():
        vertex = q.dequeue()
        print(vertex)
        for v in graph[vertex]:
            if v not in visited:
                visited.add(v)
                q.enqueue(v)

DFS (جستجوی عمقی)¶

DFS (Depth-First Search) یک الگوریتم پیمایش گراف است که برای جستجوی عمقی از یک گراف یا درخت استفاده میشود. این الگوریتم از یک ریشه شروع شده و تا انتهای یک شاخه پیش میرود و سپس بازگشت انجام میدهد.

مراحل الگوریتم DFS:

1. DFS از یک ریشه شروع میشود.

2. ریشه به عنوان بازدیدشده علامتگذاری میشود.

3. برای هر همسایه بازدیدنشده ریشه، به صورت بازگشتی DFS فراخوانی میشود.

مثال کد برای DFS:

# DFS method
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for v in graph[start]:
        if v not in visited:
            dfs(graph, v, visited)

مقایسه BFS و DFS¶

Representation Using Adjacency Matrix¶

In this method, the graph is represented using an adjacency matrix.

# Representing adjacency matrix
adjacency_matrix = [
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0]
]

Types of Graphs¶

• Undirected Graph: Edges have no direction. The relationship is mutual.

• Directed Graph (Digraph): Edges have direction. The relationship is one-way.

• Weighted Graph: Edges have numerical weights.

• Cyclic Graph: Contains at least one cycle.

• Acyclic Graph: Contains no cycles.

Adjacency Matrix¶

A 2D array where matrix[i][j] = 1 indicates an edge between node i and node j.

# Sample adjacency matrix
adj_matrix = [
    [0, 1, 1],
    [1, 0, 0],  # This comment gets translated
    [1, 0, 0]
]

Adjacency List¶

A collection of lists where each list describes neighbors of a vertex.

# Creating the graph
graph = {
    'A': ['B', 'C'],  # Node A connected to B and C
    'B': ['A'],       # Node B connected to A
    'C': ['A']        # Node C connected to A
}

Breadth-First Search (BFS)¶

Explores neighbor nodes level by level using a queue.

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            print(vertex)
            visited.add(vertex)
            queue.extend(graph[vertex])

Depth-First Search (DFS)¶

Explores as far as possible along each branch before backtracking.

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

Dijkstra's Algorithm¶

Finds shortest paths between nodes in a weighted graph.

I've preserved: 1. All RST formatting (headers, directives, indentation) 2. Code blocks and whitespace 3. Image references 4. Technical terminology 5. Code comments were only translated where they contained Finglish/Persian text

# method to calculate the largest component by member count
G = nx.Graph()
# here we sort connected components by member count in descending order
components = sorted(nx.connected_components(G), key=len, reverse=True)
# largest component
largest_component = components[0]

 1// BFS code
 2#include<bits/stdc++.h>
 3using namespace std;
 4const int maxn=100;
 5int dis[maxn];
 6int mark[maxn];
 7vector<int> adj[maxn];
 8int n , m;
 9
10void bfs(int v){
11    queue<int> q;
12    q.push(v);
13    mark[v]=1;
14    dis[v]=0;
15    while(q.size() !=0 ){
16        v=q.front();
17        q.pop();
18        for(int u=0;u<adj[v].size();u++){
19            int temp=adj[v][u];
20            if(mark[temp]==0){
21                mark[temp]=1;
22                dis[temp]=dis[v]+1;
23                q.push(temp);
24            }
25        }
26    }
27}
28
29int main(){
30    cin >> n >> m;
31    for(int i=0;i<m;i++){
32        int u , v;
33        cin >> u >> v;
34        adj[u].push_back(v);
35        adj[v].push_back(u);
36    }
37    bfs(1);
38    for(int i=1;i<=n;i++)
39        cout<<dis[i]<<" ";
40}

BFS Code¶

Input format: First two numbers n and m are given, representing the number of vertices and edges in the graph respectively. Then in the next m lines, two numbers i and j are given indicating an edge between i and j.

Output: Print n numbers where the i-th number equals \(dis(1,i)\) (the shortest path distance from vertex 1 to vertex i). The graph is guaranteed to be connected, ensuring all distances are finite.

Solution:

We use a queue (FIFO data structure) in this implementation. Key queue operations used:

• \(queue<int>q\)

• \(q.size()\) returns the number of elements in the queue

• \(q.front()\) returns the front element of the queue

• \(q.pop()\) removes the front element from the queue

• \(q.push(x)\) adds x to the end of the queue

• The queue essentially manages our "group B" of nodes to process.

Additional components: - Mark array: Initialized to 0 for all vertices. Set to 1 when a vertex enters the queue. - Dis array: Stores the calculated distance for each vertex.

const int maxn = 1e5 + 10;// hadeaksar meghdare n
int n, m;// tedad ras ha va tedad yal ha
int Dis[maxn];//javab har ras
bool Mark[maxn];//neshan midahad aya yek ras tabehal varede queue shode ya na
queue <int> q;// toozihe un neveshte shode
vector<int> adj[maxn] ;//list hamsaye haye har ras dar un neveshte shode

void bfs(int root){//fasele harki az root bedast khahad amad
    Dis[root] = 0; // dis(root , root) = 0
    Mark[root] = 1;
    q.push(root);
    while(q.size()){//ta zamani ke dakhele q ras hast while ra edame bede
        int u = q.front();//rasi dar q ke kamtarin Dis ra darad
        q.pop(); //hazfe un
        for(int i = 0; i < adj[u].size(); i++){//hamsaye haye i ra negah mikonim va agar ta be hal vared q nashodan vared mikonim
            int v = adj[u][i];
              if(!Mark[v]){
                  Mark[v] = 1;
                  Dis[v] = Dis[u] + 1;
                  q.push(v);
              }
        }
    }
}

int main(){
    cin >> n >> m ;
    for(int i = 1; i <= m; i++){//list hamsaye haye ras ha ra por mikonim
        int u, v;
        cin >> u >> v ;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs(1);//yani be ezaye root = 1 tabe bfs ra seda bezan
    for(int i = 1; i <= n; i++)//chupe khrooji
       cout << Dis[i] << ' ';
}

Conclusion¶

In this section, we introduced the BFS algorithm and its properties. Some of the most important applications of BFS include:

• Finding the distance of each vertex from a specific vertex

• Identifying vertices within the connected component of a specific vertex (and consequently determining whether the graph is connected or not)

• Traversing the graph for specific purposes

• Using the concept of BFS and BFS trees in solving theoretical problems

It is highly recommended to attempt the exercises in this section to deepen your understanding of the topic.