Graph Algorithm

Graph is a collection of vertices or nodes, connected by a collection of edges. Graphs are extremely important because they are a very flexible mathematical model for many application problems. Basically, any time you have a set of objects, and there is some “connection” or “relationship” or “interaction” between pairs of objects, a graph is a good way to model this. Examples of graphs in application include communication and transportation networks, VLSI and other sorts of logic circuits, surface meshes used for shape description in computer-aided design and geographic information systems, precedence constraints in scheduling systems etc.

A directed graph (or digraph) G = (V,E) consists of a finite set V , called the vertices or nodes, and E, a set of ordered pairs, called the edges of G.

An undirected graph (or graph) G = (V,E) consists of a finite set V of vertices, and a set E of unordered pairs of distinct vertices, called the edges.

We say that vertex v is adjacent to vertex u if there is an edge (u; v). In a directed graph, given the edge e = (u; v), we say that u is the origin of e and v is the destination of e. In undirected graphs u and v are the endpoints of the edge. The edge e is incident (meaning that it touches) both u and v.

In a digraph, the number of edges coming out of a vertex is called the out-degree of that vertex, and the number of edges coming in is called the in-degree. In an undirected graph we just talk about the degree of a vertex as the number of incident edges. By the degree of a graph, we usually mean the maximum degree of its vertices.

Notice that generally the number of edges in a graph may be as large as quadratic in the number of vertices. However, the large graphs that arise in practice typically have much fewer edges. A graph is said to be sparse if E = Θ(V ), and dense, otherwise. When giving the running times of algorithms, we will usually express it as a function of both V and E, so that the performance on sparse and dense graphs will be apparent.