Graphs: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 9: Line 9:
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 - [[Graph_Representation_in_Memory#Adjacency_Lists|adjacency lists]] and [[Graph_Representation_in_Memory#Adjacency_Matrices|adjacency matrices]] - are discussed.
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 - [[Graph_Representation_in_Memory#Adjacency_Lists|adjacency lists]] and [[Graph_Representation_in_Memory#Adjacency_Matrices|adjacency matrices]] - are discussed.


The most obvious problem that arises when dealing with graphs is to walk them: search the graph or find paths through graphs, or more generically, explore a graph and 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]] 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]] page.


Building upon the basic graph search algorithms, we discuss several useful graph problems: [[Shortest_Path_in_a_Graph|computing the shortest path between two vertices]] using breadth-first search, clustering heuristics by [[Find_Connected_Components_in_an_Undirected_Graph|finding connected components in an undirected graph]] with breadth-first search or [[Find_Strongly_Connected_Components_in_a_Directed_Graph|finding strongly connected components in a directed graph]] with depth-first search and the [[Topological_Sort_of_a_Directed_Acyclic_Graph|topological sort of a directed acyclic graph]] with depth-first search.
Building upon the basic graph search algorithms, we discuss several useful graph problems: [[Shortest_Path_in_a_Graph|computing the shortest path between two vertices]] using breadth-first search, clustering heuristics by [[Find_Connected_Components_in_an_Undirected_Graph|finding connected components in an undirected graph]] with breadth-first search or [[Find_Strongly_Connected_Components_in_a_Directed_Graph|finding strongly connected components in a directed graph]] with depth-first search and the [[Topological_Sort_of_a_Directed_Acyclic_Graph|topological sort of a directed acyclic graph]] with depth-first search.

Revision as of 00:10, 2 October 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 useful graph problems: computing the shortest path between two vertices using breadth-first search, clustering heuristics by finding connected components in an undirected graph with breadth-first search or finding strongly connected components in a directed graph with depth-first search and the 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.

Subjects

Retrieved from "https://kb.novaordis.com/index.php?title=Graphs&oldid=82730"