Graphs
This lab teaches you the following topics:
- How to create a graph
- How to search a graph using breadth and depth first search
Introduction
A graph G consists of a set V, whose members are called the vertices of G, together with a set E of pairs of distinct vertices from V. These pairs are called the edge of G. If e = v;w. is an edge with vertices v and w, then v and w are said to lie on e, and e is said to be incident with v and w. If the pairs are unordered, then G is called an undirected graph; if the pairs are ordered, then G is called a directed graph. The term directed graph is often shortened to digraph, and the unqualified term graph usually means undirected graph. The natural way to picture a graph is to represent vertices as points or circles and edges as line segments or arcs connecting the vertices. If the graph is directed, then the line segments or arcs have arrowheads indicating the direction.
Some Basic terms:
- Degree of a vertex, v, denoted deg(v) is the number of incident
- Parallel edges or multiple edges are edges of the same type and end-vertices
- Self–loop is an edge with the end vertices the same vertex
- Simple graphs have no parallel edges or self-loops
- Path is a sequence of alternating vetches and edges such that each successive vertex is connected by the edge. Frequently only the vertices are listed especially if there are no parallel edges.
- Cycle is a path that starts and ends at the same vertex.
- Simple path is a path with distinct vertices.
- Directed path is a path of only directed edges
- Directed cycle is a cycle of only directed edges.
- Sub-graph is a subset of vertices and edges.
- Spanning sub-graph contains all the vertices.
- Connected graph has all pairs of vertices connected by at least one path
- Connected component is the maximal connected sub-graph of a unconnected graph
- Forest is a graph without cycles.
Representation of Graph
Graph is a mathematical structure and finds its application is many areas, where the problem is to be solved by computers. The problems related to graph G must be represented in computer memory using any suitable data structure to solve the same. There are two standard ways of maintaining a graph G in the memory of a computer.
- Sequential representation of a graph using adjacent
Operations on Graph
Suppose a graph G is maintained in memory by the linked list representation. Basic operations are such as creating a graph, searching, deleting a vertices or edges.
- Creating A Graph
To create a graph, first adjacency list array is created to store the vertices name, dynamically at the run time. Then the node is created and linked to the list array if an edge is there to the vertex.
- Searching And Deleting From A Graph
Suppose an edge (1, 2) is to be deleted from the graph G. First we will search through the list array whether the initial vertex of the edge is in list array or not by incrementing the list array index. Once the initial vertex is found in the list array, the corresponding link list will be search for the terminal vertex.
Traversing a Graph
Many application of graph requires a structured system to examine the vertices and edges of a graph G. That is a graph traversal, which means visiting all the nodes of the graph. There are two graph traversal methods.
- Breadth First Search
Given an input graph G = (V, E) and a source vertex S, from where the searching starts. The breadth first search systematically traverses the edges of G to explore every vertex that is reachable from S. Then we examine the entire vertices neighbor to source vertex S. Then we traverse all the neighbors of the neighbors of source vertex S and so on. A queue is used to keep track of the progress of traversing the neighbor nodes.
- Depth First Search
The depth first search (DFS), as its name suggest, is to search deeper in the graph, whenever possible. Given an input graph G = (V, E) and a source vertex S, from where the searching starts. First we visit the starting node. Then we travel through each node along a path, which begins at S. That is we visit a neighbor vertex of S and again a neighbor of a neighbor of S, and so on. The implementation of BFS is almost same except a stack is used instead of the queue.
Lab Activities:
Activity 1:
Write a program to create a graph.
Solution:
#include<iostream.h>
#include<conio.h>
class graph
{
private:
int n;
int **a;
int *reach;
int *pos;
public:
graph(int k=10);
void create();
void dfs();
void dfs(int v,int label);
int begin(int v);
int nextvert(int v);
};
void graph::graph(int k)
{
n=k;
a=newint *[n+1];
reach=newint[n+1];
pos=newint [n+1];
for(int i=1;i<=n;i++)
pos[i]=0;
for(int j=1;j<=n;j++)
a[j]=newint[n+1];
}
void graph::create()
{
for(int i=1;i<=n;i++)
{
cout<<“Enter the “<<i<<“the row of matrix a:“;
for(int j=1;j<=n;j++)
cin>>a[i][j];
}
for(int k=1;k<=n;k++)
reach[k]=0;
}
void graph::dfs()
{
int label=0;
for(int i=1;i<=n;i++)
if(!reach[i])
{
label++’
dfs(i,label);
}
cout<<“The contents of the reach array is:”;
for(int j=1;j<=n;j++)
cout<<reach[j]<<” “;
}
void graph::dfs(int v,int label)
{
cout<<v<<” “;
reach[v]=label;
int u=begin(v);
while(u)
{
if(!reach[u])
dfs(u,label);
u=nextvert(v);
}
}
int graph::begin(int v)
{
if((v<1)&&(v>n))
cout<<“Bad input“;
else
for(int i=1;i<=n;i++)
if(a[v][i]==1)
{
pos[v]=i;
return i;
}
return 0;
}
int graph::nextvert(int v)
{
if((v<1)&&(v>n))
cout<<“Bad input“;
else
for(int i=pos[v]+1;i<=n;i++)
if(a[v][i]==1)
{
pos[v]=i;
return i;
}
return 0;
}
void main()
{
clrscr();
int x;
cout<<“Enter the no of vertices:“;
cin>>x;
graph g(x);
g.create();
cout<<“dfs is…. “;
g.dfs();
getch();
}
Activity 2:
Write a program to search a graph using breadth and depth first search.
Solution:
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
void create(); // For creating a graph
void dfs(); // For Depth First Search(DFS) Traversal.
void bfs(); // For Breadth First Search(BFS) Traversal.
struct node // Structure for elements in the graph
{
int data,status;
struct node *next;
struct link *adj;
};
struct link // Structure for adjacency list
{
struct node *next;
struct link *adj;
};
struct node *start,*p,*q;
struct link *l,*k;
int main()
{
int choice;
clrscr();
create();
while(1)
{
cout<<“——————–“;
cout<<“1: DFS, 2: BSF, 3: Exit , Enter your choice: “;
cin>>choice;
switch(choice)
{
case 1:
dfs();
break;
case 2:
bfs();
break;
case 3:
exit(0);
break;
default:
cout<<” Incorrect choice! Re-enter your choice.”;
getch();
}
}
return 0;
}
void create() // Creating a graph
{
int dat,flag=0;
start=NULL; ‘
cout<<“Enter the nodes in the graph(0 to end): “;
while(1)
{
cin>>dat;
if(dat==0)
break;
p=new node;
p->data=dat;
p->status=0;
p->next=NULL;
p->adj=NULL;
if(flag==0)
{
start=p;
q=p;
flag++;
}
else
{
q->next=p;
q=p;
}
}
p=start;
while(p!=NULL)
{
cout<<“Enter the links to “<<p->data<<” (0 to end) : “;
flag=0;
while(1)
{
cin>>dat;
if(dat==0)
break;
k=new link; k->adj=NULL;
if(flag==0)
{
p->adj=k;
l=k;
flag++;
}
else
{
l->adj=k;
l=k;
}
q=start;
while(q!=NULL)
{
if(q->data==dat)
k->next=q;
q=q->next;
}
}
p=p->next;
}
cout<<“———————————-“;
return;
}
// Deapth First Search(DFS) Traversal.
void bfs()
{
int qu[20],i=1,j=0;
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
qu[0]=p->data;
p->status=1;
while(1)
{
if(qu[j]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==qu[j])
break;
p=p->next;
}
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
qu[i]=q->data;
q->status=1;
qu[i+1]=0;
i++;
}
k=k->adj;
}
j++;
}
j=0;
cout<<“Breadth First Search Results “;
cout<<“————————-“;
while(qu[j]!=0)
{
cout<<qu[j]<<” “;
j++;
}
getch();
return;
}
// Breadth First Search(BFS) Traversal.
void dfs()
{
int stack[25],
top=1; cout<<“Depth First Search Results “;
cout<<“———————-“;
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
stack[0]=0;
stack[top]=p->data;
p->status=1;
while(1)
{
if(stack[top]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==stack[top])
break;
p=p->next;
}
cout<<stack[top]<<” “;
top–;
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
top++;
stack[top]=q->data;
q->status=1;
}
k=k->adj;
}
}
getch();
return;
}
Home Activities:
- Following is the algorithm for finding shortest path in a Implement it in C/C++.
Set V = {V1, V2, V3 …… Vn} contains the vertices and the edges E = {e1, e2,……em} of the graph G. W(e) is the weight of an edge e, which contains the vertices V1 and V2. Q is a set of vertices, which are not visited. m is the vertex in Q for which weight W(m) is minimum, i.e., minimum cost edge. S is a source vertex.
-
- Input the source vertices and assign it to S
-
-
- Set W(s) = 0 and
-
-
-
- Set W (v) = for all vertices V is not equal to S
-
-
- Set Q = V which is a set of vertices in the graph
-
- Suppose m be a vertices in Q for which W(m) is minimum
-
- Make the vertices m as visited and delete it from the set Q
-
- Find the vertices I which are incident with m and member of Q (That is the vertices which are not visited)
- Update the weight of vertices I = {i1, i2……. ik} by
(a) W(i1) = min [W(i1), W(m) + W(m, i1)]
-
- If any changes is made in W(v), store the vertices to corresponding vertices i, using the array, for tracing the shortest path
- Repeat the process from step 3 to 7 until the set Q is empty
-
- Exit
2. Implement dijkstra’s algorithm to find the shortest path in a
Related links
Single link list Stack AVL Trees Binary search Counting Sort
Doubly link list Queue Graphs Bubble Sort Radix sort
Circular link list Binary search tree Hashing Insertion Sort Bucket Sort
Josephus Problem Tree Traversal Heaps Quick Sort Merge Sort
At Cui tutorial, courses, past papers and final year projects
#tutorial #cui #pastpaper #courses
