Graph Data Structure

Graph Data Structure

1. The graphics

   • they are collections of things
   • relationships
   • connections between
   • The data is called
     • nodes
     • vertices

2. The connections between the nodes

   • they are called edges
     • non-lineal data estructure
   • hierarchical structures

3. represent networks

4. it's an abstract type of data

   • TAD

5. Forms of representation

   • Adjacency Matrix
     • associate
       • row
       • column
     • to each node of the graph
   • Adjacency list
     • associate
       • each node to a list
       • that contains all those nodes that are adjacent

6. graph directed

   • graph not directed

7. tree

   • directed graph
     • cycles are not allowed
     • node called root
       • A collection of trees is called
         • a forest
         • Degree
           • Number of subtrees of a node.
           • Level
             • The level of a node is defined by 1
             • + (the number of connections between the node and the root).
             • Height of a node
               • number of edges in the longest path
               • between that node and a sheet.
     • to each of the other nodes
   • abstract data type (TAD)
     • root
     • parent node
     • son node
     • non-linear structure
       • Root:
         • The top node of a tree
       • Son
         • A node directly connected to another
       • Father
         • The inverse notion of son.
         • Brothers:
           • A set of nodes with the same father.
           • Sheet:
             • A node without children.
             • Internal node:
               • A node with at least one child.

Bilder und Dateien der Mindmap