#include
     
      #include
      
       #include
       
        //图的邻接表类型定义typedef char VertexType[4];typedef char InfoPtr;typedef int VRType;#define INFINITY 10000		//定义一个无限大的值#define MaxSize 50	 //最大顶点个数typedef enum{DG,DN,UG,UN}GraphKind;		//图的类型：有向图、有向网、无向图和无向网//边结点的类型定义typedef struct ArcNode{	int adjvex;	//邻接点域,弧指向的顶点的位置	InfoPtr *info;	//与弧相关的信息	struct ArcNode *nextarc;	//指示下一个与该顶点相邻接的顶点}ArcNode;//头结点的类型定义typedef struct VNode{	VertexType data;	//用于存储顶点	ArcNode *firstarc;	//指示第一个与该顶点邻接的顶点}VNode,AdjList[MaxSize];//图的类型定义typedef struct{	AdjList vertex;	int vexnum,arcnum;	//图的顶点数目与弧的数目	GraphKind kind;	//图的类型}AdjGraph;int visited[MaxSize];//訪问标志数组//返回图中顶点相应的位置int LocateVertex(AdjGraph G,VertexType v){	int i;	for(i=0;i
        
         vexnum);	for(i=0;i
         
          vexnum;i++){		scanf("%s",G->vertex[i].data);		G->vertex[i].firstarc=NULL;	//将相关联的顶点置为空	}	printf("请输入弧尾和弧头(以空格作为间隔):\n");	for(k=0;k
          
           arcnum;k++){ //建立边链表 scanf("%s%s",v1,v2); i=LocateVertex(*G,v1); j=LocateVertex(*G,v2); //j为弧头i为弧尾创建邻接表 p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->info=NULL; p->nextarc=G->vertex[i].firstarc; G->vertex[i].firstarc=p; //i为弧头j为弧尾创建邻接表 p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i; p->info=NULL; p->nextarc=G->vertex[j].firstarc; G->vertex[j].firstarc=p; } (*G).kind=UG;}//销毁无向图Gvoid DestroyGraph(AdjGraph *G){ int i; ArcNode *p,*q; for(i=0;i<(*G).vexnum;++i){ //释放图中的边表结点 p=G->vertex[i].firstarc; //p指向边表的第一个结点 if(p!=NULL){ //假设边表不为空。则释放边表的结点 q=p->nextarc; free(p); p=q; } } (*G).vexnum=0; //将顶点数置为0 (*G).arcnum=0; //将边的数目置为0}//返回顶点v的第一个邻接顶点的序号int FirstAdjVertex(AdjGraph G,VertexType v){ ArcNode *p; int v1; v1=LocateVertex(G,v); //v1为顶点v在图G中的序号 p=G.vertex[v1].firstarc; if(p) //假设顶点v的第一个邻接点存在，返回邻接点的序号，否则返回-1 return p->adjvex; else return -1;}//返回v的相对于w的下一个邻接顶点的序号int NextAdjVertex(AdjGraph G,VertexType v,VertexType w){ ArcNode *p,*next; int v1,w1; v1=LocateVertex(G,v); //v1为顶点v在图G中的序号 w1=LocateVertex(G,w); //w1为顶点w在图G中的序号 for(next=G.vertex[v1].firstarc;next;) if(next->adjvex!=w1) next=next->nextarc; p=next; //p指向顶点v的邻接顶点w的结点 if(!p||!p->nextarc) //假设w不存在或w是最后一个邻接点，则返回-1 return -1; else return p->nextarc->adjvex; //返回v的相对于w的下一个邻接点的序号}void Visit(VertexType v){ printf("%s ",v);}//图的非递归深度优先遍历void DFSTraverse2(AdjGraph G,int v){ int i,visited[MaxSize],top; ArcNode *stack[MaxSize],*p; for(i=0;i
           
            -1||p!=NULL){ while(p!=NULL) if(visited[p->adjvex]==1) //假设p指向的顶点已经訪问过，则p指向下一个邻接点 p=p->nextarc; else{ Visit(G.vertex[p->adjvex].data); //訪问p指向的顶点 visited[p->adjvex]=1; stack[++top]=p; //保存p指向的顶点 p=G.vertex[p->adjvex].firstarc; //p指向当前顶点的第一个邻接点 } if(top>-1){ p=stack[top--]; //假设当前顶点都已经被訪问。则退栈 p=p->nextarc; //p指向下一个邻接点 } }}//从第1个顶点出发，按广度优先非递归遍历图Gvoid BFSTraverse(AdjGraph G){ int v,front,rear; ArcNode *p; int queue[MaxSize]; //定义一个队列Q front=rear=-1; //初始化队列Q for(v=0;v
            
             adjvex]==0){ //假设该顶点未被訪问过 visited[p->adjvex]=1; Visit(G.vertex[p->adjvex].data); rear=(rear+1)%MaxSize; queue[rear]=p->adjvex; } p=p->nextarc; //p指向下一个邻接点 } }}//从顶点v出发递归深度优先遍历图Gvoid DFS(AdjGraph G,int v){ int w; visited[v]=1; Visit(G.vertex[v].data); for(w=FirstAdjVertex(G,G.vertex[v].data);w>=0;w=NextAdjVertex(G,G.vertex[v].data,G.vertex[w].data)) if(!visited[w]) DFS(G,w); //递归调用DFS对v的尚未訪问的序号为w的邻接顶点}//从第1个顶点起，深度优先遍历图Gvoid DFSTraverse(AdjGraph G){ int v; for(v=0;v