Graphs: Difference between revisions
| (23 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Data_Structures#Dynamic_Sets|Data Structures]] | * [[Data_Structures#Dynamic_Sets|Data Structures]] | ||
* [[ | * [[Trees]] | ||
=Overview= | =Overview= | ||
| Line 11: | Line 11: | ||
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 [[Graph Search#BFS|breadth-first search (BFS)]] and [[Graph Search#DFS|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#Overview|Graph Search]] page. | 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 [[Graph Search#BFS|breadth-first search (BFS)]] and [[Graph Search#DFS|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#Overview|Graph Search]] page. | ||
Building upon the basic graph search algorithms, we discuss several graph problems: [[Shortest_Path_in_a_Graph#Overview|computing the shortest path between two vertices]] using breadth-first search, vertex clustering heuristics involving [[Find_Connected_Components_in_an_Undirected_Graph#Overview|finding connected components in an undirected graph]] with breadth-first search or [[Find_Strongly_Connected_Components_in_a_Directed_Graph#Overview|finding strongly connected components in a directed graph]] with depth-first search, [[Topological_Sort_of_a_Directed_Acyclic_Graph#Overview|topological sort of a directed acyclic graph]] with depth-first search. | Building upon the basic graph search algorithms, we discuss several graph problems: [[Shortest_Path_in_a_Graph#Overview|computing the shortest path between two vertices]] using breadth-first search and then with Dijkstra's algorithm, vertex clustering heuristics involving [[Find_Connected_Components_in_an_Undirected_Graph#Overview|finding connected components in an undirected graph]] with breadth-first search or [[Find_Strongly_Connected_Components_in_a_Directed_Graph#Overview|finding strongly connected components in a directed graph]] with depth-first search, [[Topological_Sort_of_a_Directed_Acyclic_Graph#Overview|topological sort of a directed acyclic graph]] with depth-first search. | ||
[[Graph_Cuts | [[Graph_Concepts#Graph_Cuts|Graph cuts]] refer to graph partition into vertex subsets. The [[The Minimum Cut Problem|minimum cut problem]] is representative for this class of problems. | ||
=Subjects= | =<span id='Subjects'></span>Graph Concepts= | ||
{{Internal|Graph_Concepts#Graph_Definition|Graph Concepts}} | |||
=Graph Representation in Memory= | |||
{{Internal|Graph Representation in Memory|Graph Representation in Memory}} | |||
=Graph Algorithms= | |||
* [[Graph Search]] | * [[Graph Search]] | ||
** [[Shortest Path in a Graph]] with breadth-first search | ** [[Shortest Path in a Graph]] with breadth-first search, Dijkstra's algorithm and more | ||
** [[Longest Path in a Graph]] | |||
** [[A Path in a Graph]] | |||
** [[Find Connected Components in an Undirected Graph]] with breadth-first search | ** [[Find Connected Components in an Undirected Graph]] with breadth-first search | ||
** [[Find Strongly Connected Components in a Directed Graph]] with depth-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 | ** [[Topological Sort of a Directed Acyclic Graph]] with depth-first search | ||
** [[ | * [[The Minimum Cut Problem]] | ||
* [[The Minimum Spanning Tree Problem|Minimum spanning tree algorithms]]: [[Prim's Algorithm]], [[Kruskal's Algorithm]] | |||
=Organizatorium= | |||
* https://github.com/jwasham/coding-interview-university#graphs | |||
Latest revision as of 01:36, 10 November 2021
Internal
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 Representation in Memory
Graph Algorithms
- Graph Search
- Shortest Path in a Graph with breadth-first search, Dijkstra's algorithm and more
- Longest Path in a Graph
- A Path in a Graph
- 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
- The Minimum Cut Problem
- Minimum spanning tree algorithms: Prim's Algorithm, Kruskal's Algorithm