Grade 11 · 10 algorithmsCitește în română

Undirected graphsGrafuri neorientate

Every undirected graphs algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

10algorithms
7chapters
1grade

Undirected graphs

Grafuri neorientate · 10 algorithms

Connected componentsComponentele conexeA graph is connected if there is a path between any two nodes. A connected component is a maximal connected 'piece' of the graph. We take the nodes…O(n²)
Detecting a cycleDetectarea unui cicluA cycle is a simple path whose first node is also its last. We run a DFS traversal and keep for every node its parent (the node we came from). If…O(n²)
Shortest path between two nodes (BFS)Lanțul de lungime minimă între două noduri (BFS)The length of a path is its number of edges. Breadth-first search started from x discovers the nodes in order of their distance from x, so the first…O(n²)
Checking a bipartite graphVerificarea unui graf bipartitA graph is bipartite if its nodes can be split into two sets A and B so that every edge has one end in A and the other in B. We color the nodes with…O(n²)
Adjacency listsListele de adiacențăFor every node we store only the list of its neighbours. The edge [x, y] is added twice: y to the list of x and x to the list of y. The memory used…O(log n)
Adjacency matrix and node degreesMatricea de adiacență și gradele nodurilorAn undirected graph with n nodes and m edges can be stored in a matrix a with n rows and n columns: a[i][j] = 1 if the edge [i, j] exists, otherwise…O(n²)
Isolated nodes and the complete graphNoduri izolate și graful completAn isolated node has degree 0. A graph is complete if any two distinct nodes are joined by an edge; the complete graph with n nodes has n · (n - 1)…O(n)
Depth-first search (DFS)Parcurgerea în adâncime (DFS)Depth-first search goes as far as it can: from the current node it moves to the first unvisited neighbour, from there to that node's first unvisited…O(n²)
Breadth-first search (BFS)Parcurgerea în lățime (BFS)Breadth-first search visits the nodes 'in layers': first the start node, then all its neighbours, then the neighbours' neighbours, and so on. We use…O(n²)
Checking a path (chain)Verificarea unui lanțA sequence of nodes x1, x2, ..., xk is a path if any two consecutive nodes are joined by an edge; the length of the path is k - 1 (the number of…O(n²)