tu.c

数据结构

#include<stdio.h>
#include<stdlib.h>
#define m 20                      /*预定义图的最大顶点数*/
typedef char datatype;       /*顶点信息数据类型*/
typedef struct node{           /*边表结点*/
    int adjvex;                      /*邻接点*/
    struct node *next;
}edgenode;
typedef struct vnode{        /*头结点类型*/
   datatype vertex;             /*顶点信息*/
   edgenode *firstedge;     /*邻接链表头指针*/
}vertexnode;
typedef struct{                       /*邻接表类型*/
     vertexnode adjlist [m];     /*存放头结点的顺序表*/
     int n,e;                             /*图的顶点数与边数*/
}adjgraph;

void createadjgraph(adjgraph *g)
    { int i,j,k;
      edgenode *s;
      printf("Please input n and e:\n");
      scanf("%d%d",&g->n,&g->e);     /*输入顶点数与边数*/
      getchar();
      printf("Please input %d vertex:",g->n);
for(i=0;i<g->n;i++)
      {scanf("%c",&g->adjlist[i].vertex);      /*读入顶点信息*/
        g->adjlist[i].firstedge=NULL;            /*边表置为空表*/
        }
      printf("Please input %d edges:",g->e);
      for(k=0;k<g->e;k++)                 /*循环e次建立边表*/
        {   scanf("%d%d",&i,&j);         /*输入无序对（i,j）*/
         s=(edgenode *)malloc(sizeof(edgenode));
             s->adjvex=j;                      /*邻接点序号为j*/
         s->next=g->adjlist[i].firstedge;
         g->adjlist[i].firstedge=s;    /*将新结点*s插入顶点vi的边表头部*/
         s=(edgenode *)malloc(sizeof(edgenode));
             s->adjvex=i;                    /*邻接点序号为i*/
         s->next=g->adjlist[j].firstedge;
         g->adjlist[j].firstedge=s;      
             /*将新结点*s插入顶点vj的边表头部*/
        }
   }

int visited[m];
void dfs(adjgraph g,int i)
{  /*以vi为出发点深度优先遍历顶点vi所在的连通分量*/
  edgenode *p;
  printf("visit vertex: %c \n",g.adjlist[i].vertex);    /*访问顶点i*/
  visited[i]=1;
  p=g.adjlist[i].firstedge;
  while (p)               /*从p的邻接点出发进行深度优先搜索*/
    {  if (!visited[p->adjvex])    
                 dfs(g,p->adjvex);     /*递归*/
       p=p->next;
    }
}
void dfstraverse(adjgraph g)
{ /* 深度优先遍历图g */
 int i;
   for (i=0;i<g.n;i++)
       visited[i]=0;         /*初始化标志数组*/
   for (i=0;i<g.n;i++)
       if (!visited[i])        /*vi未访问过*/
               dfs(g,i);
 }
 void printadjgraph(adjgraph g)
{
    int i;
    for(i=0;i< g.n;i++)
    {
        printf("%c",g.adjlist[i].vertex);
        while(g.adjlist[i].firstedge)
        {
            printf("--->%d",g.adjlist[i].firstedge->adjvex);
            g.adjlist[i].firstedge=(g.adjlist[i].firstedge)->next;
        }
        printf("\n");
    }
}

void main()
{
    adjgraph g;
    createadjgraph(&g);
    printadjgraph(g);
}