In programming, graphs allow us to represent a particular class of problem that is concerned with the connections between nodes: is there way to connect two nodes via a series of other connected nodes? How many nodes are connected to any given node? What is the shortest chain of connections between two nodes?
Examples of applications using graph structures: the web, where each page is a node and the links on it to other pages constitute the connections; schedules, where each item is a particular job that must be performed and constraints are the connections.
There are many different types of graphs. The four most important graphs types are:
- undirected graphs: where the direction of the connection is not important
- digraphs or directed graphs: where the direction is considered important in the interpretation of the connection.
- edge-weighted graphs: undirected graphs where each connection from a particular graph has an associated weight. As the direction is ignored in such graphs, weight “applies” in both directions.
- edge-weighted digraphs: similar to edge-weighted graphs, however the connections have to take direction into account. In this case, weights can be different per direction for the same connection.
Anomalies
Two features of graphs that are considered to be anomalous are self-loops and parallel edges. Self-loops are connections that connect a given node back to itself. Parallel edges are those that connect the same two nodes.
Graph Terminology
- adjacent: describes two vertices that are connected by an edge, in this case, the edge is incident to both nodes
- degree: number of edges incident to a given vertex
- path: sequence of vertices connected by edges
- cycle: path with at least one edge whose first and last vertices are the same – the length is the number of edges
- a graph is said to be connected if there is a path from every vertex to every other vertex in the graph
- acyclic: graph with no cycles, i.e. a tree