# data[].attributes.headline
Sincron, în clasă. Explicație, conversație, exercițiu.

# data[].attributes.subject
Sincron, în clasă. Explicație, conversație, exercițiu.

# data[].attributes.body
https://www.cs.usfca.edu/~galles/visualization/DFS.html

Se va folosi această unealtă de vizualizare pentru a explica elevilor principiul iar apoi pentru a verifica implementările proprii ale acestora și a îi ajuta să înțeleagă într-un mod vizual conceptele

# data[].attributes.body
Elevii sunt elemente ale unui ecosistem, folosind un ghem de sfoară sunt conectați între ei (de ex. pe baza relațiilor trofice).

Astfel se prezintă elementele de bază ce țin de grafuri (noduri, muchii, cicluri, drumuri, timpuri de grafuri). Elevii conștientizează legătura strânsă dintre elementele ecosistemului.

Se taie sfoara într-un loc/se elimită un elev (nod), se discută atât consecințele ecologice (asupra ecosistemului și la scară macro asupra economiei) dar și despre componente conexe într-un graf. Elevii defapt au reprezentat o piramidă trofică folosind grafuri.

Elevii sunt astfel implicați analitic, emotiv și kinestezic în activitate, vor înțelege mai bine lumea înconjurătoare și consecințele propriilor acțiuni.

# data[].attributes.headline
Self-paced learning, exersare independentă pe baza exemplelor date

# data[].attributes.subject
Self-paced learning, exersare independentă pe baza exemplelor date

# data[].attributes.body
https://www.programiz.com/dsa/graph-bfs

# data[].attributes.attachment_link.readable_text
Traversal means visiting all the nodes of a graph. Breadth First Traversal or Breadth First Search is a recursive algorithm for searching all the vertices of a graph or tree data structure.

BFS algorithm

A standard BFS implementation puts each vertex of the graph into one of two categories:

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The algorithm works as follows:

1. Start by putting any one of the graph's vertices at the back of a queue.

2. Take the front item of the queue and add it to the visited list.

3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the back of the queue.

4. Keep repeating steps 2 and 3 until the queue is empty.

The graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the BFS algorithm on every node

BFS example

Let's see how the Breadth First Search algorithm works with an example. We use an undirected graph with 5 vertices.

Undirected graph with 5 vertices

We start from vertex 0, the BFS algorithm starts by putting it in the Visited list and putting all its adjacent vertices in the stack.

Visit start vertex and add its adjacent vertices to queue

Next, we visit the element at the front of queue i.e. 1 and go to its adjacent nodes. Since 0 has already been visited, we visit 2 instead.

Visit the first neighbour of start node 0, which is 1

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the back of the queue and visit 3, which is at the front of the queue.

Visit 2 which was added to queue earlier to add its neighbours

4 remains in the queue

Only 4 remains in the queue since the only adjacent node of 3 i.e. 0 is already visited. We visit it.

Visit last remaining item in the queue to check if it has unvisited neighbors

Since the queue is empty, we have completed the Breadth First Traversal of the graph.

BFS pseudocode

create a queue Q
mark v as visited and put v into Q
while Q is non-empty
    remove the head u of Q
    mark and enqueue all (unvisited) neighbours of u

Python, Java and C/C++ Examples

The code for the Breadth First Search Algorithm with an example is shown below. The code has been simplified so that we can focus on the algorithm rather than other details.

# BFS algorithm in Python import collections # BFS algorithm def bfs(graph, root): visited, queue = set(), collections.deque([root]) visited.add(root) while queue: # Dequeue a vertex from queue vertex = queue.popleft() print(str(vertex) + " ", end="") # If not visited, mark it as visited, and # enqueue it for neighbour in graph[vertex]: if neighbour not in visited: visited.add(neighbour) queue.append(neighbour) if __name__ == '__main__': graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]} print("Following is Breadth First Traversal: ") bfs(graph, 0)

// BFS algorithm in Java import java.util.*; public class Graph { private int V; private LinkedList<Integer> adj[]; // Create a graph Graph(int v) { V = v; adj = new LinkedList[v]; for (int i = 0; i < v; ++i) adj[i] = new LinkedList(); } // Add edges to the graph void addEdge(int v, int w) { adj[v].add(w); } // BFS algorithm void BFS(int s) { boolean visited[] = new boolean[V]; LinkedList<Integer> queue = new LinkedList(); visited[s] = true; queue.add(s); while (queue.size() != 0) { s = queue.poll(); System.out.print(s + " "); Iterator<Integer> i = adj[s].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) { visited[n] = true; queue.add(n); } } } } public static void main(String args[]) { Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)"); g.BFS(2); } }

// BFS algorithm in C #include <stdio.h> #include <stdlib.h> #define SIZE 40 struct queue { int items[SIZE]; int front; int rear; }; struct queue* createQueue(); void enqueue(struct queue* q, int); int dequeue(struct queue* q); void display(struct queue* q); int isEmpty(struct queue* q); void printQueue(struct queue* q); struct node { int vertex; struct node* next; }; struct node* createNode(int); struct Graph { int numVertices; struct node** adjLists; int* visited; }; // BFS algorithm void bfs(struct Graph* graph, int startVertex) { struct queue* q = createQueue(); graph->visited[startVertex] = 1; enqueue(q, startVertex); while (!isEmpty(q)) { printQueue(q); int currentVertex = dequeue(q); printf("Visited %d\n", currentVertex); struct node* temp = graph->adjLists[currentVertex]; while (temp) { int adjVertex = temp->vertex; if (graph->visited[adjVertex] == 0) { graph->visited[adjVertex] = 1; enqueue(q, adjVertex); } temp = temp->next; } } } // Creating a node struct node* createNode(int v) { struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; } // Creating a graph struct Graph* createGraph(int vertices) { struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i < vertices; i++) { graph->adjLists[i] = NULL; graph->visited[i] = 0; } return graph; } // Add edge void addEdge(struct Graph* graph, int src, int dest) { // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists[dest]; graph->adjLists[dest] = newNode; } // Create a queue struct queue* createQueue() { struct queue* q = malloc(sizeof(struct queue)); q->front = -1; q->rear = -1; return q; } // Check if the queue is empty int isEmpty(struct queue* q) { if (q->rear == -1) return 1; else return 0; } // Adding elements into queue void enqueue(struct queue* q, int value) { if (q->rear == SIZE - 1) printf("\nQueue is Full!!"); else { if (q->front == -1) q->front = 0; q->rear++; q->items[q->rear] = value; } } // Removing elements from queue int dequeue(struct queue* q) { int item; if (isEmpty(q)) { printf("Queue is empty"); item = -1; } else { item = q->items[q->front]; q->front++; if (q->front > q->rear) { printf("Resetting queue "); q->front = q->rear = -1; } } return item; } // Print the queue void printQueue(struct queue* q) { int i = q->front; if (isEmpty(q)) { printf("Queue is empty"); } else { printf("\nQueue contains \n"); for (i = q->front; i < q->rear + 1; i++) { printf("%d ", q->items[i]); } } } int main() { struct Graph* graph = createGraph(6); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 1, 4); addEdge(graph, 1, 3); addEdge(graph, 2, 4); addEdge(graph, 3, 4); bfs(graph, 0); return 0; }

// BFS algorithm in C++ #include <iostream> #include <list> using namespace std; class Graph { int numVertices; list<int>* adjLists; bool* visited; public: Graph(int vertices); void addEdge(int src, int dest); void BFS(int startVertex); }; // Create a graph with given vertices, // and maintain an adjacency list Graph::Graph(int vertices) { numVertices = vertices; adjLists = new list<int>[vertices]; } // Add edges to the graph void Graph::addEdge(int src, int dest) { adjLists[src].push_back(dest); adjLists[dest].push_back(src); } // BFS algorithm void Graph::BFS(int startVertex) { visited = new bool[numVertices]; for (int i = 0; i < numVertices; i++) visited[i] = false; list<int> queue; visited[startVertex] = true; queue.push_back(startVertex); list<int>::iterator i; while (!queue.empty()) { int currVertex = queue.front(); cout << "Visited " << currVertex << " "; queue.pop_front(); for (i = adjLists[currVertex].begin(); i != adjLists[currVertex].end(); ++i) { int adjVertex = *i; if (!visited[adjVertex]) { visited[adjVertex] = true; queue.push_back(adjVertex); } } } } int main() { Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); g.BFS(2); return 0; }

BFS Algorithm Complexity

The time complexity of the BFS algorithm is represented in the form of O(V + E), where V is the number of nodes and E is the number of edges.

The space complexity of the algorithm is O(V).

BFS Algorithm Applications

1. To build index by search index

2. For GPS navigation

3. Path finding algorithms

4. In Ford-Fulkerson algorithm to find maximum flow in a network

5. Cycle detection in an undirected graph

6. In minimum spanning tree

# data[].attributes.attachment_link.title
BFS Graph Algorithm(With code in C, C++, Java and Python)

# data[].attributes.attachment_link.description
Breadth first traversal or Breadth first Search is a recursive algorithm for searching all the vertices of a graph or tree data structure. In this tutorial, you will understand the working of bfs algorithm with codes in C, C++, Java, and Python.

