Graphs

Many problems in Computer Science and Mathematics can be reduced to a set of states and a set of transitions between these states. A graph is a mathematical representation of problems like these. In the last chapter we saw that trees serve a variety of purposes in Computer Science. Trees are graphs. However, graphs are more general than trees. Abstracting away the details of a problem and studying it in its simplest form often leads to new insight. As a result, many algorithms have come out of the research in graph theory. Graph theory was first studied by mathematicians. Many of the algorithms in graphGraph theory are named for the mathematician that developed or discovered them. Dijkstra and KruskalGraphkruskal’s algorithm are two such mathematicians and this chapter covers algorithmsGraphdijkstra’s algorithm developed by them.