nbangla

PSEUDOCODE ARTICULATION-POINTS-DFS-VISIT(G,u) dfn = dfn + 1 u.d = u.low = dfn u.color = GRAY for each v ∈ G.Adj[u] if v.color == WHITE v.π = u DFS-VISIT(G,v) if u.d == 1 if G.Adj[u].size >= 2 AND v.low > u.d articPointsList.push_front(u) else if v.low &gt= u.d articPointsList.push_front(u) u.low = min(u.low, v.low) else if u.π != v u.low = min(u.low, v.d) u.color = BLACK

Many algorithms that work with directed graphs begin with such a decomposition. After decomposing the graph into strongly connected components, such algorithms run separately on each one and then combine the solutions according to the structure of connections among components. ALGORITHM STRONGLY-CONNECTED-COMPONENTS(G) call DFS(G) to compute finishing times u.f for each vertex u compute GT call DFS(GT), but in the main loop of DFS, consider the verteces in order of decreasing u.f (as computed in line 2) output the vertices of each tree in the depth-first forest formed in line 4 as a separate strongly connected component

A topological sort of a dag G = (V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering. (If the graph contains a cycle, then no linear ordering is possible.) ALGORITHM TOPOLOGICAL-SORT(S) Find the indegree INDEG(N) of each node N of S. (This can be done by traversing each adjacency matrix.) Put in a queue all the nodes with zero indegree. Repeat Steps 5 and 6 until the queue is empty. Remove the front node N of the queue. Repeat the following for each neighbor M of the node N: (a) Set INDEG(M) := INDEG(M) - 1. [This deletes the edge from N to M.] (b) If INDEG(M) = 0, then: Add M to the rear of the queue. [End of loop.] [End of Step 3 loop.] Exit.

A topological sort of a dag G = (V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering. (If the graph contains a cycle, then no linear ordering is possible.) PSEUDOCODE TOPOLOGICAL-SORT(G) call DFS(G) to compute finishing times v.f for each vertex v as each vertex is finished, insert it onto the front of a linked list return the linked list of vertices

.:: PSEUDOCODE ::. DFS(G) for each vertex u ∈ G.V u.color = WHITE u.π = NIL time = 0 for each vertex u ∈ G.V if u.color == WHITE DFS-VISIT(G,u) DFS-VISIT(G,u) time = time + 1 u.d = time u.color = GRAY for each v ∈ G.Adj[u] if v.color == WHITE v.π = u DFS-VISIT(G,v) u.color = BLACK time = time + 1 u.f = time

Breadth-first search গ্রাফ অনুসন্ধানের জন্য একটি সহজ অ্যালগরিদম এবং অনেক গুরুত্বপূর্ণ গ্রাফ অ্যালগরিদমের জন্য এটি হচ্ছে মূল আদর্শ। Prim’s minimum-spanning tree অ্যালগরিদম এবং Dijkstra’s single-source shortest-paths অ্যালগরিদম Breadth-first search -এর আইডিয়াগুলি অনুসরন করে। .:: PSEUDOCODE ::. BFS(G,s) for each vertex u ∈ G.V - {s} u.color = WHITE u.d = ∞ u.π = NIL s.color = GRAY s.d = 0 s.π = NIL Q = ∅ ENQUEUE(Q,s) while Q ≠ ∅ u = DEQUEUE(Q) for each v ∈ G.Adj[u] if v.color == WHITE v.color = GRAY v.d = u.d + 1 v.π = u ENQUEUE(Q,v) u.color = BLACK