#include<stdio.h>
#include<stdlib.h>
#define Max_vertex 20
typedef enum
{
FALSE,
TRUE
}Boolean;
Boolean visited[Max_vertex];
typedef char vertextype;
typedef struct edgenode
{
int adjvex;
struct edgenode *next;
}EdgeNode;
typedef struct vertexnode
{
vertextype vertex;
EdgeNode * firstedge;
}VertexNode;
typedef VertexNode AdjList[Max_vertex];
typedef struct ALGraph
{
AdjList adjlist;
int n,e;
}Graphic;
void createGraphic(Graphic *G)
{
int i,j,k;
EdgeNode *s;
printf("please input the vertexs' number and Edges' number:\n");
fflush(stdin);
scanf("%d%d",&G->n,&G->e);
getchar();
printf("please input the vertexs' information.\n");
for(i=1;i<(G->n+1);i++)
{
fflush(stdin);
G->adjlist[i].vertex=getchar();
G->adjlist[i].firstedge=NULL;
getchar();
}
printf("please input the nodes(double):\n");
for(k=1;k<(G->e+1);k++)
{
scanf("%d%d",&i,&j);
getchar();
s=(EdgeNode *)malloc(sizeof(EdgeNode));
if(!s)
{
printf("overflow!");
exit(0);
}
else
{
s->adjvex=j;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;
s=(EdgeNode *)malloc(sizeof(EdgeNode));
   if(!s)
    {
     printf("overflow!");
     exit(0);
   }
   else
      {
    s->adjvex=i;
        s->next=G->adjlist[j].firstedge;
        G->adjlist[j].firstedge=s;
      }
   }
}
}
void DFS(Graphic *G,int i)
{
EdgeNode *p;
printf("visitvertex:%c\n",G->adjlist[i].vertex);
visited[i]=TRUE;
p=G->adjlist[i].firstedge;
while(p)
{
if(!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
void DFSTraverse(Graphic *G)
{
int i;
for(i=1;i<(G->n+1);i++)
visited[i]=FALSE;
for(i=1;i<(G->n+1);i++)
if(!visited[i])
  DFS(G,i);
}

void main(void)
{
Graphic create;
clrscr();
createGraphic(&create);
DFSTraverse(&create);
}





评论