New Page 0

Graph

Graph (network) consists of nodes (vertices) and links (edges,arcs) between them.

A Vertex of a Graph is a connection point.

A Graph has a set of Vertices, usually shown as V = {v1, v2, ..., vn}
V = {A, B, C} or V = {1, 2, ... N}

A Vertex may have no connections, one connection or many connections.

A vertex may have any number of properties such as a name or a color.

An Edge in a graph is a connection between vertices.

Given vertices v1 and v2 in a Graph, the edge between them may be written as (v1,v2) or sometimes [v1,v2].

A Graph has a set of Edges usually denoted E.
E = {(v1,v2), (v2,v3)}

A graph may not have a more than one edge between the same vertices.

The Edge Connectivity of an Undirected Graph is the minimum number of edges that must be removed to "disconnect the graph." This is a number. A value of zero means the given graph has at least one pair of vertices x, y in V such that there is no path connecting x and y.

Adjacent (adj) vertices : joined by an edge.

A Subgraph S consists of a subset of vertices of some graph G and a subset of edges of graph G.

Example: A adj to C , but not to D.

Connected Graph	Every vertex has at least one edge to another vertex.
Disconnected Graph	There exist at least one node that is not connected to the graph.
Fully connected	every vertex has an edge to every other vertex.
Directed Graph	Each edge has a direction ( can have up to two edges, one in each direction) (v1,v2) means an edge starting at v1 and going to v2. (v1,v2) is NOT the same as (v2,v1).
Undirected graph	Edges has no direction (has at most one edge between a pair of vertices) (v1,v2) is the same as (v2,v1), the edge just connects v1 to v2.
weights	The values of the edges .Weights may be integers, real numbers, gallons per minute or any type of quantity. (v1,v2,10GPM) would indicate an Edge from vertex v1 to v2 with a flow of 10 gallons per minute. There are special cases that may not allow zero or negative weights.
Weighted Graph	Each edge has a weight
Path	Is the number of connected vertices. Between two vertices is a sequence of edges that starts at one vertex and ends at anothervertex. It may pass through the same vertex more than once
Path length	Is the number of edges that connects them.
Simple path	All vertices are distinct except the first and last can be the same. May not pass through the vertex more than once.
Directed path	Sequence of directed edges between two vertices.
Cycle	Path that begins and ends at the same vertex.
Simple cycle	Cycle which does not pass through the vertex more than once. Except the first and last can be the same
Acyclic graph	Graph with no cycles.
Complete	Each pair of distinct vertices has an edge between them.
multigraph	Graph that can have multiple edges between the same vertices e.g. E = {(v1,v2), (v1,v2), (v2,v3)}. Note: in a Directed Graph (v1,v2) and (v2,v1) is not a multi-graph, just two edges going different directions. In an Undirected Graph sometimes (v1,v2) and (v2,v1) may be included even though they are redundant and the Graph may not be considered a multi-graph.
loop or self edge	A graph edges that begins and ends at the same vertex, e.g. (v3,v3).

Example of using a graph : to connect cities.

Operating the Graph is done by 2 sets of operations , first on the nodes and second on the edges.

Create a new Graph

Insert a vertex

Delete a vetrex

Set/Get data for a vertex

Insert an edge

Delete an edge

Set / Get details of edge

Display the graph including its vertices and edges.

Array Based Representation

An adjacency matrix for a graph with n vertices numbered 0...n-1 is an n by n array matrix such that:
matrix[i][j]=1 ,if there is an edge from vertex i to vertex j
matrix[i][j]=0 ,otherwise.
If the graph is weighted, the labels are values in the matrix.
if there is no edge between a pair of vertices, then it should be infinity in the matrix (or a value that means infinity).
The matrix for an undirected graph is symmetrical.

2 arrays are required :

Vertex Array ( hold vertices details)

Adjacency matrix ( hold details of edges)

For example to connect Muharraq and Sitra , the locations 0,2 and 2,0 in the adjacency matrix is set to 1.
If the graph is directional (one way) , from Sitra to Muharraq , then only location 2,0 is set to 1.
If the links are to hold more than one value as the weight , then the matrix needs to be declared as an array of structure.
The used member is useful to avoid shifting when deleting , and reuse locations that were previously occupied.

float adjacency[SIZE][SIZE]; // Adjacency Matrix

Data Definitions	Initialization		Inserting a vertex
const int SIZE = 10; struct node{ char name[15]; int population; int used; } node cities[SIZE];	for(int i=0 ;i<SIZE; i++) cities[i].used=0;		for( i=0 ; i<SIZE ; i++) if(!cities[i].used ) { strcpy(cities[i].name , newName); cities[i].population=newPop; cities[i].used=1; break; }
Deleting a vertex			Setting and Getting vertex details
All the links must first be removed before deletion by setting all values in the adjacency matrix in the row and column matching index to 0 .			for(int i=0; i<SIZE; i++) if(strcmp(cities[i].name,SearchName)==0) { // set or get details break; }
for(int i=0; i<SIZE; i++) if(strcmp(cities[i].name,delname)==0) { cities[i].used==0); break; }
Insert an edge		Delete an edge
(1) Find the indexes of the 2 cities to be linked.		Find the indexes of the 2 cities to be remove the link between and then remove the link.
for(int i=0; i<SIZE; i++) if(cities[i].used && strcmp(cities[i].name,name)==0) { index=i; break; }		adjacency[index1][index2]=0; adjacency[index2][index1]=0;
(2) Link the 2 cities (establish bi-directional link)
adjacency[index1][index2]=dist; adjacency[index2][index1]=dist;

