X si 0

#include"stdio.h"
#include"stdlib.h"

#define B_SIZE 3
#define WIN 10000
#define LOSS -10000
#define DRAW 0
#define OCHAR(ch) ((ch=='X')?'O':'X')

char gameboard[3][3] =
{' ',' ',' ',
' ',' ',' ',
' ',' ',' '
};

int curX,curY;
int nodesSearched;

void clrscr(void)
{
#ifdef __linux__
system("clear");
#else
system("CLS");
#endif
}

// Draws the game board accourding to the accupancy matrix
void DrawBoard(char board[3][3])
{
printf("\n 0 1 2\n +-+-+-+\n");
for(int i=0; i < B_SIZE;i++)
{
printf("%d ",i);
for(int j=0; j < B_SIZE;j++)
printf("|%c",board[i][j]);
printf("|\n +-+-+-+\n");
}
}

// Evaluates the win
int CheckStatus(char board[3][3],char ch)
{
int i,j,ord;
for(i=0; i < B_SIZE;i++)
{
ord=0;
for(j=0; j < B_SIZE;j++)
{
if(board[i][j]==ch) ord++;
else break;
}
if(ord==3) return 1;
}
ord=0;
for(i=0; i < B_SIZE;i++)
{
ord=0;
for(j=0; j < B_SIZE;j++)
{
if(board[j][i]==ch) ord++;
else break;
}
if(ord==3) return 1;
}
ord=0;
for(i=0;i < B_SIZE;i++)
if(board[i][i]==ch) ord++;
if(ord==3) return 1;
else ord=0;
for(i=0; i < B_SIZE;i++)
if(board[i][B_SIZE-i-1]==ch) ord++;
if(ord==3) return 1;
return 0;
}

int Negamax(char board[3][3],int occ,int depth,char ch)
{
int score, max=LOSS;
int i,j;
nodesSearched++;
if(CheckStatus(board,ch)==1) return WIN*(10-depth); //*(10-depth) is there so we choose the shortest path to victory
else if(CheckStatus(board,OCHAR(ch))==1) return LOSS*(10-depth);
else if(occ>=9) return DRAW;
for(i=0; i < B_SIZE;i++)
for(j=0;j < B_SIZE;j++)
if(board[j][i]==' ')
{
board[j][i]=ch;
score=-Negamax(board,occ+1,depth+1,OCHAR(ch));
board[j][i]=' ';
if(score > max)
{
max=score;
if(depth==0)
{
curX=i;
curY=j;
}
}
}
return max;
}

int AlphaBeta(char board[3][3],int occ,int depth,int alpha,int beta,char ch)
{
int score,bestscore=LOSS;
int i,j;
nodesSearched++;
if(CheckStatus(board,ch)==1) return WIN*(10-depth); //*(10-depth) is there so we choose the shortest path to victory
else if(CheckStatus(board,OCHAR(ch))==1) return LOSS*(10-depth);
else if(occ>=9) return DRAW;
for(i=0; i < B_SIZE;i++)
for(j=0; j < B_SIZE;j++)
if(board[j][i]==' ')
{
board[j][i]=ch;
score=-AlphaBeta(board,occ+1,depth+1,-beta,-alpha,OCHAR(ch));
board[j][i]=' ';
if(score > beta) return score; // beta cutoff
if(score > bestscore)
{
bestscore=score;
if(depth==0)
{
curX=i;
curY=j;
}
if(score>alpha) alpha=score;
}
}
return bestscore;
}

int main()
{
int x,y,occ=0;
char mych='X',winner=0;
do
{
clrscr();
DrawBoard(gameboard);
printf("Previous move explored %d nodes\nIntroduce (x,y) coordinates:\n",nodesSearched);
scanf("%d",&y);
scanf("%d",&x);
if(x>=B_SIZE || x<0>=B_SIZE || y<0 || gameboard[y][x]!=' ') continue;

gameboard[y][x]=mych;
if(CheckStatus(gameboard,mych))
{
winner=mych;
continue;
}
if((++occ)>=9) break;

nodesSearched=0;
//Negamax(gameboard,occ,0,OCHAR(mych));
AlphaBeta(gameboard,occ,0,LOSS*11,WIN*11,OCHAR(mych));

gameboard[curY][curX]=OCHAR(mych);
if(CheckStatus(gameboard,OCHAR(mych)))
{
winner=OCHAR(mych);
continue;
}
if((++occ)>=9) break;

}while(!winner);
clrscr();
DrawBoard(gameboard);
printf("\n\nWinner is %c",winner);
return 0;
}

