Graphs: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(16 intermediate revisions by the same user not shown)
Line 1: Line 1:
=External=
* Data Structures in JavaScript: Graphs https://betterprogramming.pub/basic-interview-data-structures-in-javascript-graphs-3f9118aeb078
=Internal=
=Internal=
* [[Data_Structures#Dynamic_Sets|Data Structures]]
* [[Data_Structures#Dynamic_Sets|Data Structures]]
Line 15: Line 13:
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.
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#Definition|Graph cuts]] refer to graph partition into vertex subsets. The [[Graph_Cuts#The_Minimum_Cut_Problem|minimum cut problem]] is representative for this class of problems.
[[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=
* [[Graph Concepts]]
{{Internal|Graph_Concepts#Graph_Definition|Graph Concepts}}
* [[Graph Representation in Memory]]
 
=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, Dijkstra's algorithm and more
** [[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 Kosaraju's two-pass algorithm, based on 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
* [[Graph_Cuts#The_Minimum_Cut_Problem|Minimum Cut Problem]]
* [[The Minimum Cut Problem]]
* [[The Minimum Spanning Tree Problem|Minimum spanning tree algorithms]]: [[Prim's Algorithm]], [[Kruskal's Algorithm]]


<br>
=Organizatorium=
<center>&#91;[[Graph_Concepts|Next]]]</center>
* 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 Concepts

Graph Representation in Memory

Graph Representation in Memory

Graph Algorithms

Organizatorium