depth first search graph by using linked list

Posted by programmerwannabe on Stack Overflow See other posts from Stack Overflow or by programmerwannabe
Published on 2010-05-22T06:46:23Z Indexed on 2010/05/22 6:50 UTC
Read the original article Hit count: 188

Filed under:

im using mac book

and i cannot read the text file using this code. moreover, can you guys please add function(graph is connected?, and is this graph tree?)

inputA.txt consist

1 2
1 6
1 5
2 3
2 6
3 4
3 6
4 5 
4 6
5 6



#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

#define MAX 10
#define TRUE 1
#define FALSE 0

typedef struct Graph{
 int vertex;
 struct Graph* link;
} g_node;

typedef struct graphType{
 int x;
 int visited[MAX];
 g_node* adjList_H[MAX];
} graphType;

typedef struct stack{
 int data;
 struct stack* link;
} s_node;

s_node* top;

void push(int item){
 s_node* n=(s_node*)malloc(sizeof(s_node));
 n->data = item;
 n->link = top;
 top = n;
}

int pop(){
 int item;
 s_node* n=top;

 if(top == NULL){
  puts("\nstack is empty!\n");
  return 0;
 }
 else {
  item = n-> data;
  top = n->link;
  free(n);
  return item;
 }
}

void createGraph(graphType* g){
 int v;
 g->x = 1;
 for(v=1 ; v < MAX ; v++){
  g -> visited[v] = FALSE;
  g -> adjList_H[v] = NULL;
 }
}

void insertVertex(graphType* g, int v){
 if(((g->x)) > MAX){
  puts("\n it has been overed the number of vertex\n");
  return ;
 }
 g -> x++;
}

void insertEdge(graphType* g, int u, int v){
 g_node* node;
 if(u >= g -> x || v >= g -> x){
  puts("\n no vertex in the graph\n");
  return ;
 }

 node = (g_node*)malloc(sizeof(g_node));
 node -> vertex = v;
 node -> link = g -> adjList_H[u];
 g-> adjList_H[u] = node;
}

void print_adjList(graphType* g){
 int i;
 g_node *p;
 for(i=1 ; i<g -> x ; i++){
  printf("\n\t\t vertex %d adjacency list ",  i);
  p = g -> adjList_H[i];
  while(p){
   printf("-> %d", p-> vertex);
   p = p-> link;
  }
 }
}

void DFS_adjList(graphType* g, int v)
{
 g_node* w;
 top = NULL;
 push(v);
 g->visited[v] = TRUE;
 printf(" %d", v);
 while(top != NULL){
  w=g->adjList_H[v];
  while(w){
   if (!g->visited[w->vertex]){
    push(w->vertex);
    g->visited[w->vertex] = TRUE;
    printf(" %d", w->vertex);
    v = w->vertex;
    w=g->adjList_H[v];
   }
   else w= w->link;
  }
  v = pop();
 }
}

int main (int argc, const char * argv[]) {
 FILE *fp;
 char mychar;
 char arr[][2]={0, };
 int j, k;

 int i;
 graphType *G9;
 G9 = (graphType*)malloc(sizeof(graphType));
 createGraph(G9);

 for(i=1; i<7 ; i++)
  insertVertex(G9, i);
 fp = fopen("inputD.txt", "r");
 for(j = 0 ; j< 10 ; j++){
  for(k = 0 ; k < 2 ; k++){
   mychar = fgetc(fp);
   if(mychar = EOF){
    j=10;
    break;
   }
   else if(mychar == ' ')
    continue;
   else if(mychar <= '9' || mychar >= '1'){
    arr[j][k] = mychar;
    printf("%d%d", arr[i][k]);
   }


     }
     }




 insertEdge(G9, 1, 2);
 insertEdge(G9, 1, 6);
 insertEdge(G9, 1, 5);
 insertEdge(G9, 2, 3);
 insertEdge(G9, 2, 6);
 insertEdge(G9, 3, 4);
 insertEdge(G9, 3, 6);
 insertEdge(G9, 4, 5);
 insertEdge(G9, 4, 6);
 insertEdge(G9, 5, 6);
 insertEdge(G9, 6, 5);
 insertEdge(G9, 6, 4);
 insertEdge(G9, 5, 4);
 insertEdge(G9, 6, 3);
 insertEdge(G9, 4, 3);
 insertEdge(G9, 6, 2);
 insertEdge(G9, 3, 2);
 insertEdge(G9, 5, 1);
 insertEdge(G9, 6, 1);
 insertEdge(G9, 2, 1);

 printf("\n graph adjacency list ");
 print_adjList(G9);

 printf("\n \n//////////////////////////////////////////////\n\n depth fist search >> ");
 DFS_adjList(G9, 1);

 return 0;
}

© Stack Overflow or respective owner

Related posts about c