سكربت الدروس العربي » القسم التجريبي » test

 test  أضيف في: 8-9-1431هـ
#include <stack>
#include <queue>
#include <stdio.h>
#include <list>
#include <math.h>


using namespace std;




struct graph
{
int vertex_count;
char** vertex;
int** dist;
};


void construct_graph(graph &g, int vertex_count)
{
g.vertex_count = vertex_count;
g.vertex=new char*[vertex_count];
g.dist = new int*[vertex_count];
for (int i = 0; i < vertex_count; i++)
{
g.vertex[i]=new char[2];
g.dist[i] = new int[vertex_count];
for (int j = 0; j < vertex_count; j++)
g.dist[i][j] = 0;
}
}


void add_edge(graph g, int i, int j, int dist) {
if (i >= 0 && i < g.vertex_count && j > 0 && j < g.vertex_count) {
g.dist[i][j] = dist;
g.dist[j][i] = dist;
}
}

void remove_edge(graph g, int i, int j)
{
if (i >= 0 && i < g.vertex_count && j > 0 && j < g.vertex_count)
{
g.dist[i][j] = 0;
g.dist[j][i] = 0;
}
}

bool is_edge(graph g, int i, int j)
{
if (i >= 0 && i < g.vertex_count && j > 0 && j < g.vertex_count)
return g.dist[i][j];
else
return false;
}

int get_unvisited_child_node(graph g, int n, bool visited[])
{


int j=0;
while (j<g.vertex_count)
{
if(g.dist[n][j] && !visited[j]) return j;
j++;
}
return -1;
}

void dfs(graph g, int n)
{
bool visited[g.vertex_count];
//DFS uses Stack data structure
for(int i=0;i<g.vertex_count;i++)visited[i]=0;
stack<int> s;
s.push(n);
visited[n]=true;
printf("%s
",g.vertex[n]);
while(!s.empty())
{
int node=s.top();
int child=get_unvisited_child_node(g, node,visited);
// printf("%d
",child);
if(child!=-1)
{
visited[child]=true;
printf("%s
",g.vertex[child]);
s.push(child);
}
else
{
s.pop();
}
}
// for(int i=0;i<vertexCount;i++) printf("%d",visited[i]);
//Clear visited property of nodes
// clearNodes();
}


void bfs(graph g, int n)
{
bool visited[g.vertex_count];
//BFS uses Queue data structure
for(int i=0;i<g.vertex_count;i++)visited[i]=0;
queue<int> q;
q.push(n);
visited[n]=true;
printf("%s
",g.vertex[n]);
while(!q.empty())
{
int node=q.front();
q.pop();
int child=-1;
child=get_unvisited_child_node(g, node, visited);
while(child!=-1)
{
visited[child]=true;
printf("%s
",g.vertex[child]);
q.push(child);
child=get_unvisited_child_node(g, node,visited);


}

}
}


void destruct_graph(graph &g)
{

for (int i = 0; i < g.vertex_count; i++)
{
delete[] g.dist[i];
delete[] g.vertex[i];
}


delete[] g.dist;
delete[] g.vertex;
g.vertex_count = 0;
}


void printD(int d[], int n) {

for (int i = 0; i < n; i++)
printf("%10d %10d
", i,d[i]);
}


void dijkstra(graph g, int sv, int short_dist[])
{
bool visited[g.vertex_count];


int infinity = pow(g.vertex_count,2);


for (int i = 0; i < g.vertex_count; i++) {

short_dist[i] = infinity;
visited[i] = 0; /* the i-th element has not yet been visited */
}


short_dist[sv] = 0;
int cur=sv;


int rem_vert= g.vertex_count;


for(int k=1; k<=g.vertex_count;k++)
{



int mini = 0;
while(visited[mini]) mini++;

for (int i = 0; i < g.vertex_count; i++) if (!visited[i] && (short_dist[i] < short_dist[mini])) mini = i;


visited[mini] = 1;




for (int i = 0; i < g.vertex_count; i++)
if (g.dist[mini][i])
if (short_dist[mini] + g.dist[mini][i] < short_dist[i])
short_dist[i] = short_dist[mini] + g.dist[mini][i];

}
}




int main()
{
printf("
");


// printf(" adjacency_list before adding edges
");


graph mcho_map;


int vertex_count;
scanf("%d", &vertex_count);




construct_graph(mcho_map, vertex_count);




for(int i=0;i<vertex_count; i++)
{
scanf("%s",mcho_map.vertex[i]);
}

/*
for(int i=0;i<mcho_map.vertex_count;i++) printf(" %s",mcho_map.vertex[i]); //print the matrix header
for(int i=0;i<mcho_map.vertex_count;i++) //outer loop
for(int j=0;j<mcho_map.vertex_count;j++) //inner loop
{
if(j==0) printf("
%s",mcho_map.vertex[i]);//start each line of the matrix in new line.
printf(" %d",mcho_map.dist[i][j]); // printing dist contents.
}*/
add_edge(mcho_map, 0,3,1);


add_edge(mcho_map, 3,1,1);
add_edge(mcho_map, 3,2,1);
add_edge(mcho_map, 2,5,1);
add_edge(mcho_map, 5,4,1);


//add_edge(mcho_map, 1,4,1);


/* printf("
");


printf(" dist after adding edges
");


for(int i=0;i<mcho_map.vertex_count;i++) printf(" %s",mcho_map.vertex[i]);


for(int i=0;i<mcho_map.vertex_count;i++)
for(int j=0;j<mcho_map.vertex_count;j++)
{
if(j==0) printf("
%s",mcho_map.vertex[i]);
printf(" %d",mcho_map.dist[i][j]);
}


printf("
");
*/


//printf("Depth First Search
");
//dfs(mcho_map, 0);


printf("
");


//printf("Breadth First Search
");
//bfs(mcho_map, 0);



int short_dist[mcho_map.vertex_count];


dijkstra(mcho_map, 0, short_dist);


printD(short_dist, mcho_map.vertex_count);
destruct_graph(mcho_map);






return 0;
}
الكاتب: test انقر هنا لمراسلة test أنقر هنا للإنتقال إلى موقع test إضافة للمفضلة إضافة لمفضلة Google إضافة لمفضلة Delicious إضافة لمفضلة Digg إضافة لمفضلة Facebook
خيارات الدرس : ارسل الدرس لصديق ارسل الدرس لصديق  طباعة الدرس طباعة الدرس  حفظ الدرس كملف Word حفظ الدرس كملف Word  حفظ الدرس كملف PDF حفظ الدرس كملف PDF

التعليقات
لا يـوجـد تـعليـقات على هـذا الـدرس