Graph theory is one of the important field of mathematics which is closely related to computer science. Many of the real world problems which are difficult to visualize can be easily represented using graphs. Thus graphs are used extensively in computer science to represent communication networks, computational semantics and so on.
The famous PageRank algorithm of Google uses Graph theory, where each webpage is considered as a vertex of a graph and each vertex is weighted based on the number of quality links to that web page. Even though PageRank is not the only algorithm used by Google to rank webpages, it is the most popular one.
Another important area in Computer Science where Graph theory is used is Semantic networks. It is a part of NLP( Natural Language Processing) or Knowledge representation. A semantic network is a network which represents the semantic relationship between concepts, or in simple words, how different concepts are connected to each other. It uses vertices to represent concepts and the edges to represent relationships.
As complicated problems can be represented easily using graphs, formulating new algorithms for graphs is a major interest in computer science. There are several algorithms used to solve problems using graphs.
These are some of the important algorithms used in Graph theory.
- Bellman–Ford algorithm
- Dijkstra's algorithm
- Ford–Fulkerson algorithm
- Kruskal's algorithm
- Nearest neighbor algorithm
- Prim's algorithm
- Depth-first search
- Breadth-first search