Graph Algorithms

4 Key excerpts on "Graph Algorithms"

• 

  eBook - ePub

  Principles of Computational Cell Biology

  From Protein Complexes to Cellular Networks

  • Volkhard Helms(Author)
  • 2018(Publication Date)
  • Wiley-VCH

    (Publisher)

  Search and enumeration. Many problems (such as a chess game) can be tackled by constructing a corresponding search problem on a mathematical graph. Algorithms to explore graphs define rules how the graph may be searched.

  Probabilistic and heuristic algorithms. This class of algorithms is quite diverse.

  1. Probabilistic algorithms make some random choices during the execution.
  2. Genetic algorithms try to solve a given problem by mimicking biological evolutionary processes. Typically, these are iterative algorithms where random mutations among the current “solutions” generate the next generation of “solutions.” In this manner, genetic algorithms implement the biological concepts of reproduction and “survival of the fittest.” We will see an example of this type in Section 14.5 .
  3. Heuristic algorithms. The general purpose of such algorithms is not to identify an optimal solution. They are employed when the computing time or memory requirements to find an optimal solution is beyond manageable bounds. Instead, heuristic algorithms construct an approximate solution in a reasonable time.

  Figure 4.4 Two popular ways to store connectivity information. (a) The first array contains pointers to the proteins interacting with protein 1, the second array contains the interaction partners of protein 2, etc. (b) An n × n matrix contains values of “1” for interacting proteins and values of “0” for those where no interactions were recorded.

  4.3 Data Structures for Graphs

  As introduced in Section 4.1 , a graph is an abstract data structure. A graph is formed by a set of vertices and a set of edges. The edges represent relationships (connections) between the vertices. In typical implementations of graphs, vertices are implemented as structures or objects. Edges can be realized in several ways. Each of them has its own advantages and disadvantages. One strategy is an adjacency list. This “list” essentially consists of an array of vertices that are associated with incident edges (Figure 4.4 ). If information is only stored in vertices, not in edges (i.e. it is not a weighted graph), a row simply contains the indices of the vertices to which the row vertex is connected to. In this way, edges can be represented in a memory saving fashion. A favorable property of this realization is that it is straightforward to add new vertices to the graph. They can be linked to existing vertices simply by adding elements to the appropriate arrays. On the other hand, it takes O(n) time to find out whether two given vertices are connected by an edge. Here, n

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Discrete Mathematics

  Graph Algorithms, Algebraic Structures, Coding Theory, and Cryptography

  • Sriraman Sridharan, R. Balakrishnan(Authors)
  • 2019(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 1 Graph Algorithms I

  The aim of physical sciences is not the provision of pictures, but the discovery of laws governing the phenomena and the application of these laws to discover new phenomena. If a picture exists, so much the better. Whether a picture exists or not is only a matter of secondary importance.

  P. Dirac

  In this chapter, we study various algorithms on graphs. Unfortunately, the graphs are not manipulated by their geometrical representation inside a computer. We start with two important representations of graphs: the adjacency matrix representation and the adjacency list representation. Of course, we have to choose a representation so that the operations of our algorithm can be performed in order to minimize the number of elementary operations.

  After seeing how the graphs are represented inside a computer, two minimum spanning tree algorithms in a connected simple graph with weights associated to each edge, one due to Prim and the other invented by Kruskal are presented. Then, shortest path problems in a weighted directed graph are studied. First, the single-source shortest path problem due to Dijkstra is presented. As an application, an algorithm is given to test the bipartiteness of a graph. Next, a single-source shortest path algorithm for negative edge weights is given. Then, all-pairs shortest path problem due to Floyd and the transitive closure algorithm by Warshall are given. Floyd’s algorithm is applied to find eccentricities of vertices, radius and diameter of a graph.

  Finally, we study a well-known graph traversal technique, called depth-first search. As applications of the graph traversal method, we study the algorithms to find connected components, biconnected components, strongly connected components, topological sort and program evaluation and research technique (PERT). In the last subsection, we study the famous NP-complete problem, traveling salesman problem (TSP) and present the brute-force algorithm and two approximate algorithms. For basic properties of graphs and digraphs, the reader may see [6

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Hands-On Data Structures and Algorithms with Python

  • Dr. Basant Agarwal(Author)
  • 2022(Publication Date)
  • Packt Publishing

    (Publisher)

  9

  Graphs and Algorithms

  Graphs are a non-linear data structure, in which the problem is represented as a network by connecting a set of nodes with edges, like a telephone network or social network. For example, in a graph, nodes can represent different cities while the links between them represent edges. Graphs are one of the most important data structures; they are used to solve many computing problems, especially when the problem is represented in the form of objects and their connection, e.g. to find out the shortest path from one city to another city. Graphs are useful data structures for solving real-world problems in which the problem can be represented as a network-like structure. In this chapter, we will be discussing the most important and popular concepts related to graphs.

  In this chapter, we will learn about the following concepts:

  • The concept of the graph data structure
  • How to represent a graph and traverse it
  • Different operations and their implementation on graphs

  First, we will be looking into the different types of graphs.

  Graphs

  A graph is a set of a finite number of vertices (also known as nodes) and edges, in which the edges are the links between vertices, and each edge in a graph joins two distinct nodes. Moreover, a graph is a formal mathematical representation of a network, i.e. a graph G is an ordered pair of a set V of vertices and a set E of edges, given as G = (V, E) in formal mathematical notation.

  An example of a graph is shown in Figure 9.1 :

  Figure 9.1: An example of a graph

  The graph G = (V, E) in Figure 9.1 can be described as below:

  • V = {A, B, C, D, E}
  • E = {{A, B}, {A, C}, {B, C}, {B, D}, {C, D}, {D, D}, {B, E}, {D, E}}
  • G = (V, E)

  Let’s discuss some of the important definitions of a graph:

  • Node or vertex : A point or node in a graph is called a vertex. In the preceding diagram, the vertices or nodes are A , B , C , D , and E and are denoted by a dot.
  • Edge : This is a connection between two vertices. The line connecting A and B

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Learning JavaScript Data Structures and Algorithms

  • Loiane Groner(Author)
  • 2018(Publication Date)
  • Packt Publishing

    (Publisher)

  Graphs

  In this chapter, you will learn about another nonlinear data structure, called graphs. This will be the last data structure we will cover before diving into sorting and searching algorithms. This chapter will cover a considerable part of the wonderful applications of graphs. Since this is a vast topic, we could write a book like this just to dive into the amazing world of graphs. In this chapter, we will cover:

  • Graph terminology
  • Representing a graph in three different ways
  • The graph data structure
  • Graph search algorithms
  • Shortest path algorithms
  • Minimum spanning tree algorithms

  Passage contains an image

  Graph terminology

  A graph is an abstract model of a network structure. A graph is a set of nodes (or vertices ) connected by edges . Learning about graphs is important because any binary relationship can be represented by a graph.

  Any social network, such as Facebook, Twitter, and Google+, can be represented by a graph. We can also use graphs to represent roads, flights, and communications, as shown in the following image: Let's learn more about the mathematical and technical concepts of graphs.

  A graph G = (V, E) is composed of:

  • V : A set of vertices
  • E : A set of edges connecting the vertices in V

  The following diagram represents a graph: Let's cover some graph terminology before we start implementing any algorithms.

  Vertices connected by an edge are called adjacent vertices . For example, A and B are adjacent, A and D are adjacent, A and C are adjacent, and A and E are not adjacent.

  A degree of a vertex consists of the number of adjacent vertices. For example, A is connected to three vertices. Therefore, A has degree 3. E is connected to two vertices. Therefore, E has degree 2.

  A path is a sequence of consecutive vertices, such as v1 , v2 , ..., vk , where vi and vi+1 are adjacent. Using the graph from the previous diagram as an example, we have the paths A B E I and A C D G , among others.

  A simple path does not contain repeated vertices. As an example, we have the path A D G . A cycle is a simple path, except for the last vertex, which is the same as the first vertex: A D C A (back to A

  Sign up to read

  Learn more about book