Just a graph algorithm program about Deep First Search that I manage to finish right now during my experiment. Kinda hard to understand since the command is mostly not a language that we use in daily life. I HATE PROGRAMMING...!!!!

huispc1 [67]% vi dfs.c

#define MAX_NUM 30

#include
#include

typedef struct s_vertex{
int name;
struct s_vertex *next;
}VERTEX;

VERTEX *newvertex(void)
{
VERTEX *p;

p = (VERTEX *)malloc(sizeof(VERTEX));
if (p == NULL){
fputs("malloc failed\n", stderr);
exit(1);
}else
return(p);
}

void makelist (VERTEX *adj[], int *v_num)
{
VERTEX *tail, *new;
int a,b;

printf ("頂点数を入力して下さい:");
scanf ("%d",v_num);
printf ("\n各頂点の鄰接点を入力して下さい\n");

for (a = 0; a < *v_num; a++){
printf ("頂点 %d の鄰接点\n", a+1);
tail = NULL;
do{
printf("鄰接点名を入力して下さい:");
scanf("%d",&b);
if (b<0)>
new = newvertex();
new -> name = b;
new -> next = tail;
tail = new;
} while (b >= 0);
adj [a] = tail;
}
}
void printlist (VERTEX *adj[], int v_num)
{
VERTEX *this;
int a;

printf ("---------------------------------------------\n");
printf ("入力されたグラフの表示\n");

for (a = 0; a <>
printf ("%d -->", a+1);
this = adj[a];
while(this != NULL){
printf(" %d ", this->name);
this = this -> next;
}
printf ("\n");
}
}

/*頂点を訪問し、timestamp(発見時刻と終了時刻)を記憶していく*/
void dfs_visit(VERTEX *adj[], int v_num, int visited[], int pi[], int f[], int d[], int *time, int u)
{
VERTEX *this;
int b;

visited[u] = 1;
(*time)++; /*時刻単位を増やす*/
d[u] = *time; /*この頂点の発見時刻を格納*/

this = adj[u-1];
while (this != NULL) {
b = this -> name; /*頂点名を代入*/
if (visited[b] == 0){ /*その頂点が末訪問であれば*/
pi[b] = u; /*prodecessorを記録し*/
dfs_visit(adj, v_num, visited, pi, f, d, time, b ); /*その頂点を訪問し調べる*/
}
this = this -> next;
}

(*time)++;
f[u] = *time;
}

void printstamp (int v_num, int f[], int d[])
{
int a;

printf("-----------------------------------------\n");
printf("vertex\t d\t f\n");

for(a = 1; a <= v_num; a++) {
printf("%d\t %d\t %d\n", a, d[a], f[a]);
}
}


void dfs (VERTEX *adj[], int v_num)
{
int visited[MAX_NUM],pi [MAX_NUM];
int time, f[MAX_NUM], d[MAX_NUM];
int i,u;

for(i=1; i<=v_num; i++)
visited[i]= pi[i]=f[i]=d[i]=0;
time = 0;
for(u = 1; u<= v_num; u++)
if (visited[u] == 0)
dfs_visit(adj, v_num, visited, pi, f, d, &time, u);
printstamp (v_num, f, d);
}

int main(void)
{
VERTEX *adj[MAX_NUM];
int v_num;

makelist(adj, &v_num);
printlist(adj, v_num);
dfs(adj, v_num);
return(0);
}

huispc1 [68]% cc -ansi -Wall dfs.c
huispc1 [69]% cc -ansi -Wall -o dfs dfs.c
huispc1 [70]% ./dfs
頂点数を入力して下さい:5

各頂点の鄰接点を入力して下さい
頂点 1 の鄰接点
鄰接点名を入力して下さい:4
鄰接点名を入力して下さい:3
鄰接点名を入力して下さい:-1
頂点 2 の鄰接点
鄰接点名を入力して下さい:5
鄰接点名を入力して下さい:4
鄰接点名を入力して下さい:-1
頂点 3 の鄰接点
鄰接点名を入力して下さい:1
鄰接点名を入力して下さい:-1
頂点 4 の鄰接点
鄰接点名を入力して下さい:3
鄰接点名を入力して下さい:-1
頂点 5 の鄰接点
鄰接点名を入力して下さい:-1
---------------------------------------------
入力されたグラフの表示
1 --> 3 4
2 --> 4 5
3 --> 1
4 --> 3
5 -->
-----------------------------------------
vertex d f
1 1 6
2 7 10
3 2 3
4 4 5
5 8 9
huispc1 [71]%



ps: tensyen dalam lab boleh main2 copy paste programming baru siap nie....even sbenarnya salah ntah knape ada stngah command xmau kluar kalau copy paste kat blog ni....