Phase 3 Discussion Board
March 4, 2013
Task Type: Discussion Board Deliverable Length: 3 Parts: See Assignment Details
Points Possible: 75
Graphs and Trees
Task Background: Graphs and trees provide you with ways to visualize data sets, and the opportunity to do analysis on the data (e.g., shortest path). Knowing the structure of a database enables you to choose a proper algorithm for searching for data within a database.
Primary Task Response: Within the Discussion Board ...view middle of the document...
Clearly explain. (15 points)
My data can only be represented by a graph and not a tree because it has disjointed sets. A tree cannot have disjointed sets. This data can only be displayed in a graph. It is not possible to display it in a tree because it does not have one simple path and some nodes are not reachable or connected to each other.
Part II (35 points – distributed as follows)
The set of all possible sequences of moves in a chess game can be represented by a tree (decision tree). If you were to write a chess-playing computer program that can determine the best move at each step, would you use a depth-first or a breadth-first search for the best move at each step in the game? Why?
1) What is a graph? (5 points)
Graphs are generalizations of trees. They have nodes and edges like trees but they are basically more general than trees. A graph can have any number of edges and can be undirected or directed. In directed graphs you can only go node to node. Undirected graphs have no direction. You must follow the arrows in a directed graph but in a undirected graph you can go either way along an edge.
2) What is a Tree and how is a tree different from a graph – give at least 2 reasons? (5 points)
A tree is a undirected graph. It is connected with no cycles and is connected by any two vertices with one simple path. There are also directed trees which is a directed graph if the direction of the edges were not acknowledged. Trees have direction and do not contain cycles.Trees cannot have disjointed nodes like graphs either.
3) What is a Depth First Search of a tree? (5 points)
Depth First Search explores a path all the way to the edges before backtracking and exploring another path. It will process the vertices first deep and then widen. Afterwards it processes a vertex it recursively processes all of its descendants. The object of a Depth First Search is to search deeper into a graph wherever possible.
4) What is a Breadth First Search of a tree and how is it different from a Depth First Search? (5 points)
Breadth First Search is a search that explores the nodes nearest to the root before...