编辑代码

#include<stdio.h>
#include<malloc.h>
#define INF 32767
#define MAXV 10
typedef char InfoType;

typedef struct ANode
{    
	int adjvex;	     //边的终点编号
    struct ANode *nextarc;
    int weight;          //边的相关信息
}ArcNode;	    //边结点类型

typedef struct VNode	
{   
	InfoType info;        //顶点信息
    ArcNode *firstarc; //指向第一条边
}VNode;	//邻接表头结点类型

typedef struct
{   
	VNode adjlist[ MAXV ];   //邻接表
    int n, e;  //n为顶点数、e为边数
}AdjGraph;	//图邻接表类型 

void CreateAdj(AdjGraph *&G, int A[N][N], char V[N], int n, int e)
{   
	int i, j;  ArcNode *p;
    G=(AdjGraph *)malloc(sizeof(AdjGraph));
    for(i=0;i<n;i++)
    {
		G->adjlist[i].info = V[i];
		G->adjlist[i].firstarc = NULL;
     }
     for( i=0; i<n; i++ )
         for( j=n-1; j>=0; j-- )
	     if(A[i][j] != 0 && A[i][j] != INF)
	        {	  
			 p=(ArcNode *)malloc(sizeof(ArcNode));
		   	 p->adjvex=j;
		     p->weight=A[i][j];
		     p->nextarc = G->adjlist[i].firstarc;  //头插法
		     G->adjlist[i].firstarc = p; 
	         }
      G->n = n;  G->e = e;
} 

void DispAdj (AdjGraph *G)
{    
	ArcNode *p;
    for(int i=0;i<G->n;i++)
    {	
	  	p = G->adjlist[i].firstarc;
		printf("%d(%c): ", i, G->adjlist[i].info);
		while(p!=NULL)
		{    
			 printf("%d[%d]->", p->adjvex, p->weight);
	      	 p=p->nextarc;	
	}
		printf("^\n");
       }
} 

int visited[MAXV]={0};
void DFS (AdjGraph *G, int v)
 {    ArcNode *p;
       	visited[v]=1;
       printf("%d(%c)", v, G->adjlist[v].info); 
       p=G->adjlist[v].firstarc;
       while(p!=NULL)
       {	if( visited[p->adjvex] == 0 )
     	         DFS(G, p->adjvex);
	p = p->nextarc;		
       } 
 } 
void DFS1(AdjGraph *G)
{      int i;
        for(i=0;i<G->n;i++)
            if(visited[i]==0) 
				DFS(G, i);
}