CE204
Data Structures and Algorithms
Part 7
18/02/2020 CE204 Part 7
1
Graphs 1
A graph is a collection of vertices and edges, where each edge connects two of the vertices. We shall assume that the two vertices must be distinct (i.e. an edge cannot connect a vertex to itself) and that there is at most one edge connecting any given pair of vertices. An edge connecting two vertices u and v may be denoted by (u,v).
In an undirected graph the edge (u,v) is the same as (v,u), but in a directed graph each edge has a direction, so (u,v) and (v,u) would be distinct.
A path from vertex v1 to vk is a sequence of edges of the form (v1,v2), (v2,v3) …(vk-1,vk).
18/02/2020 CE204 Part 7
2
Graphs 2
A graph is connected if for every pair of vertices u and v there is a path from u to v.
A cycle is a non-empty path from a vertex to itself comprising distinct edges.
A graph that contains no cycles is said to be acyclic.
In a weighted graph a numeric value (the weight), usually an integer, is associated with each edge. In most applications this will represent some measure of distance, cost or capacity. An edge from u to v with weight 5 be may be denoted by (u,v,5).
18/02/2020 CE204 Part 7
3
Graphs 3
It is common to use n and e to denote the number of vertices and edges respectively of a graph.
It is easy to see that for any graph e