Graph Data Structure

11 Key excerpts on "Graph Data Structure"

• 

  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 - PDF

  Connecting Discrete Mathematics and Computer Science

  • David Liben-Nowell(Author)
  • 2022(Publication Date)
  • Cambridge University Press

    (Publisher)

  But, of course, when we represent a graph on a computer, we’ll need to use some data structure to store a network, not just some image file. Here we will give a brief summary of the two major data structures used to represent graphs. If you’ve had a course on data structures, then this material may be a review; if not, it will be a preview. Taking it further: A visual representation is great for some smaller networks, and a well-designed layout can sometimes make even large networks easy to understand at a glance. Graph drawing is the problem of algorithmically laying out the nodes of a graph well—in an aesthetic and informative manner. There’s a physics analogy that’s often used in laying out graphs, in which we imagine nodes “attracting” and “repelling” each other depending on the presence or absence of edges. See p. 600 for more, including an application of this graph-drawing idea to the 9/11 Memorial in New York City. Some other gorgeous visualizations of network (and other!) data can be found online at sites like Flowing Data (http://flowingdata.com/), Information Is Beautiful (http://informationisbeautiful.net), or some of the beautiful books on data visualization (such as [18]). The most straightforward data structure for a graph is just a list of nodes and a list of edges. But this straightforward representation suffers for some standard, natural questions that are typically asked about graphs. Many of the natural questions that we will find ourselves asking are things like: What are all of the neighbors of A? or Are B and C joined by an edge? There are two standard data structures for graphs, each of which is tailored to make it possible to answer one of these two questions quickly. Adjacency lists The first standard data structure for graphs is an adjacency list, which—as the name implies—stores, for each node u, a list of the nodes adjacent to u: Definition 11.12: Adjacency list.

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  Data Structures and Program Design Using C

  A Self-Teaching Introduction

  • D. Malhotra, N. Malhotra(Authors)
  • 2018(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  C H A P T E R 12 GRAPHS In This Chapter ● ● Introduction ● ● Definitions ● ● Graph representation ● ● Graph traversal techniques ● ● Topological sort ● ● Minimum spanning tree ● ● Summary ● ● Exercises 12.1 Introduction So far, we have studied various types of linear data structures which are widely used in various applications. But the only non-linear data struc- ture we have studied thus far is trees. In trees, we discussed the parent- child relationship in which one parent can have many children. But in graphs, this parent-child relationship is less restricted, that is, any com- plex relationship can exist. Thus, a tree can be generalized as a special type of graph. Therefore, a graph is a non-linear data structure which has a wide range of real-life applications. A graph is a collection of some ver- tices (nodes) and edges that connect these vertices. Figure 12.1 represents a graph. 474 • DATA STRUCTURES AND PROGRAM DESIGN USING C Thus, a graph G can be defined as an ordered set of vertices and edges (V, E), where V(G) represents the set of vertices and E(G) represents the set of edges that connect these vertices. In the previous figure, V(G) = {A, B, C, D, P, Q} represents the set of vertices and E(G) = {(A, B), (B, D), (D, C), (C, A), (C, Q), (Q, D), (A, P), (P, C)} represents the set of edges. Now, there are two types of graph: 1. Undirected Graph – In an undirected graph, the edges do not have any direction associated with them. As we can see in the following fig- ure, the two nodes A and B can be traversed in both the directions, that is, from A to B or from B to A. Thus, an undirected graph does not give any information about the direction. Practical Application: A simple illustration of the graph is that when we connect with our friends on social media, say Facebook, where each user is a vertex and two users connect with each other, it forms an edge. FIGURE 12.1. A graph.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Introduction to Logic Design

  • Svetlana N. Yanushkevich, Vlad P. Shmerko(Authors)
  • 2008(Publication Date)
  • CRC Press

    (Publisher)

  3 Graphical Data Structures Graphs Directed and undirected Isomorphic Planar Cubes and hypercubes Binary trees Nodes, root, links, paths The adjacency matrix H-trees Codes and graphs Decision trees and functions Spanning trees Functions and decision trees Lattice topology Embedding Evaluation Advanced topics Topology and placement Topology and computing Graphical Data Structures 67 3.1 Introduction Graphical data structures are suitable for representing and computing logic functions. Graphs show the relationship between the variables of a logic function. The manipulation of the variables and terms of a function is replaced by the manipulation of graphical components (nodes, links, and paths): < Algebraic data structure > ⇔ < Graphical data structure > 3.2 Graphs in discrete device and system design A logic network is modeled using an abstraction, which shows the relevant features without their associated details. In the design of digital devices, there are three levels of abstraction: The architectural level, which represents a set of devices performing a set of operations. Graphs such as block diagrams are used at this level for viewing such features as parallelism of processing, data transfer, and position of devices. The logical level shows how a network evaluates a set of logic functions. Graphical data structures such as directed graphs, or networks of nodes representing gates, are used at this level for representation, manipulation, and computing. The physical , or geometric , level, which represents a network as a set of geometric entities. Graphical data structures such as placement and routing diagrams are used for a representation of components that is suitable for implementation of the available technology. 3.2.1 Graphs at the logical level The use of graphs in logic design implies compliance with graph theory. Graph theory includes the classification of graphs, their properties, and techniques for their manipulation.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms Using C#

  • Michael McMillan(Author)
  • 2007(Publication Date)
  • Cambridge University Press

    (Publisher)

  C HAPTER 16 Graphs and Graph Algorithms T he study of networks has become one of the great scientific hotbeds of this new century, though mathematicians and others have been studying networks for many hundreds of years. Recent developments in computer technology (i.e., the Internet), and in social theory (the social network, popularly con-ceived in the concept of “six degrees of separation”), have put a spotlight on the study of networks. In this chapter, we look at how networks are modeled with graphs. We’re not talking about the graphs such as pie graphs or bar graphs. We define what a graph is, how they’re represented in VB.NET, and how to implement important graph algorithms. We also discuss the importance of picking the correct data representation when working with graphs, since the efficiency of graph algorithms is dependent on the data structure used. G RAPH D EFINITIONS A graph consists of a set of vertices and a set of edges . Think of a map of your state. Each town is connected with other towns via some type of road. A map is a type of graph. Each town is a vertex and a road that connects two towns is an edge. Edges are specified as a pair , (v1, v2), where v1 and v2 are two vertices in the graph. A vertex can also have a weight , sometimes also called a cost. 283 284 GRAPHS AND GRAPH ALGORITHMS A B C D E F G H F IGURE 16.1. A Digraph (Directed Graph). A graph whose pairs are ordered is called a directed graph , or just a digraph . An ordered graph is shown in Figure 16.1 . If a graph is not ordered, it is called an unordered graph , or just a graph. An example of an unordered graph is shown in Figure 16.2 . A path is a sequence of vertices in a graph such that all vertices are connected by edges. The length of a path is the number of edges from the first vertex in the path to the last vertex. A path can also consist of a vertex to itself, which is called a loop .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Computer Arithmetics for Nanoelectronics

  • Vlad P. Shmerko, Svetlana N. Yanushkevich, Sergey Edward Lyshevski(Authors)
  • 2018(Publication Date)
  • CRC Press

    (Publisher)

  5 Graph-Based Data Structures 5.1 Introduction Theoretically, any problem associated with a finite graph is solvable. Graphical data structures are one of the ways for specification of logic functions. Graphs show the relationship between the variables and the logic function. The manipulation of the variables and terms of a function is replaced by the manipulation of graphical components (nodes, links, and paths). 5.2 Graphs in discrete device and system design A logic network is modeled using an abstraction, which shows the relevant features without their associated details. In the design of digital devices, there are three levels of abstraction. The architectural level, which represents a set of devices performing a set of operations. Graphs such as block diagrams are used at this level for viewing such features as parallelism of processing, data transfer, and position of devices. The logical level shows how a network evaluates a set of logic functions. Graphical data structures such as directed graphs, or networks of nodes representing gates, are used at this level for representation, manipulation, and computing. The physical , or geometric , level, which represents a network as a set of geometric entities. Graphical data structures such as placement and routing diagrams are used for a representation of components that is suitable for implementation of the available technology. 5.2.1 Graphs at the logical level The use of graphs in logic design implies compliance with graph theory. Graph theory includes the classification of graphs, their properties, and techniques 97 98 Computer Arithmetics for Nanoelectronics for their manipulation. The type of graph used in logic design depends on the specific problem; in particular: (a) if the direction of dataflow is important, directed graphs are used; (b) if data are transmitted using operations, bipartite graphs are appropriate; and (c) if a problem is represented by a decision table, trees and diagrams are used.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms in Java

  • Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser(Authors)
  • 2014(Publication Date)
  • Wiley

    (Publisher)

  Chapter 14 Graphs Contents 14.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574 14.1.1 The Graph ADT . . . . . . . . . . . . . . . . . . . . . . . 580 14.2 Data Structures for Graphs . . . . . . . . . . . . . . . . . . 581 14.2.1 Edge List Structure . . . . . . . . . . . . . . . . . . . . . 582 14.2.2 Adjacency List Structure . . . . . . . . . . . . . . . . . . 584 14.2.3 Adjacency Map Structure . . . . . . . . . . . . . . . . . . 586 14.2.4 Adjacency Matrix Structure . . . . . . . . . . . . . . . . . 587 14.2.5 Java Implementation . . . . . . . . . . . . . . . . . . . . 588 14.3 Graph Traversals . . . . . . . . . . . . . . . . . . . . . . . . 592 14.3.1 Depth-First Search . . . . . . . . . . . . . . . . . . . . . 593 14.3.2 DFS Implementation and Extensions . . . . . . . . . . . . 598 14.3.3 Breadth-First Search . . . . . . . . . . . . . . . . . . . . 602 14.4 Transitive Closure . . . . . . . . . . . . . . . . . . . . . . . 605 14.5 Directed Acyclic Graphs . . . . . . . . . . . . . . . . . . . . 609 14.5.1 Topological Ordering . . . . . . . . . . . . . . . . . . . . 609 14.6 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . 613 14.6.1 Weighted Graphs . . . . . . . . . . . . . . . . . . . . . . 613 14.6.2 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . 615 14.7 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . 624 14.7.1 Prim-Jarn ´ ık Algorithm . . . . . . . . . . . . . . . . . . . 626 14.7.2 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . 629 14.7.3 Disjoint Partitions and Union-Find Structures . . . . . . . 634 14.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639 574 Chapter 14. Graphs 14.1 Graphs A graph is a way of representing relationships that exist between pairs of objects. That is, a graph is a set of objects, called vertices, together with a collection of pairwise connections between them, called edges.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Graphs Theory and Applications

  With Exercises and Problems

  • Jean-Claude Fournier(Author)
  • 2013(Publication Date)
  • Wiley-ISTE

    (Publisher)

  section 6.4 ).

  1.2 Definition of graphs

  An (undirected) graph G is defined by two finite sets:3 a non-void set X of elements called vertices , a set E (which can be empty) of elements called edges , with for each edge e two associated vertices, x and y , distinct or not, called the endvertices of e .

  1.2.1 Notation

  We write G = (X , E ). The sets X and E can be denoted by X (G ) and E (G ). The cardinality of X , that is the number of vertices, is usually denoted by n or nG . The cardinality of E , that is, the number of edges, is denoted by m or

  mG

  . The pair of endvertices of an edge e is simply denoted by xy (or yx ) instead of the customary mathematical notation {x , y } when x ≠ y .

  1.2.2 Representation

  It is both usual and practical to draw a graph in a plane in the following manner: the vertices are represented by dots and the edges by simple lines (which can be mathematically defined with precision) connecting two endvertices (see Figure 1.2 ).

  There are, of course, many possible representations for a particular graph because of the different ways there are to place the vertices dots and to trace the edge lines in the plane. For certain applications it is important to find a drawing which shows the structure of the graph, or some of its properties, in relation to the application studied. One example of this is the representation on a screen of the potential task graph in scheduling tasks (discussed in Chapter 6

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Fundamentals of Graph Theory

  • Allan Bickle(Author)
  • 2020(Publication Date)
  • American Mathematical Society

    (Publisher)

  Chapter 1 Basics of Graphs 1.1. Graphs as Models Social networks have become increasingly prominent in modern life. On the inter-net, a social network has many people as members. These people are friends with some people and not with others. This is a virtual version of real-life friendships. Instead of friendship, the relationship between people could be acquaintance or it could be biological relation. In other industries, more distinct relationships are possible. In the entertain-ment industry, we can ask whether two people have ever collaborated on some project. In academia, a natural relationship to consider is whether two people have ever coauthored a paper. There are many questions we can ask about social networks. Who has the most friends? What is the largest number of people who are all friends? Given two people, what is the smallest number of people required to “connect” them? Rather than try to solve equivalent problems separately in different contexts, we should use a mathematical model that can describe all of these situations. Then we can solve problems once in this abstract setting and apply the results to many different real-world problems. We can model a social network by drawing a dot to represent each person and a line between two dots when two people are friends. Example. Abe is friends with Barry and Darrel. Barry is friends with Abe and Evan. Carl is friends with Darrel. Darrel is friends with Abe, Carl, and Evan. Evan is friends with Barry and Darrel. These friendships are illustrated in the figure below. 1 2 1. Basics of Graphs Abe Barry Carl Darrel Evan The same model works just as well for other relationships between people, and many other real-world problems. Definition 1.1. A graph G is a mathematical object consisting of a finite non-empty set of objects called vertices V ( G ) (the vertex set ), and a set of edges E ( G ) (the edge set ). An edge is two-element subset of the vertex set. We commonly use G and H for graphs; u , v , w, .

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Handbook of Graph Theory

  • Jonathan L. Gross, Jay Yellen, Ping Zhang, Jonathan L. Gross, Jay Yellen, Ping Zhang(Authors)
  • 2013(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 1

  Introduction to Graphs

  Section 1.1 Fundamentals of Graph Theory

  Jonathan L. Gross Columbia University Jay Yellen Rollins College

  Introduction

  Configurations of nodes and connections occur in a great diversity of applications. They may represent physical networks, such as electrical circuits, roadways, or organic molecules. They are also used in representing less tangible interactions as might occur in ecosystems, sociological relationships, databases, or in the flow of control in a computer program.

  1.1.1 Graphs and Digraphs

  Any mathematical object involving points and connections between them may be called a graph . If all the connections are unidirectional, it is called a digraph . Our highly inclusive definition in this initial section of the Handbook permits fluent discussion of almost any particular modification of the basic model that has ever been called a graph.

  Basic Terminology

  Definitions

  D1 : A graph G = (V , E ) consists of two sets V and E .

  • The elements of V are called vertices (or nodes ).
  • The elements of E are called edges .
  • Each edge has a set of one or two vertices associated to it, which are called its endpoints . An edge is said to join its endpoints.

  NOTATION : The subscripted notations V G and E G (or V (G ) and E (G )) are used for the vertex- and edge-sets when G is not the only graph under consideration.

  D2 : If vertex v is an endpoint of edge e , then v is said to be incident on e , and e is incident on v .

  D3: A vertex u is adjacent to vertex v if they are joined by an edge.

  D4: Two adjacent vertices may be called neighbors .

  D5: Adjacent edges are two edges that have an endpoint in common.

  D6: A proper edge is an edge that joins two distinct vertices.

  D7: A multi-edge

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  C++ Programming

  Program Design Including Data Structures

  • D. Malik(Author)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  Clearly, each node has two components, say vertex and link . The component vertex contains the index of the vertex adjacent to vertex i . EXAMPLE 20-4 Consider the directed graphs of Figure 20-4. Figure 20-5 shows the adjacency list of the directed graphs G 1 and G 2 FIGURE 20-5 Adjacency list of graphs of Figure 20-4 3 4 5 2 2 [1] [2] [3] [4] [5] 3 5 1 3 2 8 0 5 4 5 0 7 4 6 6 [0] [1] [2] [3] [4] [5] [6] [7] [8] Adjacency list of graph G 1 of Figure 20-4 Adjacency list of graph G 2 of Figure 20-4 Operations on Graphs Now that you know how to represent graphs in computer memory, the next obvious step is to learn the basic operations on a graph. The operations commonly performed on a graph are as follows: 1. Create the graph. That is, store the graph in computer memory using a particular graph representation. 2. Clear the graph. This operation makes the graph empty. 3. Determine whether the graph is empty. Copyright 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-300 1424 | Chapter 20: Graphs 4. Traverse the graph. 5. Print the graph. We will add more operations on a graph when we discuss a specific application or a particular graph later in this chapter. How a graph is represented in computer memory depends on the specific applica-tion. For illustration purposes, we use the adjacency list (linked list) representation of graphs. Therefore, for each vertex, v , the vertices adjacent to v (in a directed graph, also called the immediate successors ) are stored in the linked list associated with v . To manage the data in a linked list, we use the class unorderedLinkedList , discussed in Chapter 16. The labeling of the vertices of a graph depends on a specific application. If you are dealing with the graph of cities, you could label the vertices by the names of the cit-ies. However, to write algorithms to manipulate a graph as well as to simplify the algorithm, there must be some ordering to the vertices.

  Sign up to read

  Learn more about book