aoesearch.c

无向图的邻接表的建立和遍历

/*无向图的邻接表的建立和遍历*/
#define MaxSize 100
#define NULL     0
struct ArcNode                   /*定义边结点*/
{int adjvex;
 struct ArcNode *nextarc;
};
struct Vnode                     /*定义定点结点*/ 
{int data;
    struct ArcNode *firstarc;
};
struct Vnode AdjList[MaxSize];
int m,n,v,cord;
main()
{void creatgraph(struct Vnode a[MaxSize]);
 void dfs(struct Vnode a[MaxSize]);
 void bfs(struct Vnode a[MaxSize]);
 do{printf("\n      main menu");
    printf("\n   1: creat wuxiangtu lianjiebiao");
    printf("\n   2: an shendu bianli tu");
    printf("\n   3: an guangdu bianli tu");
    printf("\n   4: exit");
    printf("----------------------------------------------------");
    printf("\n   please input your choice: 1,2,3,4\n");
    scanf("%d",&cord);
    switch(cord)
    {case 1:  creatgraph(AdjList); break;
     case 2:  dfs(AdjList); break;
     case 3:  bfs(AdjList); break;
     case 4:  exit(0);
    }
   }while(cord<=4);
}/*main end*/
void creatgraph(struct Vnode a[MaxSize])
{int i,j,k;
 struct ArcNode *p;
 printf("input arces and vexes:\n");     /*输入图的边数和顶点数*/ 
 scanf("%d,%d",&m,&n);
 for(k=0;k<n;k++)                        /*初始化顶点向量表*/ 
    {a[k].data=k+1;
     a[k].firstarc=NULL;
    }
 for(k=0;k<m;k++)
    {printf("\ninput arc:   ");          /*输入和边关联的顶点号，建立相应的链表*/
     scanf("%d,%d",&i,&j);
     p=(struct ArcNode *)malloc(sizeof(struct ArcNode));
     p->adjvex=j;
     p->nextarc=a[i-1].firstarc;         /*每一个边结点均插入在链表的首部*/
     a[i-1].firstarc=p;
     p=(struct ArcNode *)malloc(sizeof(struct ArcNode));
     p->adjvex=i;
     p->nextarc=a[j-1].firstarc;
     a[j-1].firstarc=p;
     }
 printf("\n");
 for(k=0;k<n;k++)                        /*显示已建立的邻接表信息*/
    {printf("%d",a[k].data);
     p=a[k].firstarc;
     while(p)
          {printf("%d",p->adjvex);p=p->nextarc;}
     printf("\n");
    }
}/*creatgraph end*/
void dfs(struct Vnode a[MaxSize])
{struct ArcNode *p,*ar[MaxSize];         /*ar[MAX]作为顺序栈，存放遍历过程中边结点的地址*/
 int x,i,y,top=-1;
 int visited[MaxSize];                   /*用作存放已遍历过顶点的标记*/
 for(i=0;i<n;i++) visited[i]=0;
 printf("\ninput x:");
 scanf("%d",&x);                         /*输入图遍历的始顶点的编号*/
 printf("%d",x);
 visited[x-1]=1;
 p=a[x-1].firstarc;                      /*下一个要遍历的顶点所关联的边结点，向量表的下标从0开始*/
 while((p)||(top>=0))
      {if(!p) {p=ar[top]; top--;}
       y=p->adjvex;
       if(visited[y-1]==0)
         {visited[y-1]=1;                /*若未遍历过，则遍历，并且把下一个顶点进栈，从本顶点出发继续按深度遍历*/
	  printf("->%d",y);
	  p=p->nextarc;
          if(p) {top++;ar[top]=p;}
	  p=a[y-1].firstarc;
         }
       else p=p->nextarc;
      }
}/*dfs end*/
void bfs(struct Vnode A[MaxSize])
{struct ArcNode *p;
 int x,i,y,front=-1,rear=-1,ar[MaxSize],visited[MaxSize];  /*数组ar[MAX]为顺序队列存放刚遍历过的顶点号*/
 for(i=0;i<n;i++) visited[i]=0;
 printf("\ninput x:");
 scanf("%d",&x);                         /*输入图遍历的始顶点的编号*/
 printf("%d",x);
 visited[x-1]=1;
 p=A[x-1].firstarc;
 while((p)||(front!=rear))
      {if(!p){ front++;
	       y=ar[front];
	       p=A[y-1].firstarc;
	     }
       y=p->adjvex;
       if(visited[y-1]==0)                /*遍历顺点并插入队列*/
	     {visited[y-1]=1;
	      printf("->%d",y);
	      rear++;
	      ar[rear]=y;
	     }
       p=p->nextarc;
      }
}/*bfs*/