# data[].attributes.headline
Plurisdisciplinar fizică informatică - Legile lui Kirchhoff

# data[].attributes.subject
Plurisdisciplinar fizică informatică - Legile lui Kirchhoff

# data[].attributes.body
Introducere în concept din punctul de vedere al informaticii: https://www.tutorialspoint.com/network_theory/network_theory_topology.htm

Elevii vor folosi resursele prezentate în cadrul laboratorului de informatică, vor modela un circuit simplu, vor realiza un program C++ care calculează caracteristici de bază ale circuitului; în cadrul laboratorului de fizică vor realiza fizic un circuit simplu (de exemplu folosind un breadboard) care a fost modelat anterior pe calculator și vor măsura caracteristicile sale folosind un multimetru.

Elevii vor compara rezultatele obțiune practic cu cele anticipate folosind calculatorul.

# data[].attributes.attachment_link.description
3 resistors with single voltage supply -- Kirchhoff’s voltage law

# data[].attributes.headline
Interdisciplinar matematică-informatică. Cum au fost create grafurile?

# data[].attributes.subject
Interdisciplinar matematică-informatică. Cum au fost create grafurile?

# data[].attributes.attachment_link.title
How the Königsberg bridge problem changed mathematics - Dan Van der Vieren

# data[].attributes.headline
Învătare interactivă și prin reprezentare grafică, self-paced learning, asincron

# data[].attributes.subject
Învătare interactivă și prin reprezentare grafică, self-paced learning, asincron

# data[].attributes.attachment_link.readable_text
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines.

D3 Graph Theory is a project aimed at anyone who wants to learn graph theory. It provides quick and interactive introduction to the subject. The visuals used in the project makes it an effective learning tool.

And yes, it is an open-source project. Check the code at GitHub.

# data[].attributes.attachment_link.title
D3 Graph Theory - Interactive Graph Theory Tutorials

# data[].attributes.attachment_link.description
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines. D3 Graph Theory is a project aimed at anyone who wants to learn graph theory.

# data[].attributes.attachment_link.readable_text
A graph is a collection of two sets V and E where V is a finite non-empty set of vertices and E is a finite non-empty set of edges.

Vertices are nothing but the nodes in the graph.

Two adjacent vertices are joined by edges.

Any graph is denoted as G = {V, E}.

For Example:

A tree is a finite set of one or more nodes such that -

1. There is a specially designated node called root.

2. The remaining nodes are partitioned into n>=0 disjoint sets T₁, T₂, T₃, ..., Tn
where T₁, T₂, T₃, ..., Tn are called the subtrees of the root.

The concept of a tree is represented by following Fig.

Graph vs Tree

# data[].attributes.attachment_link.title
Difference between graph and tree - GeeksforGeeks

# data[].attributes.attachment_link.description
A graph is a collection of two sets V and E where V is a finite non-empty set of vertices and E is a finite non-empty set of edges. Vertices are nothing but the nodes in the graph. Two adjacent vertices are joined by edges. Any graph is denoted as G = {V, E}.

# data[].attributes.attachment_link.title
Basic Properties of a Graph - GeeksforGeeks

# data[].attributes.attachment_link.description
A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. Properties of Graphs are basically used for the characterization of graphs depending on their structures.

# data[].attributes.attachment_link.readable_text
A Graphis a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph can be defined as, A Graph consisting of a finite set of vertices(or nodes) and a set of edges that connect a pair of nodes.

Types of Graphs:

1. Finite Graphs

A graph is said to be finite if it has a finite number of vertices and a finite number of edges.

2. Infinite Graph:

A graph is said to be infinite if it has an infinite number of vertices as well as an infinite number of edges.

3. Trivial Graph:

A graph is said to be trivial if a finite graph contains only one vertex and no edge.

4. Simple Graph:

A simple graph is a graph that does not contain more than one edge between the pair of vertices. A simple railway track connecting different cities is an example of a simple graph.

5. Multi Graph:

Any graph which contains some parallel edges but doesn't contain any self-loop is called a multigraph. For example a Road Map.

Parallel Edges: If two vertices are connected with more than one edge then such edges are called parallel edges that are many routes but one destination.

Loop: An edge of a graph that starts from a vertex and ends at the same vertex is called a loop or a self-loop.

6. Null Graph:

A graph of order n and size zero is a graph where there are only isolated vertices with no edges connecting any pair of vertices.

7. Complete Graph:

A simple graph with n vertices is called a complete graph if the degree of each vertex is n-1, that is, one vertex is attached with n-1 edges or the rest of the vertices in the graph. A complete graph is also called Full Graph.

8. Pseudo Graph:

