graph3.cpp

实现图的遍历

#include<stdio.h>
#include<stdlib.h>
#define MAX 20
int visited[MAX];
typedef struct arcnode{
    int adjvex;
    struct arcnode *nextarc;
}arcnode;
typedef struct vnode{
    int data;
    arcnode *firstarc;
}vnode,adjlist[MAX];
typedef struct{
    adjlist vertices;
    int vexnum,arcnum;
}algraph;
int locatevex(algraph *g,int s)
{
    int i;
    for(i=0;i<g->vexnum;i++)
	if(g->vertices[i].data==s)
	   return i;
      return -1;
}
int createNDG(algraph *g)
{
    int i,j,k;
    int v[MAX],w[MAX],e,d;
    arcnode *p,*q;
    printf("shu ru jidian ge shu:");
    scanf("%d",&(g->vexnum));
    printf("\nshu ru fu de tiaoshu:");
    scanf("%d",&(g->arcnum));
    scanf("%d",&e);
    printf("\nEnter the name of vex:");
    for(i=0;i<g->vexnum;i++)
       {
       scanf("%d",&(g->vertices)[i].data);
       g->vertices[i].firstarc=NULL;
       }
    scanf("%d",&d);
    printf("\nEnter the two vex that connect the edge:");
    for(k=0;k<g->arcnum;k++)
     {
       scanf("%d %d,",&v[k],&w[k]);
       i=locatevex(g,v[k]);
       if(i==-1)
	 {
	   printf("You've entered a vex name that do not exist in this graph! ");
	   return -1;
	 }
       j=locatevex(g,w[k]);
       if(j==-1)
	 {
	   printf("You've entered a vex name that do not exist in this graph! ");
	   return -1;
	 }
       p=(arcnode *)malloc(sizeof(arcnode));
       p->nextarc=(g->vertices)[i].firstarc;
       p->adjvex=j;
       (g->vertices)[i].firstarc=p;
       q=(arcnode *)malloc(sizeof(arcnode));
       q->nextarc=(g->vertices)[j].firstarc;
       q->adjvex=i;
       (g->vertices)[j].firstarc=q;
     }
       return 0;
}
int firstadjvex(algraph *t,int v)
{
    arcnode *q;
    q=(t->vertices)[v].firstarc;
    if(q==NULL)
      return -1;
    else
      return(q->adjvex);
}
int nextadjvex(algraph *g,int v,int w)
{
    arcnode *p;
    p=(g->vertices)[v].firstarc;
    while((p->adjvex!=w)&&(p!=NULL))
      p=p->nextarc;
    if(p==NULL)
      return -1;
    if(p->adjvex==w)
      {
	p=p->nextarc;
	if(p==NULL)
	  return -1;
	else
	  return(p->adjvex);
       }
    return -1;
}
void pathlength(algraph *g,int v,int w,int k,int *p)
{
    int u;
    visited[v]=1;
    for(u=firstadjvex(g,v);u>=0;u=nextadjvex(g,v,u))
      {
	 if((!visited[u])&&(u!=w))
             pathlength(g,u,w,k-1,p);
         if((u==w)&&(k==1))
             {*p=1;break;}
       }
}
void main()
{
    int l=0,m;
    algraph *G;
    int v,w,d,e;
    int k,x,i,j,*p=0;
    arcnode *q;
    G=(algraph *)malloc(sizeof(algraph));
    for(x=0;x<G->vexnum;v++)
	visited[x]=0;
    l=createNDG(G);
    scanf("%d",&d);
    for(m=0;m<G->vexnum;m++)
	 {
	   q=(G->vertices)[m].firstarc;
	   printf("\nThe arc starts from %c to:",(G->vertices)[m].data);
	   while(q!=NULL)
	     {
	       printf(" %d",q->adjvex);
	       q=q->nextarc;
	      }
	   printf("\n");
	 }
    if(l==-1)
      printf("ERROR!");
    else
     {
      printf("\nEnter the two vex's name that you want to certificate:");
      scanf("%d,%d",&v,&w);
      scanf("%d",&e);
      printf("\nEnter the length of the path between them:");
      scanf("%d",&k);
      i=locatevex(G,v);j=locatevex(G,w);
      pathlength(G,i,j,k,p);
      if((*p)==1)
        printf("The path is correct!");
      else  
        printf("There do not exist such a path!");
      }
}