tu.txt

图的建立与多种遍利方法

#include"stdio.h"
#include"stdlib.h"
#define LEN sizeof(struct edge)
#define MaxVerTexNum 30
typedef int ElemType;
typedef struct edge
                {
                    int AdjVertex;
                    struct edge *NextEdge;
                }EdgeType;
typedef struct node 
                {
                    ElemType Vertex;
                    int flag;
                    EdgeType *FirstEdge;
                }VertexType;
typedef VertexType adjlist[MaxVerTexNum];
typedef struct nod
                 {
                      int num;
                      struct nod *next;
                  }*point;
adjlist Graph;
void creat()
{
    int i,j,k,m;
    int v1,v2;    
    EdgeType *p,*q; 
    int n,e;
   /*输入图中顶点个数 N 和 边数 E */
    printf("please enter the nodes number : ");   
    scanf("%d",&n);
    printf("please enter the edges number : ");
    scanf("%d",&e);
    /*输入顶点的数据：*/
    for(k=0;k<n;k++)
        {
            scanf("%d",&Graph[k].Vertex);
            Graph[k].FirstEdge=NULL;
            Graph[k].flag=0;
        }
    /*输入各边，次序为：弧尾顶点、弧头顶点*/
    printf("enter the edges : ");
    for(k=0;k<e;k++)
        {
         scanf("%d,%d",&v1,&v2);        
         for(m=0;m<n;m++)
            {
                if(Graph[m].Vertex==v1)
                    i=m;
                if(Graph[m].Vertex==v2)
                    j=m;
            }
         q=(EdgeType *)malloc(LEN);
         q->AdjVertex=j;
         q->NextEdge=Graph[i].FirstEdge;
         Graph[i].FirstEdge=q;
         p=(EdgeType *)malloc(LEN);
         p->AdjVertex=i;
         p->NextEdge=Graph[j].FirstEdge;
         Graph[j].FirstEdge=p;
        }
    /*显示图的邻接表的结构*/
    printf("xianshi : \n");
    for(i=0;i<n;i++)
        {
             printf("%d\t",i);
             v1=Graph[i].Vertex;
             printf("Vertex : %d",v1);
             p=Graph[i].FirstEdge;
             while(p!=NULL)
                {
                    v2=p->AdjVertex;
                    printf("--%d",v2);
                    p=p->NextEdge;
                }
            printf("\n");
        }
}
void bfs(adjlist GL,int i)
{    
    point p,head,q;
    int ft=-1;    
    EdgeType *L;
    int j;    
    printf("%d\t",GL[i].Vertex);
    head=q=(point)malloc(sizeof(struct nod));
    q->num=i;
    GL[i].flag=1;
    while(head!=NULL)   
        {
            ft=head->num;    
            L=GL[ft].FirstEdge;
            while(L!=NULL)
                {
                     j=L->AdjVertex;
                     if(GL[j].flag!=1)  
                         {                     
                             printf("%d\t",GL[j].Vertex);
                             GL[j].flag=1;
                             p=(point)malloc(sizeof(struct nod));
                             p->num=j;
                             q->next=p;
                             q=p;
                             q->next=NULL;
                          }
                     L=L->NextEdge;
                }
            head=head->next;
        }
}            
void dfs(adjlist GL,int i) 
{
    EdgeType *L;
    int j;    
    printf("%d\t",GL[i].Vertex);
    GL[i].flag=2;   
    L=GL[i].FirstEdge;
    while(L!=NULL)
        {
            j=L->AdjVertex;
            if(GL[j].flag!=2)
                dfs(GL,j);
            L=L->NextEdge;
        }
}
void main()
{   int inta,intb,intc=0;
creat();
    printf(" \n\t\t 1 : DFS");
    printf(" \n\t\t 2 : BFS");
    printf(" \n\t\t 3 : Exit");
    printf("\nEnter your chose :");
    scanf("%d",&inta);
    while(inta!=3)
    {   intc=intc+1; 
        printf("Bian Li Qi Dian : ");
        scanf("%d",&intb);
        switch (inta)
            {
                case 1 : bfs(Graph,intb); break;
                case 2 : dfs(Graph,intb); break;
             }
        if(intc==2)
            return;
        printf(" \n\t\t 1 : DFS");
        printf(" \n\t\t 2 : BFS");
        printf(" \n\t\t 3 : Exit");
        printf("\nEnter your chose :");
        scanf("%d",&inta);
    }}