Graphs: Difference between revisions
| Line 10: | Line 10: | ||
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: 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. | ||
Building upon the basic graph search algorithms, we discuss several useful graph problems: computing the shortest path between two vertices, finding connected components in an undirected graph, finding strongly connected components in a directed graph and the topological sort of a directed acyclic graph. | 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, finding connected components in an undirected graph, finding strongly connected components in a directed graph and the topological sort of a directed acyclic graph. | ||
=Subjects= | =Subjects= | ||
Revision as of 19:24, 1 October 2021
Internal
Overview
Graphs are fundamental structures in computer science. They apply 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 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 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: 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 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, finding connected components in an undirected graph, finding strongly connected components in a directed graph and the topological sort of a directed acyclic graph.
Subjects
- Graph Concepts
- Graph Representation in Memory
- Graph Search
- Shortest Path in a Graph with breadth-first search
- Find Connected Components in an Undirected Graph with breadth-first search
- Find Strongly Connected Components in an Directed Graph with depth-first search
- Topological Sort of a Directed Acyclic Graph with depth-first search