Exercitii Prolog

% daca o lista e palindroma

is_palindrome(L) :- reverse(L,L).

% daca un numar este prim
radacina(X, Y):-
N is Y*Y, N =< X, X mod Y =:= 0.
radacina(X, Y):-
Y < X, Y1 is Y + 1, radacina(X, Y1).
prim(X):-
Y is 2, X > 1 , \+radacina(X, Y).

% duplicarea elem unei liste
dupli([],[]).
dupli([X|Xs],[X,X|Ys]) :- dupli(Xs,Ys).

se aplica: dupli([1,2,3], L).

% o lista care contine toate elementele intre 2 limite

range(I,I,[I]).
range(I,K,[I|L]) :- I < K, I1 is I + 1, range(I1,K,L).

se aplica: range(1,5, L).

altele

Quicksort (Haskell)

module Quick_sort where

partition p [] = ([],[])

partition p (x:rest) = if p x then (x:l,r) else (l,x:r)

where (l,r) = partition p rest

{-

sau

partition p (x:rest)

| p x = (x:l,r)

| otherwise = (l,x:r)

where (l,r)= partition p rest

-}

-- Varianta 1

qsort [] = []

qsort (x:ls) = qsort l ++ [x] ++ qsort r

where (l,r) = partition (<= x) ls

-- Varianta 2

qs [] = []

qs (x:ls) = qs l ++ [x] ++ qs r

where l = [y | y <- ls, y <= x]

r = [y | y <- ls, y > x]

-- Varianta 3

qss [] = []

qss (x:ls) = let l = [y | y <- ls, y <= x]

r = [y | y <- ls, y > x]

in qss l ++ [x] ++ qss r

Problema reginelor in Clips

; Placing N non-attacking queens on a NxN chessboard

; ==================================================

; CGA 2009

(deftemplate board (slot id) (slot free_line) (multislot queens))

; chessboard = (board (id an_id) (free_line l) (queens [1 c1 ] [ 2 c2 ] ... [ N cN ] ))

(defrule read_size

=>

(printout t "Board size: ")

(bind ?n (read))

(assert (board (id (gensym)) (free_line ?n) (queens))

(solutions 0))

(if (> ?n 0) then (assert (column ?n))))

(defrule lines_and_columns

(column ?n&~1)

=>

(assert (column (- ?n 1))))

(defrule place_queen

(board (id ?id) (free_line ?l&~0) (queens $?q))

(column ?c)

(not (board (id ?id)

(queens $? [ ?lq ?cq&:(or (= ?cq ?c) (= (- ?lq ?l) (abs (- ?cq ?c)))) ] $?)))

=>

(assert (board (id (gensym)) (free_line (- ?l 1)) (queens [ ?l ?c ] $?q))))

(defrule solution

?f <- (board (free_line 0) (queens $?q))

?g <- (solutions ?c)

=>

(retract ?f ?g)

(assert (solutions (+ ?c 1)))

(printout t $?q crlf))

(defrule print_count

(declare (salience -10))

(solutions ?n)

=>

(printout t ?n " solutions" crlf))

Prolog

parent(andrew, bob).

parent(andrew, beth).

parent(bob, carlos).

parent(beth, cindy).

grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

mylast(X, [X]).

mylast(X, [_|T]) :- mylast(X, T).

Determinati penultimul element al unei liste. Exemplu:

?- before_last(X, [1, 2, 3]). X = 2

before_last(X, [X,Y]).

before_last(X, [_|T]) :- before_last(X, T).

Determinati elementul de indice k dintr-o lista. Exemplu:

?- kth(X, 3, [4, 3, 2]). X = 2

kth(X,1,[X|T]).

kth(X,K,[Y|L]) :- Z is K-1 , kth(X,Z,L).

Determinati lungimea unei liste. Exemplu:

