Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Graph (abstract data type)
Summary
In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics.
A graph data structure consists of a finite (and possibly mutable) set of vertices (also called nodes or points), together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges (also called links or lines), and for a directed graph are also known as edges but also sometimes arrows or arcs. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.
A graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).
The basic operations provided by a graph data structure G usually include:
tests whether there is an edge from the vertex x to the vertex y;
lists all vertices y such that there is an edge from the vertex x to the vertex y;
adds the vertex x, if it is not there;
removes the vertex x, if it is there;
adds the edge z from the vertex x to the vertex y, if it is not there;
removes the edge from the vertex x to the vertex y, if it is there;
returns the value associated with the vertex x;
sets the value associated with the vertex x to v.
Structures that associate values to the edges usually also provide:
returns the value associated with the edge (x, y);
sets the value associated with the edge (x, y) to v.
Adjacency list
Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices.
Adjacency matrix
A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.