Graph Basic without Library in C
Breadth Frist Search (BFS) in C
#include<stdio.h>
#include<iostream>
using namespace std;
#define for(i,b,c) for(int i=b; i<c; i++)
int adjMatrix[100][100];
int Vis[100];
int Node, Edge;
int queueSize = 1000;
int queue[1000];
int frontPivot=0, rearPivot=-1;
void enqueue(int item)
{
rearPivot = (rearPivot + 1)%queueSize;
queue[rearPivot]=item;
return;
}
void deque()
{
frontPivot = (frontPivot+1)%queueSize;
return;
}
int front()
{
return queue[frontPivot];
}
int isEmpty()
{
if(frontPivot==(rearPivot+1)%queueSize)
return 1;
return 0;
}
int Level[100]={-1};
void BFS(int root)
{
Vis[root]=1;
enqueue(root);
Level[root]=1;
while(isEmpty()!=1)
{
int src = front();
printf("%d ", src);
deque();
for(i, 1, Node+1)
{
if(adjMatrix[src][i]==1 && Vis[i]==0)
Level[i] = Level[src]+1, Vis[i]=1, enqueue(i);
}
}
return;
}
int main()
{
// int Node, Edge;
cin>>Node>>Edge;
for(i, 0, 100)
for(j, 0, 100)
Vis[i]=0, adjMatrix[i][j]=0;
for(i, 0, Edge)
{
int u, v;
cin>>u>>v;
adjMatrix[v][u]=1;
adjMatrix[u][v]=1;
}
BFS(1);
}
Depth Frist Search (DFS) in C
#include<stdio.h>
#include<iostream>
using namespace std;
#define for(i,b,c) for(int i=b; i<c; i++)
int adjMatrix[100][100];
int Vis[100];
int Node, Edge;
void DFS(int root)
{
Vis[root]=1;
printf("%d ", root);
for(i, 1, Node+1)
{
if(adjMatrix[root][i]==1 && Vis[i]==0){
DFS(i);
// Vis[i]=1;
}
}
return;
}
int main()
{
// int Node, Edge;
cin>>Node>>Edge;
for(i, 0, 100)
for(j, 0, 100)
Vis[i]=0, adjMatrix[i][j]=0;
for(i, 0, Edge)
{
int u, v;
cin>>u>>v;
adjMatrix[v][u]=1;
adjMatrix[u][v]=1;
}
DFS(1);
}
Cycle Detect in Directed Graph in C
#include<stdio.h>
int adjMat[11][11];
int adjMat2[11][11];
int vis[11];
int vis2[11];
int el[11];
int cnt;
void dfs2(int u)
{
vis2[u]=1;
el[cnt]=u;
cnt++;
int i, j;
for(i=0; i<10 ;i++)
{
if(adjMat2[u][i]==1 && !vis2[i])
dfs2(i);
}
}
void dfs(int u)
{
//printf("%d ", u);
int i;
vis[u]=1;
for(i=0; i<10 ;i++)
{
if(adjMat[u][i] && !vis[i])
dfs(i);
if(adjMat[u][i]&& vis[i] && !vis2[i])
{
cnt=0;
int k,l;
for(k=0; k<10; k++)
vis2[k]=0;
//printf(":: %d", i);
dfs2(i);
printf("Cycle Detected:");
for(k=0; k<cnt; k++)
{
for(l=k+1; l<cnt; l++)
{
if(el[l]<el[k])
{
int mn = el[l];
el[l]=el[k];
el[k]=mn;
}
}
}
for(k=0; k<cnt; k++)
printf(" %d",el[k]);
printf("\n");
return;
}
}
}
int main()
{
int i, j, k;
for(i=0; i<10; i++)
{
vis[i]=0;
for(j=0; j<10; j++)
{
adjMat[i][j]=adjMat2[i][j]=0;
}
}
int node, edge;
scanf("%d %d", &node, &edge);
for(i=0; i<edge; i++)
{
int u, v;
scanf("%d %d", &u, &v);
adjMat[u][v]=1;
adjMat2[v][u]=1;
}
for(i=0; i<node; i++)
if(!vis[i])
dfs(i);
return 0;
}
/*
10 10
0 1
1 2
2 0
3 4
4 5
5 6
6 7
7 3
8 8
9 9
*/
Cycle Detect in Undirected Graph by DFS
#include<stdio.h>
int adjMat[11][11];
int adjMat2[11][11];
int vis[11];
int vis2[11];
int el[11];
int cnt;
void dfs2(int u)
{
vis2[u]=1;
el[cnt]=u;
cnt++;
int i, j;
for(i=0; i<10 ;i++)
{
if(adjMat2[u][i]==1 && !vis2[i])
dfs2(i);
}
}
int gcnt;
void dfs(int u, int par=-1)
{
//printf("%d ", u);
int i;
vis[u]=1;
for(i=0; i<10 ;i++)
{
if(adjMat[u][i] && !vis[i])
dfs(i, u);
if(adjMat[u][i]&& vis[i] && par!=i && !vis2[i])
{
cnt=0;
int k,l;
for(k=0; k<10; k++)
vis2[k]=0;
// printf(":: %d", i);
dfs2(i);
printf("Cycle Detected:");
for(k=0; k<cnt; k++)
{
for(l=k+1; l<cnt; l++)
{
if(el[l]<el[k])
{
int mn = el[l];
el[l]=el[k];
el[k]=mn;
}
}
}
for(k=0; k<cnt; k++)
printf(" %d",el[k]);
printf("\n");
return;
}
}
}
int main()
{
int i, j, k;
for(i=0; i<10; i++)
{
vis[i]=0;
for(j=0; j<10; j++)
{
adjMat[i][j]=adjMat2[i][j]=0;
}
}
int node, edge;
scanf("%d %d", &node, &edge);
for(i=0; i<edge; i++)
{
int u, v;
scanf("%d %d", &u, &v);
adjMat[u][v]=1;
adjMat[v][u]=1;
adjMat2[v][u]=1;
adjMat2[u][v]=1;
}
for(i=0; i<node; i++)
if(!vis[i])
dfs(i);
return 0;
}
/*
10 10
0 1
1 2
2 0
3 4
4 5
5 6
6 7
7 3
8 8
9 9
*/
Cycle Detect in an Undirected graph by Disjoint Set in C
#include<stdio.h>
int adjMat2[11][11];
int vis2[11];
int el[11];
int cnt;
int Find(int par[], int u )
{
if(par[u]==-1 || par[u]==u)
return u;
else
return Find(par, par[u]);
}
void Union(int par[], int u, int v)
{
int par_u = Find(par, u);
int par_v = Find(par, v);
par[par_u]=par_v;
return;
}
void dfs2(int u)
{
vis2[u]=1;
el[cnt]=u;
cnt++;
int i, j;
for(i=0; i<10 ;i++)
{
if(adjMat2[u][i]==1 && !vis2[i])
dfs2(i);
}
}
void F(int i)
{
cnt=0;
int k,l;
for(k=0; k<10; k++)
vis2[k]=0;
dfs2(i);
printf("Cycle Detected:");
for(k=0; k<cnt; k++)
{
for(l=k+1; l<cnt; l++)
{
if(el[l]<el[k])
{
int mn = el[l];
el[l]=el[k];
el[k]=mn;
}
}
}
for(k=0; k<cnt; k++)
printf(" %d",el[k]);
printf("\n");
return;
}
struct Edge
{
int src, des;
};
int main()
{
int i, j, k;
for(i=0; i<10; i++)
{
vis2[i]=0;
for(j=0; j<10; j++)
{
adjMat2[i][j]=0;
}
}
int node, edge;
scanf("%d %d", &node, &edge);
Edge Edges[edge];
int par[19];
for(i=0; i<node; i++)
par[i]=-1;
for(i=0; i<edge; i++)
{
int u, v;
scanf("%d %d", &u, &v);
Edges[i].src = u;
Edges[i].des = v;
adjMat2[v][u]=1;
adjMat2[u][v]=1;
Union(par, u, v);
}
for(i=0; i<edge; i++)
{
int x = Find(par, Edges[i].src);
int y = Find(par, Edges[i].des);
if(x==y && !vis2[Edges[i].src])
{
F(Edges[i].src);
}
}
return 0;
}
/*
10 10
0 1
1 2
2 0
3 4
4 5
5 6
6 7
7 3
8 8
9 9
*/
Cycle Detect in Directed Graph by Coloring in C
#include<stdio.h>
int AdjMat[11][11];
int color[11];
int el[11];
int cnt;
#define WHITE 0
#define GRAY 1
#define BLACK 2
void DFS(int u)
{
color[u]=GRAY;
el[cnt]=u;
cnt++;
int i, j;
for(i=0; i<10 ;i++)
{
if(AdjMat[u][i]==1 && color[i]==WHITE)
DFS(i);
if(AdjMat[u][i]==1 && color[i]==GRAY)
{
printf("Cycle Detected in %d\n", u);
return;
}
}
color[u]=BLACK;
return;
}
int main()
{
int i, j, k;
for(i=0; i<10; i++)
{
color[i]=WHITE;
for(j=0; j<10; j++)
{
AdjMat[i][j]=0;
}
}
int node, edge;
scanf("%d %d", &node, &edge);
for(i=0; i<edge; i++)
{
int u, v;
scanf("%d %d", &u, &v);
AdjMat[u][v]=1;
}
for(i=0; i<edge; i++)
{
if(color[i]==WHITE)
{
DFS(i);
printf("-------------------\n");
}
}
return 0;
}
/*
10 10
0 1
1 2
2 0
3 4
4 5
5 6
6 7
7 3
8 8
9 9
*/
Print the elements in the Cycle in a Graph
#include<stdio.h>
int AdjMat[11][11], AdjMat2[11][11];
int vis[11], vis2[11];
int Ans[11];
int cnt;
void DFS2(int st, int en);
void DFS(int u)
{
vis[u]=1;
int i,k;
for(i=0; i<10; i++)
{
if(AdjMat[u][i]==1 && !vis[i])
DFS(i);
else if(AdjMat[u][i]==1 && vis[i])
{
cnt=0;
DFS2(u, i);
printf("-------------------\n");
int k;
for(k=0; k<cnt; k++)
{
printf(" %d",Ans[k]);
}
printf("\n");
}
}
return;
}
void DFS2(int st, int en)
{
vis2[st]=1;
Ans[cnt++]=st;
int i;
for(i=0; i<10; i++)
{
if(AdjMat2[st][i]==1 && !vis2[i])
{
if(i!=en)
DFS2(i, en);
else
{
Ans[cnt++]=en;
}
}
}
return;
}
int main()
{
int i, j, k;
for(i=0; i<10; i++)
{
vis[i]=0;
vis2[i]=0;
for(j=0; j<10; j++)
{
AdjMat[i][j]=0;
AdjMat2[j][i]=0;
}
}
int node, edge;
scanf("%d %d", &node, &edge);
for(i=0; i<edge; i++)
{
int u, v;
scanf("%d %d", &u, &v);
AdjMat[u][v]=1;
AdjMat2[v][u]=1;
}
for(i=0; i<edge; i++)
{
if(vis[i]==0)
{
DFS(i);
printf("-------------------\n");
}
}
return 0;
}
/*
10 10
0 1
1 2
2 0
3 4
4 5
5 6
6 7
7 3
8 8
9 9
*/
Negative Cycle Detect in a Directed Graph
#include<stdio.h>
int adjMat[11][11];
int cst[11];
#define md 99999
int min(int a, int b)
{
return a>b?b:a;
}
int BellmanFord(int Node)
{
int i, j,k;
for(i=1; i<Node; i++)
{
for(j=0; j<Node; j++)
{
for(k=0; k<Node; k++)
{
if(adjMat[j][k]!=0)
{
cst[k] = min(cst[j]+adjMat[j][k], cst[k]);
}
}
}
}
for(j=0; j<Node; j++)
{
for(k=0; k<Node; k++)
{
if(adjMat[j][k]!=0)
{
if(cst[j]+adjMat[j][k]<cst[k])
return 1;
}
}
}
return 0;
}
int main()
{
int i, j, k;
for(i=0; i<10; i++)
{
cst[i]=md;
for(j=0; j<10; j++)
adjMat[i][j]=0;
}
int node, edge;
scanf("%d %d", &node, &edge);
for(i=0; i<edge; i++)
{
int u, v, cost;
scanf("%d %d %d", &u, &v, &cost);
adjMat[u][v]=cost;
// adjMat[v][u]=cost;
}
if(BellmanFord(node))
printf("Cycle Detected!\n");
else
printf("No Cycle\n");
return 0;
}
/*
4 4
0 1 1
1 2 -1
2 3 -1
3 0 -1
*/
Kurskal’s Minimum Spanning Tree
#include<stdio.h>
int adjMat[11][11];
int vis[11];
struct Edges
{
int src, des, cost;
};
int Find(int par[], int u)
{
if(par[u]==u)
return u;
return Find(par, par[u]);
}
void Union(int par[], int u, int v)
{
int x = Find(par, u);
int y = Find(par, v);
if(x!=y)
par[x]=y;
return;
}
Edges Ans[11];
int cnt, tot_cost;
void KruskalAlgorithm(int par[], Edges Edge[], int n_edges)
{
cnt=0;
int i;
tot_cost=0;
for(i=0; i<n_edges; i++)
{
int x = Find(par, Edge[i].src);
int y = Find(par, Edge[i].des);
if(x!=y)
{
tot_cost+=Edge[i].cost;
Ans[cnt++]=Edge[i];
par[x]=y;
}
}
return;
}
int main()
{
int i, j, k;
int node, edge;
scanf("%d %d", &node, &edge);
Edges Edge[edge];
for(i=0; i<edge; i++)
{
int u, v, cost;
scanf("%d %d %d", &u, &v, &cost);
Edge[i].src=u;
Edge[i].des=v;
Edge[i].cost=cost;
}
for(i=0; i<edge; i++)
{
for(j=i; j<edge; j++)
{
if(Edge[i].cost>Edge[j].cost)
{
Edges tm = Edge[i];
Edge[i] = Edge[j];
Edge[j] = tm;
}
}
}
int par[node];
for(i=0; i<node; i++)
par[i]=i;
KruskalAlgorithm(par, Edge, edge);
printf("\nTotal Cost: %d\n", tot_cost);
printf("Final Edges:\n");
for(i=0; i<cnt; i++)
{
printf("%d---%d\n",Ans[i].src, Ans[i].des);
}
return 0;
}
/*
6 7
0 1 2
0 2 1
1 2 1
1 5 3
1 4 2
2 4 4
4 5 5
*/
Dijkstra’s Algorithm (Shorted Path from source to all other nodes)
#include<stdio.h>
int AdjMat[11][11], cost[11];
int nodes, edges;
#define inf 12345
#define min(a, b) a<b?a:b
void DijsktraAlgorithm(int vis[], int src)
{
vis[src]=1;
int i;
for(i=0; i<nodes; i++)
if(!vis[i] && AdjMat[src][i])
cost[i] = min(cost[i], cost[src]+AdjMat[src][i]);
int mn=inf, in=-1;
for(i=0; i<nodes; i++)
{
if(mn>cost[i] && !vis[i])
{
mn = cost[i];
in=i;
}
}
if(in!=-1)
DijsktraAlgorithm(vis, in);
return;
}
int main()
{
int i, j;
scanf("%d %d",&nodes, &edges);
int vis[nodes];
for(i=0; i<nodes; i++)
for(j=0; j<nodes; j++)
cost[i]=inf,vis[i]=0,AdjMat[i][j]=0;
for(i=0; i<edges; i++)
{
int u, v, cost;
scanf("%d %d %d",&u, &v, &cost);
AdjMat[u][v]=cost;
AdjMat[v][u]=cost;
}
cost[0]=0;
DijsktraAlgorithm(vis, 0);
printf("Shortest Distances from Source:");
for(i=0; i<nodes; i++)
printf(" %d",cost[i]);
return 0;
}
/*
6 8
0 1 2
0 2 1
1 2 1
1 5 3
1 4 2
2 4 4
4 5 5
5 3 1
*/
Folyd Warshall Algorithm (All Pair Shortest Path Algorithm)
#include<stdio.h>
int AdjMat[11][11];
int nodes, edges;
#define inf 12345
#define min(a, b) a<b?a:b
int main()
{
int i, j, k;
scanf("%d %d",&nodes, &edges);
for(i=0; i<nodes; i++)
for(j=0; j<nodes; j++)
AdjMat[i][j]=inf, AdjMat[i][i]=0;
for(i=0; i<edges; i++)
{
int u, v, cost;
scanf("%d %d %d",&u, &v, &cost);
AdjMat[u][v]=cost;
}
for(k=0; k<nodes; k++)
for(i=0; i<nodes; i++)
for(j=0; j<nodes; j++)
AdjMat[i][j] = min(AdjMat[i][j], AdjMat[i][k]+AdjMat[k][j]);
printf("Shortest Distances:\n");
for(i=0; i<nodes; i++)
{
for(j=0; j<nodes; j++)
printf("%d ",AdjMat[i][j]);
printf("\n");
}
return 0;
}
/*
6 8
0 1 2
0 2 1
1 2 1
1 5 3
1 4 2
2 4 4
4 5 5
5 3 1
*/