Given the undirected graph in Figure 1, determine the BFS-tree and the values of the v.d attribute of every node v.
Given the undirected graph in Figure 1, determine the DFS-tree and the values of the v.d and v.f attributes of every node v.
Given the directed graph in Figure 2, classify its edges as tree edges, back edges, forward edges and cross edges according to a DFS search.
[Figure 2: just imagine any directed graph you like ;-) ]
Implement a generic priority first search (a single implementation, functioning as a "4-in-1"), where the priority can be defined in different ways such that the 4 particular algorithms (DFS, BFS, Prim, Dijkstra) result as particular cases of the priority-first search.
The word-stair game starts with 2 words, of equal length, and has to find the stairs to transform the first word into the second one. A stair is a transformation of a valid word, by changing one of its letters, into another valid word. All the valid words are given in a dictionary. Example: ball - bald - bold - cold
Write a program that repeatedly reads 2 words of equal length from the input and prints out their shortest word stair, if such a word stair exist. If the words are not of equal length, an error message is displayed. The dictionary is given as a text file of words.
Hint: Represent the dictionary as a graph. The words are nodes of the graph. An edge exists between 2 nodes if the words are of the same length and they differ by only one letter. This graph is a sparse graph, take this into account when choosing a graph representation. Use BFS to find a shortest path from the first word to the second word
Dictionary input file: A file containing words of the english dictionary is given in wordsEn.txt.
CLRS Problem [22.2-7]. There are 2 types of professional wrestlers: babyfaces and heels. Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n + r)-time algorithm that determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it.
Hint: Use a graph, where the wrestlers correspond to nodes and the rivalries to edges. The problem of building the 2 teams corresponds to determining whether the graph is bipartite, anf if it is, determine a coloring of its vertices using only 2 colors, such that no adjacent vertices are colored using the same color. Use can use any graph searching algorithm (DFS or BFS) to solve this: The first vertex is assigned to the first team. When discovering a new vertex, mark it as belonging to the opposite team as its parent vertex; when encountering a vertex which has been already discovered, test if it has been assigned the right team; if not, this means that it is not possible to build the 2 teams. Prove that this algorithm is correct !
[CLRS - 22.2-9] Let G=(V, E) be a connected, undirected graph. Give an O(V+E)-time algorithm to compute a path in G that traverses each edge in E exactly once in each direction. Describe how you can find your way out of a maze if you are given a large supply of pennies.
[CLRS - 22.3-13] A directed graph G=(V, E) is singly connected if G contains at most one simple path from u to v for all vertices u and v in V. Give an efficient algorithm to determine whether or not a directed graph is singly connected.