Graphs

Internal

• Data Structures
• Trees

Overview

Graphs are fundamental data structures in computer science. They map directly to a large number of problems that involve physical networks - such as the phone network or the internet, or logical networks about parallel relationships between objects in general - the order in which to execute interdependent tasks, or the analysis of social networks.

Graphs are backed by mathematical formalism. The Graph Concepts page provides a number of terms, concepts, notations and some mathematical tools that are useful when dealing with graphs. Graph Representation in Memory describes ways to represent graph nodes and edges in such a way that they can be efficiently manipulated by algorithms. The most common arrangements - adjacency lists and adjacency matrices - are discussed.

The most obvious problem that arises when dealing with graphs is to walk them. It includes searching the graph or finding paths through them, or more generically, exploring a graph to infer knowledge about it. The classical algorithms for graph exploration are breadth-first search (BFS) and depth-first search (DFS). Both these algorithms are very efficient, they are capable of exploring the graph in linear time of the number of vertices and edges O(n + m). They are described and discussed in the Graph Search page.

Building upon the basic graph search algorithms, we discuss several graph problems: computing the shortest path between two vertices using breadth-first search and then with Dijkstra's algorithm, vertex clustering heuristics involving finding connected components in an undirected graph with breadth-first search or finding strongly connected components in a directed graph with depth-first search, topological sort of a directed acyclic graph with depth-first search.

Graph cuts refer to graph partition into vertex subsets. The minimum cut problem is representative for this class of problems.

Graph Concepts

Graph Concepts

Graph Representation in Memory

Graph Representation in Memory

Graph Algorithms

• Graph Search
  • Shortest Path in a Graph with breadth-first search, Dijkstra's algorithm and more
  • Find Connected Components in an Undirected Graph with breadth-first search
  • Find Strongly Connected Components in a Directed Graph with Kosaraju's two-pass algorithm, based on depth-first search
  • Topological Sort of a Directed Acyclic Graph with depth-first search
  • Longest Path in a Graph
• The Minimum Cut Problem
• Minimum spanning tree algorithms: Prim's Algorithm, Kruskal's Algorithm

Organizatorium

• https://github.com/jwasham/coding-interview-university#graphs