A graph G with a self-loop and some multiple edges is called a pseudo graph.

9. Regular Graph:

A simple graph is said to be regular if all vertices of graph G are of equal degree. All complete graphs are regular but vice versa is not possible.

10. Bipartite Graph:

A graph G = (V, E) is said to be a bipartite graph if its vertex set V(G) can be partitioned into two non-empty disjoint subsets. V1(G) and V2(G) in such a way that each edge e of E(G) has one end in V1(G) and another end in V2(G). The partition V1 U V2 = V is called Bipartite of G. Here in the figure: V1(G)={V5, V4, V3} and V2(G)={V1, V2}

11. Labeled Graph:

If the vertices and edges of a graph are labeled with name, date, or weight then it is called a labeled graph. It is also called Weighted Graph.

12. Digraph Graph:

A graph G = (V, E) with a mapping f such that every edge maps onto some ordered pair of vertices (Vi, Vj) are called a Digraph. It is also called Directed Graph. The ordered pair (Vi, Vj) means an edge between Vi and Vj with an arrow directed from Vi to Vj. Here in the figure: e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)

13. Subgraph:

A graph G1 = (V1, E1) is called a subgraph of a graph G(V, E) if V1(G) is a subset of V(G) and E1(G) is a subset of E(G) such that each edge of G1 has same end vertices as in G.

14. Connected or Disconnected Graph:

Graph G is said to be connected if any pair of vertices (Vi, Vj) of a graph G is reachable from one another. Or a graph is said to be connected if there exists at least one path between each and every pair of vertices in graph G, otherwise, it is disconnected. A null graph with n vertices is a disconnected graph consisting of n components. Each component consists of one vertex and no edge.

15. Cyclic Graph:

A graph G consisting of n vertices and n> = 3 that is V1, V2, V3- - - - Vn and edges (V1, V2), (V2, V3), (V3, V4)- - - - (Vn, V1) are called cyclic graph.

16. Types of Subgraphs:

Vertex disjoint subgraph: Any two graph G1 = (V1, E1) and G2 = (V2, E2) are said to be vertex disjoint of a graph G = (V, E) if V1(G1) intersection V2(G2) = null. In the figure, there is no common vertex between G1 and G2.

Edge disjoint subgraph: A subgraph is said to be edge-disjoint if E1(G1) intersection E2(G2) = null. In the figure, there is no common edge between G1 and G2.

Note: Edge disjoint subgraph may have vertices in common but a vertex disjoint graph cannot have a common edge, so the vertex disjoint subgraph will always be an edge-disjoint subgraph.
Related article: Applications, Advantages and Disadvantages of Graph

# data[].attributes.attachment_link.title
Types of Graphs with Examples - GeeksforGeeks

# data[].attributes.attachment_link.description
A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.

# data[].attributes.attachment_link.title
Practice | GeeksforGeeks | A computer science portal for geeks

# data[].attributes.attachment_link.description
Platform to practice programming problems. Solve company interview questions and improve your coding intellect

# data[].attributes.headline
Fundamentele Programarii Culegere de probleme pentru clasa a XI-a

# data[].attributes.subject
Fundamentele Programarii Culegere de probleme pentru clasa a XI-a

# data[].attributes.body
Dana Lica
ISBN: 9738803721

# data[].attributes.attachment_link.title
Grafuri Orientate - Teorie si Program C++ - Informatica - Clasa a 11-a

# data[].attributes.attachment_link.title
Grafuri Neorientate - Teorie si Program C++ - Informatica - Clasa a 11-a

# data[].attributes.attachment_link.title
Parcurgerea grafurilor (BFS si DFS) in C++ - Teoria Grafurilor

# data[].attributes.attachment_link.readable_text
Pe teritoriul insulelelor FalkLand exista n britanici notati de la 1 la n si m argentinieni notati de la 1 la m.

Se știe că fiecare britanic poate lega o singura relație de prietenie cu una dintre cunoștințele sale Argentiniene și vice-versa. Pentru a detensiona relațiile, cele două naționalități sunt obligate să se cunoască și să lege cât mai multe relații de prietenie.

Având în vedere faptul că fiecare britanic poate lega o singură relație de prietenie cu un argentinian, iar relatiie de prietenie se știu deoarece acestea sunt evidente, Margaret Thatcher va solicită ajutorul în aflarea numărului maxim de relații noi de prietenie care se vor lega pe insula .

# data[].attributes.attachment_link.description
Pe teritoriul insulelelor FalkLand exista n britanici notati de la 1 la n si m argentinieni notati de la 1 la m. Se știe că fiecare britanic poate lega o singura relație de prietenie cu una dintre cunoștințele sale Argentiniene și vice-versa.