Graph Traversal

General Traversal (1)

// Given a city index the function returns its name
char* getName( int j)
{
if (cities[j] .used)
     return(cities[j] .name);
else
     return ("not found");
}
// Prints all out going links originating from the city index passed.
void printLinks(int i)
{
cout << "Links to: \n";
for (int j =0 ; j < SIZE; j++)
{
if (adjacency[i][j] > 0)
      cout << getName(j)
             <<" with distance" <<adjacency [i][j] << " \n";
}
void traversal() {
/* The vertex/nodes array is read , and the information for each city is printed. All outgoing links from each city are also printed by calling "printLinks".*/
for (int i=0; i < SIZE; i++)
      if (cities[i] .used)

        {
          cout << " \n City :"<<cities[i].name;
          printLinks(i) ;

}

Depth First Traversal -DFS (2)	Breadth First Traversal -BFS (3)

// Traverses a Graph Beginning at Vertex v Stack s s.push(v) // v is considered visited once pushed to s while (!s.isEmpty()) { s.getTop(topV) // topV is the vertex on top of the stack if (there is at least one unvisited vertex u adjacent to topV) s.push(u) // u is visited and pushed to the stack else s.pop() // backtrack to a previous vertex }// end while	//Traverse a graph beginning at Vertex v Queue q q.add(v) // v is considered visited once added to Q while (!q.isEmpty()) { q.getFront(frontV) // frontV is the vertex at the front of the queue q.remove() // there is a path from the vertex frontV to every vertex added to the queue q for (each unvisited vertex u adjacent to frontV) q.add(u) // u is visited and added to the queue q }// end while
Drawbacks with DFS and BFS is that they can traverse only connected graph

Shortest Path

Dijkstra's shortest path can be used to determine the shortest path from any node to all nodes in the graph.
The graph needs to be initialized with high values at the beginning.
The algorithm stores all weights from the source vertex to all other vertices in the graph in an array called weight.
It then step by step attempts to visit the vertex with minimum weight using the vertices stored in a set visited, and adding the newly visited vertex to it.

/* Finds the minimum cost path between an origin vertex (vertex 0) and all other vertices in a weighted directed graph of N vertices. Graph's weights are nonnegative./ Shortest Path (Graph) { visited = vertex 0; for (vertex = 0 through N-1) weight[vertex]* = adjacency[0][vertex] for (count = 2 through N) { find the smallest weight[vertex] such that vertex is not visited add vertex to visited // Check weight [unvisited] for all unvisited vertices not in visited for (all vertices not visited) if (weight [unvisited] > ( weight [vertex] + adjacency[vertex][unvisited] )) weight [unvisited] = weight[vertex] + adjacency[vertex][unvisited] } // end Shortest path
Example 1, find the shortest path from 0 to all other vertices

	Executing the shortest path algorithm
The locations with no connections are set to the highest value possible. Vertex 0 is added to the set visited and the array weight is updated for all direct connections from 0. At count 2 the cheapest path is to vertex 4, so it is added to visited. A cheaper path from 0 through 4 to all other unvisited vertices is examined, and a cheaper one found to 2 and 3. At count 3 vertex 3 is added to visited and a cheaper path is examined from 3 to all other vertices not invisited. A cheaper one found from 0 to 1 through 4 then 3. At count 4 vertex 1 is added to visited and a path from 0 to 2 is examined through 1, but no change since there is no cheaper link. At count 5, 2 is the only remaining vertex, so - it is added to visited and we stop. At count 1 the algorithm found that the shortest way to get to 4 is directly, the shortest way to get to 2 and 3 is through 4 at count 2, and the shortest way to 1 is through 4 and 3 at count 3.
Example2

Spanning Tree

A tree is a special type of a undirected graph that is connected but with no cycles.
Therefore, all trees can be considered graphs, but not all graphs are trees.
A spanning tree of a connected undirected graph G is a subgraph of G that contains all G's nodes and enough edges to connect them. Given a graph G, if we remove all cycles from the graph, the resulting graph is a spanning tree.
There could be more than one spanning tree for a graph, and the commonly used one in problem solving is the minimum spanning tree.

The Minimum Spanning Tree

It is a tree that connects all nodes in a graph such that edges with minimum weight are selected, and others are removed

Select a starting vertex V
Mark V as visited and include it in the minimum spanning tree
Repeat the following steps while there are unvisited vertices
1. Find the least-cost edge (V,U) from a visited vertex V to unvisited U
2. Mark U as visited and add it to the minimum spanning tree
3. Add the edge (V,U) to the minimum spanning tree.