?- len(X, [1, 2, 3]). X = 3

len(0, []).

len(X, [H|T]) :- len(Z, T) , X is Z+1.

Concatenati doua liste. Exemplu:

?- concat([1, 2], [3], L). L = [1, 2, 3]

concat([], L, L).

concat([H|T],X,[H|L]) :- concat(T, X, L).

Inversati o lista. Exemplu:

?- rev([1, 2, 3], L). L = [3, 2, 1]

put(X,L,V) :- concat(L,[X],V).

inver([],[]).

inver([H|T], L) :- inver(T,B) , put(H,B,L).

Partitiile unui numar in Haskell si Clips

_____________________HUSKELL________________________

leng [] = 0

leng (a:list) = 1 + leng list

-- ret o lista in care elem de pe poz poz_start si poz_start+1 sunt alipite,adunate

sm list poz_start 1 = []

sm (a:list) poz_start i =

if(i==poz_start) then (a+(head list)):(sm (tail list) poz_start (i-1))

else a:(sm list poz_start (i-1))

find lista poz_start = sm lista (leng lista - poz_start + 1) (leng lista)

-- genereaza toate astfel de combinari (pot fi duplicate)

genComb list k =

if(k<=(leng list - 1)) then (find list k):(genComb list (k+1))

else []

genC lista = genComb lista 1

-- eliminare duplicate de tip lista dintr-o lista

-- daca un element e membru intr-o lista

member x [] = False

member x (h:t) =

if (h == x) then True

else member x t

-- sterge element dintr-o lista

del x (a:list) =

if (x==a) then list

else a:(del x list)

-- daca doua liste sunt egale

eg [] list = True

eg (a:l1) l2 =

if (member a l2 == True) then eg l1 (del a l2)

else False

egale l1 l2 =

if (leng l1 == leng l2 && (eg l1 l2 == True)) then True

else False

-- daca o lista exista intr-o lista de liste

exista l [] = False

exista l (b:lista) =

if (egale l b == True) then True

else exista l lista

-- elimina duplicate

elimd [] = []

elimd (a:list) =

if(exista a list) then elimd list

else a:(elimd list)

generate list = elimd(genC list)

-- adauga la o lista de liste o noua lista

alipire [] list = [list]

alipire (a:l) list =

a:(alipire l list)

-- genereaza partitii pt o lista cu lungime admisa

gen_size list size =

if(size == leng list) then generate list

else []

-- gen partitiile pt toate listele de o anumita lungime dintr-o lista de liste

gen [] size = []

gen (a:list_of_lists) size =

(gen_size a size)++(gen list_of_lists size)

gen_final list 1 = list

gen_final list n =

gen_final ((gen list n)++list) (n-1)

-- n scris ca "suma" de n elem de 1

equiv 0 = []

equiv n =

1:(equiv (n-1))

result 0 = [[0]]

result n =

(elimd (gen_final (generate (equiv n)) n))++[(equiv n)]

-- se apeleaza: result n

_____________________ CLIPS ____________________

(deftemplate partitie (multislot p) )

(deffacts facts (p ) (n 5)) ; n reprezinta numarul pt partitionat

; scrie nr n de forma (p 1 1 ... 1) = prima partitie

(defrule init

?q <- (n ?x)

?r <- (p $?a)

(test (> ?x 0))

=> (retract ?q)

(assert (n (- ?x 1)))

(retract ?r)

(assert (p $?a 1))

)

; creeaza partitii cu tot cu duplicate

(defrule adds

(p $?a ?b ?c $?d)

=> (assert (p $?a (+ ?b ?c) $?d))

)

; sterge partitiile care contin nr descrescatoare (si elimina duplicate)

(defrule delete

?q <-(p $?a ?b ?c $?d)

(test ( > ?b ?c))

=>(retract ?q)

)

; partitiile se pot vedea in (facts)

; (p .....)

Problema reginelor in Scheme

; Generatori de solutii si cele N regine

