Arjun Suresh (talk | contribs) (Created page with "<syntaxhighlight lang="C"> #include<iostream> using namespace std; struct vert { char neighbour[20]; int nn; char name; int color; int d; char pi; }; void bfs(char sta...") |
Arjun Suresh (talk | contribs) |
||
| Line 22: | Line 22: | ||
int i; | int i; | ||
for(i = 0; i < vi; i++) | for(i = 0; i < vi; i++) | ||
| − | if(vertex[i].name==a) | + | if(vertex[i].name == a) |
return i; | return i; | ||
return 0; | return 0; | ||
| Line 30: | Line 30: | ||
{ | { | ||
char b, a,start; | char b, a,start; | ||
| − | int c,d,i,u; | + | int c, d, i, u; |
| − | cout<<"Enter the edges\n0 to stop:\n "; | + | cout << "Enter the edges\n0 to stop:\n "; |
while(1) | while(1) | ||
{ | { | ||
| Line 40: | Line 40: | ||
cin >> b; | cin >> b; | ||
c = 0,d = 0; | c = 0,d = 0; | ||
| − | for(i =0 ;i < vi;i++) | + | for(i = 0 ; i < vi; i++) |
{ | { | ||
if(a == vertex[i].name) | if(a == vertex[i].name) | ||
| Line 55: | Line 55: | ||
if(c == 0) | if(c == 0) | ||
{ | { | ||
| − | vertex[vi].name=a; | + | vertex[vi].name = a; |
| − | vertex[vi].nn=0; | + | vertex[vi].nn = 0; |
| − | vertex[vi++].neighbour[vertex[vi].nn++]=b; | + | vertex[vi++].neighbour[vertex[vi].nn++] = b; |
} | } | ||
if(d == 0) | if(d == 0) | ||
| Line 133: | Line 133: | ||
} | } | ||
} | } | ||
| − | while(top>0) | + | while(top > 0) |
{ | { | ||
u = stack[--top]; | u = stack[--top]; | ||
<syntaxhighlight lang="C">
using namespace std;
struct vert { char neighbour[20]; int nn; char name; int color; int d; char pi; };
void bfs(char start); void dfs(char start); int vi = 0; vert vertex[20];
int findi(char a) { int i; for(i = 0; i < vi; i++) if(vertex[i].name == a) return i; return 0; }
int main() { char b, a,start; int c, d, i, u;
cout << "Enter the edges\n0 to stop:\n "; while(1) { cin >> a; if(a == '0') break; cin >> b; c = 0,d = 0; for(i = 0 ; i < vi; i++) { if(a == vertex[i].name) { vertex[i].neighbour[vertex[i].nn++] = b; c++; } if(b == vertex[i].name) { vertex[i].neighbour[vertex[i].nn++] = a; d++; } } if(c == 0) { vertex[vi].name = a; vertex[vi].nn = 0; vertex[vi++].neighbour[vertex[vi].nn++] = b; } if(d == 0) { vertex[vi].name = b; vertex[vi].nn = 0; vertex[vi++].neighbour[vertex[vi].nn++] = a; } } cout << "Enter the starting vertex: "; cin >> start; bfs(start); cout << endl; dfs(start); }
void bfs(char start) { int i; int front = 0, back = 0, u; int queue[50]; for(i = 0; i < vi; i++) { if(vertex[i].name == start) { vertex[i].color = 1; vertex[i].d = 0; vertex[i].pi = 0; queue[back++] = i; } else { vertex[i].color = 0; vertex[i].d = -1; vertex[i].pi = 0; } } while(front < back) { u = queue[front++]; cout << vertex[u].name <<"\t"; for(i = 0; i<vertex[u].nn; i++) { if(vertex[findi(vertex[u].neighbour[i])].color == 0) { vertex[findi(vertex[u].neighbour[i])].color = 1; vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d+1; vertex[findi(vertex[u].neighbour[i])].pi = vertex[u].pi; queue[back++] = findi(vertex[u].neighbour[i]); } } vertex[u].color = 2; } }
void dfs(char start) { int i; int top = 0,u; int stack[50]; for(i = 0;i < vi; i++) { if(vertex[i].name == start) { vertex[i].color = 1; vertex[i].d = 0; vertex[i].pi = 0; stack[top++] = i; } else { vertex[i].color = 0; vertex[i].d = -1; vertex[i].pi = 0; } } while(top > 0) { u = stack[--top]; cout << vertex[u].name << "\t"; for(i = 0;i < vertex[u].nn; i++) { if(vertex[findi(vertex[u].neighbour[i])].color == 0) { vertex[findi(vertex[u].neighbour[i])].color = 1; vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d+1; vertex[findi(vertex[u].neighbour[i])].pi = vertex[u].pi; stack[top++] = findi(vertex[u].neighbour[i]); } } vertex[u].color = 2; } }
</syntaxhighlight>
<syntaxhighlight lang="C">
using namespace std;
struct vert { char neighbour[20]; int nn; char name; int color; int d; char pi; };
void bfs(char start); void dfs(char start); int vi = 0; vert vertex[20];
int findi(char a) { int i; for(i = 0; i < vi; i++) if(vertex[i].name==a) return i; return 0; }
int main() { char b, a,start; int c,d,i,u;
cout<<"Enter the edges\n0 to stop:\n "; while(1) { cin >> a; if(a == '0') break; cin >> b; c = 0,d = 0; for(i =0 ;i < vi;i++) { if(a == vertex[i].name) { vertex[i].neighbour[vertex[i].nn++] = b; c++; } if(b == vertex[i].name) { vertex[i].neighbour[vertex[i].nn++] = a; d++; } } if(c == 0) { vertex[vi].name=a; vertex[vi].nn=0; vertex[vi++].neighbour[vertex[vi].nn++]=b; } if(d == 0) { vertex[vi].name = b; vertex[vi].nn = 0; vertex[vi++].neighbour[vertex[vi].nn++] = a; } } cout << "Enter the starting vertex: "; cin >> start; bfs(start); cout << endl; dfs(start); }
void bfs(char start) { int i; int front = 0, back = 0, u; int queue[50]; for(i = 0; i < vi; i++) { if(vertex[i].name == start) { vertex[i].color = 1; vertex[i].d = 0; vertex[i].pi = 0; queue[back++] = i; } else { vertex[i].color = 0; vertex[i].d = -1; vertex[i].pi = 0; } } while(front < back) { u = queue[front++]; cout << vertex[u].name <<"\t"; for(i = 0; i<vertex[u].nn; i++) { if(vertex[findi(vertex[u].neighbour[i])].color == 0) { vertex[findi(vertex[u].neighbour[i])].color = 1; vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d+1; vertex[findi(vertex[u].neighbour[i])].pi = vertex[u].pi; queue[back++] = findi(vertex[u].neighbour[i]); } } vertex[u].color = 2; } }
void dfs(char start) { int i; int top = 0,u; int stack[50]; for(i = 0;i < vi; i++) { if(vertex[i].name == start) { vertex[i].color = 1; vertex[i].d = 0; vertex[i].pi = 0; stack[top++] = i; } else { vertex[i].color = 0; vertex[i].d = -1; vertex[i].pi = 0; } } while(top>0) { u = stack[--top]; cout << vertex[u].name << "\t"; for(i = 0;i < vertex[u].nn; i++) { if(vertex[findi(vertex[u].neighbour[i])].color == 0) { vertex[findi(vertex[u].neighbour[i])].color = 1; vertex[findi(vertex[u].neighbour[i])].d = vertex[u].d+1; vertex[findi(vertex[u].neighbour[i])].pi = vertex[u].pi; stack[top++] = findi(vertex[u].neighbour[i]); } } vertex[u].color = 2; } }
</syntaxhighlight>
GATECSE