有向图遍历，十字链表存储，深度遍历，广度遍历。

曾经终败给现在 2022-08-19 02:09 3阅读 0赞

![Center][]

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX_VERTEX_NUM 20 
    #define MAXSIZE 100 
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    int visited[MAX_VERTEX_NUM]; //用于区分节点是否，访问过。
     
    typedef struct ArcBox{       //定义弧的结构。 
    	int tailvex, headvex;
    	struct ArcBox *hlink, *tlink;  
    }ArcBox;
    typedef struct VexNode{      //顶点结构 
    	char data[5];
    	ArcBox *firstin, *firstout; 
    }VexNode;
    typedef struct {            //图结构 
    	VexNode xlist[MAX_VERTEX_NUM];  
    	int vexnum, arcnum;    
    }OLGraph;
    typedef struct{             //队列结构 
    	int *base;
    	int rear;
    	int front;
    }SqQueue;
    //查找元素v，在顶点数组中的下标。 
    int LocateVex(OLGraph G,char v[]){
    	for(int i = 0; i < G.vexnum; i++){
    		if(strcmp(G.xlist[i].data, v) == 0){
    			return i;
    		} 
    	} 
    }
    //创建图 
    int CreateDG(OLGraph &G){
    	printf("请输入图的顶点数：");
    	scanf("%d",&G.vexnum);
    	printf("请输入图的弧数：");
    	scanf("%d",&G.arcnum);
    	printf("输入图的结点内容:\n");
    	//初始化各个顶点 
    	for(int i = 0; i < G.vexnum; i++){
    		printf("输入第%d个顶点：", i+1);
    		fflush(stdin); 
    		scanf("%s", G.xlist[i].data);  
    	    G.xlist[i].firstin = NULL;
    	    G.xlist[i].firstout = NULL;
    	}
    	printf("\n");
    	for(int k = 0; k < G.arcnum; k++){
    		char data1[5], data2[5];
    		ArcBox* p;
    		printf("输入第%d条弧的始点和终点：", k+1);
    		scanf("%s%s", data1, data2);
    		int i = LocateVex(G, data1); 
    		int j = LocateVex(G, data2); 
    		p = (ArcBox*)malloc(sizeof(ArcBox));
    		p->tailvex = i;
    		p->headvex = j;
    		p->tlink = G.xlist[i].firstout;  
    		p->hlink = G.xlist[j].firstin;
    		G.xlist[i].firstout = p; 
    		G.xlist[j].firstin = p;
    	}
    	printf("\n");
    	return OK;
    }
    //第一个领结点 
    int FirstAdjVex(OLGraph G, int v){
    	ArcBox* p;
    	if(G.xlist[v].firstout){
    		p = G.xlist[v].firstout;
    		return p->headvex;
    	}else{
    		return ERROR;
    	} 
    }
    //相对v顶点的下一个顶点。 
    int NextAdjVex(OLGraph G, int v, int w){
    	ArcBox* p;
    	if(( v > G.vexnum) && ( w > G.vexnum)){
    		  return ERROR;
    	}
    	for(p = G.xlist[v].firstout; p->headvex != w; p = p->tlink);
    	if(p->tlink){
    		return p->tlink->headvex;
    	}else{
    		return 0;
    	} 
    }
    //深度递归遍历 
    void DFS(OLGraph G,int v){
    	visited[v] = TRUE;
    	printf("%s\t", G.xlist[v].data); 
    	for(int w = FirstAdjVex(G,v); w > 0 ; w = NextAdjVex(G,v,w)){
    		if(!visited[w]){
    			   DFS(G,w); 
    		} 
    	} 
    }
    //深度遍历 
    void DFSTraverse(OLGraph G){
    	if(G.vexnum == 0 || G.arcnum == 0 ){
    		printf("         图未创建成功!");
    		return; 
    	} 
    	for(int v=0; v<G.vexnum; v++){
    		visited[v] = FALSE;   
    	} 
    	for(int v = 0;v < G.vexnum;v++){
    		if(!visited[v]){
    			DFS(G,v); 
    		}  
    	} 
    }
    
    void InitQ(SqQueue &Q){
    	Q.base = (int *)malloc(MAXSIZE * sizeof(int));
    	if(!Q.base){
    		 exit(0);
    	} 
    	Q.rear = 0;
    	Q.front = 0; 
    }
    void EnQueue(SqQueue &Q, int e){
    	if((Q.rear+1) % MAXSIZE == Q.front){
    		 exit(0);
    	} 
    	Q.base[Q.rear] = e;
    	Q.rear = (Q.rear+1) % MAXSIZE;
    }
    void DeQueue(SqQueue &Q, int &e){
    	if(Q.rear == Q.front){
    		 exit(0);
    	} 
    	e = Q.base[Q.front];
    	Q.front = (Q.front+1) % MAXSIZE;
    }
    int QueueEmpty(SqQueue Q){
    	if(Q.rear == Q.front){
    		return TRUE;
    	}else{
    		return FALSE;
    	} 
    }
    //广度遍历 
    void BFSTraverse(OLGraph G){
    	if(G.vexnum == 0 || G.arcnum == 0){
    		printf("         图未创建成功!");
    		return; 
    	} 
    	SqQueue Q;
    	for(int v = 0; v < G.vexnum; ++v){
    		visited[v] = FALSE;
    	}  
    	InitQ(Q);                   
    	for(int v = 0;  v < G.vexnum; ++v){
    		if(!visited[v]) 
    		{
    			visited[v] = TRUE; 
    			printf("%s\t", G.xlist[v].data);
    			EnQueue(Q,v);             
    			while(!QueueEmpty(Q))
    			{
    				int u;
    				DeQueue(Q,u);         
    				for(int w = FirstAdjVex(G,u); w > 0; w = NextAdjVex(G,u,w)){
    					if(!visited[w]){    
    						visited[w] = TRUE; 
    						printf("%s\t",G.xlist[w].data);
    						EnQueue(Q,w);
    					}
    				}   
    			}   
    		}  
    	} 
    }                     
    
    int main(){
    	printf("---------------------------------------------------------------------\n");
    	printf("              十字链表存储，有向图深度广度遍历                       \n");
    	printf("---------------------------------------------------------------------\n");
    	printf("           1.创建图， 2.深度遍历， 3.广度遍历， 4.退出               \n");
    	char sel; 
    	OLGraph G;
    	printf("请选择： ");
    	scanf("%c", &sel);
    	while(sel != '4'){
    		switch(sel){
    			case '1': 
    				CreateDG(G); 
    				break;
    			case '2':
    				printf("           深度遍历为：               \n");
    				DFSTraverse(G); 
    				break; 
    			case '3': 
    				printf("           广度遍历为：               \n");
    				BFSTraverse(G); 
    				break;
    			default :
    				printf("输入有误！");
    				break; 
    		}
    		fflush(stdin);
    		printf("\n请选择： ");
    		scanf("%c", &sel);
    	}
    	 exit(1); 
    	return 0;
    }

[Center]: /images/20220731/647b46046a6d4eb29d2044222d20bef8.png