(define dfs

(lambda (init expand test)

(letrec ((search (lambda (border)

(cond ((null? border) '())

((test (car border)) (cons (car border)

(delay (search (cdr border)))))

(else (search (append (expand (car border))

(cdr border))))))))

(search (list init)))))

; ======= n Regine ========

; tabla de sah = ((linie_i . coloana_i) ... (linie_1 . colana_1))

; unde (linie_i . coloana_i) este pozitia reginei i pe tabla de sah

; (expand n)

; - primeste o tabla de sah cu primele i regine pozitionate corect

; - reintoarce lista tablelor de sah pe care este pozitionata regina i+1

(define expand

(lambda (n)

(lambda (board)

(let ((l (+ (length board) 1)))

(foreach (columns 1 n)

(lambda (c) (not (attack l c board)))

(lambda (c) (cons (cons l c) board)))))))

; (attack l c board)

; - primeste l c = pozitia unei noi regine

; board = o tabla de sah pe care sunt deja pozitionate corect

; reginele l-1, l-2,...1

; - reintoarce #t daca regina l este pozitionata corect

(define attack

(lambda (l c board)

(exists (lambda (queen)

(let ((lq (car queen)) (cq (cdr queen)))

(or (= c cq) (= (- l lq) (abs (- c cq))))))

board)))

; (exists p l) = #t daca in lista l exista un element care satisface predicatul p

(define exists

(lambda (p l)

(cond ((null? l) #f)

((p (car l)) #t)

(else (exists p (cdr l))))))

; (foreach set predicate fun) =

; lista tuturor elementelor din set (o lista), care satisfac predicatul pred,

; prelucrate prin fun

(define foreach

(lambda (set pred fun)

(cond ((null? set) '())

((pred (car set)) (cons (fun (car set))

(foreach (cdr set) pred fun)))

(else (foreach (cdr set) pred fun)))))

(define columns

(lambda (inf sup)

(if (> inf sup) '()

(cons inf (columns (+ 1 inf) sup)))))

(define queens

(lambda (n)

(dfs '() (expand n) (lambda (board) (= (length board) n)))))

(define hd car)

(define tl (lambda (s) (force (cdr s))))

(define take

(lambda (n s)

(if (or (zero? n) (null? s)) '()

(cons (hd s) (take (- n 1) (tl s))))))

(define drop

(lambda (n s)

(if (or (zero? n) (null? s)) s

(drop (- n 1) (tl s)))))

(define queens5 (queens 5))

(define queens8 (queens 8))

(define gen-gen

(lambda (s) ; s = fluxul solutiilor unei probleme

(lambda (n)

(let ((sols (take n s)))

(set! s (drop n s))

sols))))

(define gen-gen-queens

(lambda (gen)

(lambda (n)

(map (lambda (tabla) (map cdr tabla)) (gen n)))))

(define q5 (gen-gen queens5))

(define q5bis (gen-gen queens5))

(define q8 (gen-gen queens8))

(define qq5 (gen-gen-queens q5))

Grafuri in Scheme - ciclicitate

; a si b sunt grafuri

(define a '((0 1 2 3)((0 1 1 0) (1 0 0 1) (1 0 0 1) (0 1 1 0))))

(define b '((0 1 2 3)((0 0 1 0) (0 0 0 1) (1 0 0 1) (0 1 1 0))))

; reprezentarea grafului e (noduri matDeAdiac)

; o lista care are 2 liste

; prima lista e cea cu nodurile (0 1 2 3)

; e folosita pt parcurgerea grafului din toate nodurile

; a 2-a lista e o lista de liste cu 0 si 1

(define pos

(lambda(l n)

(if(= n 0) (car l)

(pos (cdr l) (- n 1)))))

(define ap1

(lambda(a n)

(if(null? a) '()

(if(= 1 (car a))

(cons n (ap1 (cdr a) (+ n 1)))

(ap1 (cdr a) (+ n 1))))))

(define vecini

(lambda(a n)

(ap1 (pos a n) 0)))

(define in

(lambda(l x)

(if(null? l) #f

(if(= x (car l)) #t

(in (cdr l) x)))))

(define fct

(lambda (a l)

(lambda(x)

(parc a x l))))

(define map2

(lambda(l f)

(if(null? l) '()

(cons (f (car l)) (map2 (cdr l) f)))))

; cut scoate un element dintr-o lista

; (cut '(1 2 3 4) 1) retureaza (2 3 4)

; e folosita de functia pt parcurgere

; daca ajung in nodul u din nodul v (v e vecin cu u) si il scot din lista de vecin

(define cut

(lambda(l x)

(if(null? l) '()

(if(= x (car l)) (cut (cdr l) x)

(cons (car l) (cut (cdr l) x))))))

; functia parc parcurge graful dintr-un nod si mentine o lista despre originea grafului (cum a aparut)

; apoi isi ia vecinii si il ignora pe cel din care am venit eu, si reapeleaza functia pt ce a ramas

; daca nodul e in lista din care a venit inseamna ca e ciclu

; daca nu mai sunt vecini, nu e ciclu pe ramura asta a dfs-ului

(define parc

(lambda(a n l)

(if(in l n) #t

(if(null? (cut (vecini a n) (car l))) #f

(map2 (cut (vecini a n) (car l)) (fct a (cons n l)))))))

(define ciclu

(lambda(a)

(map2 (car a) (fct (cadr a) '(-1)))))

(ciclu a)

(ciclu b)

Generarea mai multor numere prime in Scheme

; verificam daca x se divide cu y

(define divides?

(lambda (x y)

(zero? (remainder x y)))) ; remainder x y <=> x modulo y

; definitiile pentru fluxul numerelor naturale

(define succ

(lambda (n)

(+ n 1)))

(define make_naturals

(lambda (k)

(cons k (delay (make_naturals (succ k))))))

; definim fluxul numerelor naturale incepand de la 2

(define naturals_from_2 (make_naturals 2))

; functia take

(define take

(lambda (n stream)

(if (zero? n) '()

(cons (car stream) (take (- n 1) (force (cdr stream)))))))

; functie care primeste un flux, si intoarce un flux filtrat, dupa functia f

(define filt

(lambda (f s) ; parametrii sunt functia de filtrare, si fluxul

(if (f (car s))

(cons (car s) (delay (filt f (force (cdr s)))))

(filt f (force (cdr s))))))

; functia de cernere (sita)

(define sieve

(lambda (s)

(cons (car s)

(delay (sieve (filt

(lambda (x) (not (divides? x (car s))))

(force (cdr s))))))))

; definitia fluxului

(define primes_stream (sieve naturals_from_2))

; testare

(take 10 primes_stream) ; va intoarce (2 3 5 7 11 13 17 19 23 29)

Inversarea unei liste in Clips

; inversarea unei liste

(deffacts siruri

(sirul 1 este Ion o iubeste pe Maria)

(sirul 2 este 1 2 3 4 5 6)

(sirul 3 este a b c d e f g)

)

(defrule pune-markeri

?f <- (sirul ?id este $?continut)

(not (sirul ?id a fost luat in considerare))

=> (retract ?f)

(assert (sirul ?id este # $?continut #)

(sirul ?id a fost luat in considerare))

)

(defrule inversare

?f <- (sirul ?id este $?ceva1 # ?x $?ceva2 ?y # $?ceva3)

=> (retract ?f)

(assert (sirul ?id este $?ceva1 ?y # $?ceva2 # ?x $?ceva3))

)

(defrule terminare

(declare (salience -10))

?f <- (sirul ?id este $?ceva1 # $?ceva2)

=> (retract ?f)

(assert (sirul ?id este $?ceva1 $?ceva2))

)

Problema de decodificare in Verilog

Sa se proiecteze un sistem care decodifica un sir de biti conform arborelui prezentat in

continuare (bazat pe probabilitatile de aparitie):

/* Din desen rezulta urmatoarele codificari:

A - 0, B - 100, C - 101, D - 110, E - 111

=> 5 simboluri + un eventual simbol invalid => iesirea va fi pe 3 biti

*/

Rezolvare (modulul verilog):

`timescale 1ns / 1ps

module rezolvare(

input clk,

input clr,

input din,

output reg valid,

output reg [2:0] dout

);

// li se ofera valori oarecare, nu conteaza

localparam A=3'd0;

localparam B=3'd1;

localparam C=3'd2;

localparam D=3'd3;

localparam E=3'd4;

localparam invalid=3'd7;

reg [1:0] state;

always@(posedge clk or negedge clr)

if (~clr) begin

state <= 0;

valid <= 0;

dout <= invalid;

end

else

case (state)

2'd0 : if (din) begin // starea 0 , cand primeste primul bit de la intrare

valid <= 0; // cand din == 1, nu exista un simbol valid S = 1

dout <= invalid;

state <= 1;

end

else begin // cand bitul primit din == 0, dout = A = 1

valid <= 1;

dout <= A;

state <= 0;

end

2'd1 : if (din) begin // 2'd1 corespunde starii din care se poate ajunge in 10 sau 11

valid <= 0;

dout <= invalid; // 11 nu este un simbol valid

state <= 3;

end

else begin

valid <= 0;

dout <= invalid; // nici 10

state <= 2;

end

2'd2 : if (din) begin // 2'd2 corespunde starii din care se poate ajunge in 100 sau 101

valid <= 1;

dout <= C; // 101 inseamna 'C'

state <= 0;

end

else begin

valid <= 1;

dout <= B; // 100 inseamna 'B'

state <= 0;

end

2'd3 : if (din) begin // 2'd3 corespunde starii din care se poate ajunge in 110 sau 111

valid <= 1;

dout <= E; // 111 inseamna 'E'

state <= 0;

end

else begin

valid <= 1;

dout <= D; // 110 inseamna 'D'

state <= 0;

end

endcase

endmodule

Tutorial de Electronica :-)

+ altele la Related videos

Noduri critice intr-un graf

Folosind algoritmul pentru nodurile critice :

Considerăm că avem un graf (neorientat și conex) cu N noduri si M muchii. Un nod al grafului se numește critic dacă prin eliminarea lui din graf (și a muchiilor adiacente cu acest nod), graful nu mai rămâne conex. Ne punem problema de a determina care sunt nodurile critice ale unui graf (aceasta este o problemă care apare des în practică, deoarece multe structuri pot fi modelate cu ajutorul grafurilor, iar nodurile critice pot reprezenta punctele vulnerabile ale acestor structuri).

Pași de execuție

Se face o parcurgere DF dintr-un nod oarecare al grafului, pe care îl vom numi în continuare nod rădăcină. Știm că o parcurgere DF determină un arbore parțial de acoperire al grafului, având rădăcină în nodul rădăcină. În cadrul parcurgerii, vom calcula nivelul pe care se află fiecare nod (nivelul rădăcinii este 1, iar nivelul fiecărui nod este egal cu nivelul nodului tată plus 1). Ca urmare a unei parcurgeri DF, muchiile grafului pot fi împărțite în două categorii : muchii ce fac parte din arborele DF (muchii înainte sau muchii directe) și muchii ce nu fac parte din acest arbore (muchii de întoarcere, muchii înapoi sau muchii inverse). Pentru fiecare nod vom calcula, pe langa nivelul acestuia, și nivelul minim la care poate ajunge nodul respectiv mergând numai pe muchii directe din subarborele său din cadrul arborelui DF și folosind ca ultima muchie o muchie inversă. Acestă valoare, pe care o vom numi nivelul minim accesibil este egală cu minimul dintre urmatoarele 3 valori :

• nivelul nodului curent
• minimul dintre nivelurile nodurilor cu care este legat nodul curent printr-o muchie inversă
• minimul dintre nivelurile minime accesibile ale fiiilor nodului curent din cadrul arborelui DF

Se poate observa ușor că un nod (diferit de rădăcină) este critic dacă are cel puțin un fiu pentru care nivelul minim accesibil este mai mare sau egal cu nivelul nodului. Rădăcina este nod critic dacă are cel puțin 2 fii.

=== Implementare in C ===

#include "stdio.h"

int n, a[20][20], viz[20];

void citire()
{ FILE * f = fopen("neorientat","r");
fscanf(f,"%d", &n); int i,j;
while(!feof(f))
{ fscanf(f,"%d %d", &i, &j);
a[i][j]=1; a[j][i]=1;
a[i][i]=1; a[j][j]=1; }
}

/* Determinarea nodurilor critice pt graf neorientat */

void df(int vf)
{ int i; viz[vf]=1;
for(i=1; i<=n; i++)
if(a[vf][i]==1 && viz[i]==0)
df(i);
}

int conex()
{ int i, p=0;
for (i=1; i<=n; i++)
if(viz[i]==0)
{ df(i); p++; }
if(p==1)
return 1;
return 0;
}


int main()
{ int i,j;
citire();
printf("Noduri critice: ");
for(i=1;i<=n;i++) //elimin fiecare nod
{ for(j=1;j<=n;j++)
if(a[i][j]==1)
{ a[i][j]=2; a[j][i]=2; }
if(i==n)
df(i-1);
else
df(i+1);
if(!conex())
printf("%d ", i) ;
for(j=1;j<=n;j++)
if(a[i][j]==2)
{ a[i][j]=1; a[j][i]=1; }
for(j=1;j<=n;j++)
viz[j]=0;
}
printf("\n");
return 0;
}

Componentele tare conexe ale unui graf orientat

Folosind "Roy-Warshall"

#include "stdio.h"

int n, a[20][20], viz[20], d[20][20];

void citire()
{ FILE * f = fopen("proba","r");
fscanf(f,"%d", &n); int i,j;
while(!feof(f))
{ fscanf(f,"%d %d", &i, &j);
a[i][j]=1; d[i][j]=1;
a[i][i]=1; d[i][i]=1;
a[j][j]=1; d[j][j]=1; }
}

/* afisarea componentelor tare conexe */

int conex_tare()
{ /* Roy Warshall */
int i,j,k;
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(d[i][k] && d[k][j])
d[i][j]=1;

int ok=1;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if(d[i][j]==0)
ok=0;
return ok;
}

void df(int vf)
{ int i; viz[vf]=1;
printf("%d ",vf); //afisare
for(i=1; i<=n; i++)
if((d[vf][i]==1 && d[i][vf]) && viz[i]==0)
df(i);
}


int main()
{ citire();
if(conex_tare())
printf("este tare conex\n");
else printf("nu este tare conex\n");
int i;
df(1);
for (i=1; i<=n; i++)
if(viz[i]==0)
{ printf("\n"); df(i); }
printf("\n");
return 0;
}

Componentele conexe ale unui graf neorientat

Program in C care afla componentele conexe dintr-un graf neorientat, folosind o parcurgere DFS. Din fisierul graf.txt se citesc numarul de noduri si perechile de noduri reprezentand fiecare muchie.

#include "stdio.h"

int n, a[20][20], viz[20];

void citire()
{ FILE * f = fopen("graf.txt","r");
fscanf(f,"%d", &n); int i,j;
while(!feof(f))
{ fscanf(f,"%d %d", &i, &j);
a[i][j]=1; a[j][i]=1; a[i][i]=1; a[j][j]=1; }
}

/* afisare componente conexe pt graf neorientat */

void df(int vf)
{ int i; viz[vf]=1;
printf("%d ",vf); //afisare
for(i=1; i<=n; i++)
if(a[vf][i]==1 && viz[i]==0)
df(i);
}


int main()
{ int p,i; p=0;
citire();
for (i=1; i<=n; i++)
if(viz[i]==0)
{ df(i); printf("\n"); p++; }
if(p==1)
printf(" graf conex\n");
else
printf("are %d componente conexe\n", p);
return 0;
}

Algoritmul lui Kruskal, folosind operatii cu multimi disjuncte

Arborele minim de acoperire (AMA) pentru un graf se defineste pentru grafuri neorientate si conexe (toate nodurile grafului se afla in aceeasi componenta conexa).

Dandu-se un graf conex si neorientat G=(V, E), unde V = multimea nodurilor, iar E multimea muchiilor grafului G, se numeste arbore minim de acoperire un graf conex si neorientat G' = (V, E'), unde E' inclus in E cu proprietatile:
- G' este este un arbore (graf aciclic);
- suma costurilor muchiilor din E' sa fie minima.

Dintre algoritmii clasici care se ocupa de determinarea arborelui minim de acoperire amintim: algoritmul Kruskal si algoritmul Prim.

=== Pseudocod ===

Fie G=(V, E), graf neorientat si conex
1) AMA = multimea vida
2) Pentru fiecare nod din V
creeaza_multime(v)
3) Sorteaza muchiile din E crescator dupa cost
4) Pentru fiecare muchie (u, v) din E in ordine crescatoare
- Daca gaseste_multime(u) != gaseste_multime(v)
a) Se adauga muchia (u, v) in AMA
b) reuneste(u, v)

=== Implementare in C ===

#include "stdio.h"
#include "stdlib.h"
#define MAX 100
#define INF -1

int n,m,**b;
typedef struct multime {
int c; //contorul multimii
int S[MAX]; //elementele multimii
} Set;

typedef struct muchie {
int x; int y; int cost;
} Muchie;

Muchie mu[MAX];
Set C[MAX]; //colectia
int nset; //nr de seturi

void citire()
{ FILE *f=fopen("in","r");
fscanf(f,"%d",&n);
int i,j,k,cost;
fscanf(f,"%d",&m); //nr muchii
for(i=0;i<=m-1;i++)
{ fscanf(f,"%d %d %d",&j,&k,&cost); mu[i].x=j; mu[i].y=k; mu[i].cost=cost; }
}


/* functii pt multimi disjuncte */

void Make_Set (int n)
{ int i; nset=n;
for(i=0; i<=n-1; i++)
{ C[i].c=1;
C[i].S[0]=i; }
}

void Print_Set()
{ int i,j;
for(i=0; i<=nset-1; i++)
{ for(j=0; j<=C[i].c-1 ; j++)
printf("%d ",C[i].S[j]);
printf("\n"); }
}

//identific a cata multime este multimea in care se afla un element
int Find(int x)
{ int j,i;
for(i=0;i<=nset-1;i++) // pt fiecare set
{ for(j=0; j<=C[i].c-1; j++)
if(x==C[i].S[j])
return i;
}
return -1;
}


void Set_Union(int a,int b) // reuniunea se face in C[a],se sterge C[b]
{ int i;
for(i=0;i<=C[b].c-1;i++)
if(Find(C[b].S[i])!=a)
{ C[a].S[C[a].c]=C[b].S[i]; C[a].c++; }
for(i=b; i<=nset-1; i++)
C[i]=C[i+1];
nset--;
}

void print_muchii()
{ int i;
for(i=0;i<=m-1;i++)
printf("%d %d %d \n",mu[i].x,mu[i].y,mu[i].cost);
}

Muchie arc_min() //gaseste arcul de cost minim si apoi il sterge!
{ int i,min=mu[0].cost,poz=0;
Muchie x=mu[0];
for(i=1; i<=m-1; i++)
if(mu[i].cost < min)
{ min=mu[i].cost; poz=i; x=mu[i]; }
for(i=poz; i<=m-2; i++)
mu[i]=mu[i+1];
m--;
return x;
}

void kruskal()
{
Make_Set(n);
Muchie a;
int u,v,i,j;
b=(int **)malloc(n*sizeof(int *));
for(i=0; i<=n-1; i++)
b[i]=(int *)malloc(n*sizeof(int));
for(i=0; i<=n-1; i++)
for(j=0; j<=n-1; j++)
{ if(i!=j)
b[i][j]=INF;
else
b[i][j]=0; }

int nm=0;
while (nm < n-1) // cat timp nu am atins n-1 muchii
{ a=arc_min();
u=a.x; v=a.y;
if(Find(u)!=Find(v)) // daca se afla in seturi diferite
{ Set_Union(Find(u),Find(v));
b[u][v]=a.cost; b[v][u]=a.cost; nm++; } //adaug muchie la graf nou
}
}

int *viz;

void afisare(int vf)
{
int i; viz[vf]=1;
printf("%d ",vf);

for(i=0; i<=n-1; i++)
if(b[vf][i]>=0 && viz[i]==0)
afisare(i);
}

void afisare2()
{ int i,j,w;
for(i=0; i<=n-1; i++)
for(j=i+1; j<=n-1; j++)
{ w=b[i][j];
if(w > 0)
printf("muchia %d-%d cost %d\n", i,j, w);
}
}

int main()
{ citire();
kruskal();
viz=(int *)malloc(n*sizeof(int));
int i;
for(i=0; i<=n-1 ;i++)
viz[i]=0;
afisare2();
free(viz);
return 0;
}