[shkola] Graph Algorithms Source

Towa sa source-owete na algoritmite, koito razgledahme!
W skoro wreme ochakwajte i zadachi kxm tqh!!

Ivo

==============================================================

        Ivaylo Riskov    <ivaylo_riskov@xxxxxxx>

        "Stenderup's Law:
           The sooner you fall behind, the more time you will have to 
catch up"

==============================================================

#define MAX_NODES       100
#define INFINITY        1000000000

int adj[MAX_NODES][MAX_NODES];

void DFS(int depth, int node) {
        int i, flag;

        flag = 0;
        for (i = 0; i < MAX_NODES; i++)
                if (adj[node][i]) {
                        //do something here
                        flag = 0;
                        DFS(depth + 1, i);
                        //do something here
                }
        if (!flag) {
                //no adjacent nodes found
                //do some special processing here
        }
}

void BFS(int node) {
        int queue[MAX_NODES];   //NOTE! You man need to hange the size of the 
array
        int i, qe, qb;

        //add the first note to the queue
        qe = qb = 0;
        queue[qe++] = node;

        while (qe > qb) {
                node = queue[qb++];

                //do something here
                for (i = 0; i < MAX_NODES; i++)
                        if (adj[node][i]) {
                                //do something here
                                queue[qe++] = i;
                        }
        }
}

int parent[MAX_NODES];
int visited[MAX_NODES];
int dist[MAX_NODES];

void Dijkstra(int node) {
        int i, min_dist;

        for (i = 0; i < MAX_NODES; i++)
                visited[i] = 0,
                dist[i] = INFINITY;

        dist[node] = 0;

        while (1) {
                //find not visited node with minimal distance
                min_dist = INFINITY;
                for (i = 0; i < MAX_NODES; i++)
                        if (!visited[i] && dist[i] < min_dist)
                                min_dist = dist[i],
                                node = i;

                //no more nodes to visit - return
                if (min_dist == INFINITY)
                        return;

                visited[node] = 1;
                for (i = 0; i < MAX_NODES; i++)
                        if (dist[node] + adj[node][i] < dist[i])
                                dist[i] = dist[node] + adj[node][i],
                                parent[i] = node;
        }
}

void Floyd() {
        int i, j, k;
        
        for (i = 0; i < MAX_NODES; i++)
                for (j = 0; j < MAX_NODES; j++)
                        for (k = 0; k < MAX_NODES; k++)
                                if (adj[i][j] + adj[j][k] < adj[i][k])
                                        adj[i][k] = adj[i][j] + adj[j][k];
}

Other related posts: