graph.h

数据结构中图的相关操作,数据结构中图的相关操作

#define NULL 0
#define MAX_V_N 20;
typedef char arcinfo;
typedef char vexinfo;
int visited[20];

typedef struct arcnode
{
 int adjvex;
 struct arcnode *next;
 arcinfo data;
}arcnode;

typedef struct vnode
{
 vexinfo data;
 arcnode *link;
}vnode;

typedef struct
{
 vnode adjlist[20];  /*?*/
 int vexnum,arcnum;
}ALG;

void cr_ALG(ALG *g)
{
 int i,head,tail;
 arcinfo info;
 arcnode *p;
 printf("enter the graphic's vertex number   \n");
 scanf("%d",&(g->vexnum));
fflush(stdin);
printf("enter arc number:\n");
scanf("%d",&(g->arcnum));
fflush(stdin);
printf("\n\n");
printf("enter each vertex's data\n");
 for(i=0;i<(g->vexnum);++i)
 {printf("NO.%d\n",i);
  scanf("%c",&((g->adjlist[i]).data));
 fflush(stdin);
  (g->adjlist[i]).link=NULL;
 
 }
 printf("enter each arc's head,tail,and data\n");
 for(i=0;i<(g->arcnum);++i)
 {puts("enter head:\n"); 
scanf("%d",&head);
fflush(stdin);
puts("enter tail:\n");
scanf("%d",&tail);
fflush(stdin);
puts("enter data:\n");
  scanf("%d",&info);
fflush(stdin);
  p=(arcnode*)malloc(sizeof(arcnode));
  p->adjvex=tail;
  p->next=(g->adjlist[head]).link;
  p->data=info;
  (g->adjlist[head]).link=p;
 }
}


void tra_DFS(ALG *g)
{
 int i,j;
 for(i=0;i<g->vexnum;++i)
  visited[i]=0;
 for(j=0;j<g->vexnum;++j)
 {
 if(visited[j]==0)
  dfs(g,j);
 }
}


dfs(ALG *g, int i)
{
 int j;
 visited[i]=1;
 printf("%c",(g->adjlist[i]).data);
printf("\n\n");
 for(j=fstadjvex(g,i);j>=0;j=nxtadjvex(g,i,j))
 {
 if(visited[j]==0)
  dfs(g,j);
 }
}


int fstadjvex(ALG *g,int i)
{
 if(g->adjlist[i].link==NULL)
   return(-1);
 else return ((g->adjlist[i]).link)->adjvex;
}


int nxtadjvex(ALG *g,int i,int j)
{
 arcnode *temp;
 temp=(g->adjlist[i]).link;
 while(temp->adjvex!=j)
 {
  temp=temp->next;
 }
 if(temp->next==NULL)
  return (-1);
 else return temp->next->adjvex;
}