Insight into programming algorithms

Home » Graph Theory

Graph Theory


These include the programming algorithms related to graph theory for more information visit the wiki post.
The algorithms posted till date can be viewed for the sidebar on the left.

Basic Information

A graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics.

A graph data structure consists of a finite (and possibly mutable) set of vertices or 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, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.

Basic type of Graphs

1. Undirected Graph

An undirected graph is graph, where all the edges are bidirectional i.e, there is no particular direction given from on node to other. An undirected graph is sometimes called an undirected network.

2. Directed Graph

A directed graph is graph, where all the edges are directed from one vertex to another i.e, there is a particular direction given from one node to other. A directed graph is sometimes called a digraph or a directed network.

d-graph1

3. Cyclic Graph

A cyclic graph is a graph containing at least one graph cycle i.e, a node may be visited again from the same node by travelling through the edges.A cyclic graph possessing exactly one cycle is called a unicyclic graph.

4. Acyclic graph

An acyclic graph is a graph having no graph cycles i.e, a node cannot be visited again from the same node by travelling through the edges. Acyclic graphs are bipartite. A connected acyclic graph is known as a tree, and a disconnected acyclic graph is known as a forest (i.e., a collection of trees).

cyclicVSacyclic

These types can be combined as well for example, directed acyclic graph(DAG) or undirected cyclic graph etc.

There are various other types of graphs except these basic types which can be read about here and here.

Representations

There are different ways of representing a graph

1. Adjacency list

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.

adjlistexample

1. Adjacency List

2. Adjacency matrix

A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.

7.-Weighted-Graph-Adjacency-Matrix

3. Incidence matrix

A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column.

IncidenceMatrix_999

Incidence Matrix

%d bloggers like this: