数据结构图的遍历 C语言版

阳光穿透心脏的1/2处 2022-06-09 04:24 195阅读 0赞

#include <stdio.h>
    #include <stdint.h>
    #define max_vertex_num 100 //最多顶点个数
    typedef char VertexData;
    typedef int AdjType ;
    typedef int OtherInfo ;
    typedef struct ArcNode
    {
    	int adj; //对于无权图 用1表示相邻 0表示不相邻 ；对于带权图，则为权值类型
        OtherInfo info;
    } ArcNode;
    typedef struct
    {
    	VertexData  vertex[max_vertex_num];  //定义存储顶点的数组
    	ArcNode   arcs[max_vertex_num][max_vertex_num]; //定义邻接矩阵
    	int vexnum,arcnum; //定义顶点的个数和边的个数
    } AdjMatrix;   //邻接矩阵的结构体
    
    int LocateVertex(AdjMatrix  *G,VertexData v)  //求顶点的位置
    {
    	int j=-1,k,i;
    	for(k=0;k<G->vexnum;k++)
    	if(G->vertex[k]==v)
    	{
    		j=k;
    		break;
    	}
    	return (j);
    }
    
    void CreateMatrix(AdjMatrix *G) //用邻接矩阵创建无向图
    {
    	int i,k,j;
    	char v1,v2;
    	printf("用邻接矩阵来创建图 请输入图的顶点个数和弧数\n") ;
    	scanf("%d%d",&G->vexnum,&G->arcnum);
    	for(i=0;i<G->vexnum;i++)
    	for(j=0;j<G->vexnum;j++)
    		G->arcs[i][j].adj=0;  //初始化邻接矩阵
    	printf("请连续输入图的各个顶点的字母\n");
    	getchar();
    	for(i=0;i<G->vexnum;i++)
    		scanf("%c",&G->vertex[i]); //输入图的各个顶点
    
    	printf("请输入两个顶点之间的弧 一行两个顶点用，隔开\n");
    
    	for(k=0;k<G->arcnum;k++)
    	{
    		getchar();
    		scanf("%c,%c",&v1,&v2);
    		i=LocateVertex(G,v1);
    		j=LocateVertex(G,v2);
    		G->arcs[i][j].adj=1;
    		G->arcs[j][i].adj=1;
    	}
    }
    
    int visit[max_vertex_num];
    void DFS(AdjMatrix G,int v0) //v0为开始深度优先遍历的起始点
    {
        printf("%c ",G.vertex[v0]);
        visit[v0]=1;
        int vj;
        for(vj=0;vj<G.vexnum;vj++)
            if(!visit[vj] &&G.arcs[v0][vj].adj==1)
                  DFS(G,vj);
    }
    void TravelDFS(AdjMatrix G)
    {
        int i;
        for(i=0;i<G.vexnum;i++) visit[i]=0;
        for(i=0;i<G.vexnum;i++)
            if(!visit[i]) DFS(G,i) ;
    }
    
    typedef int QueueElementType;
    typedef struct Node
    {
        QueueElementType data;
        struct Node  *next;
    } LinkQueueNode;  //定义队列结点
    typedef struct
    {
        LinkQueueNode *front; //队列头结点指针
        LinkQueueNode *rear;  //队列尾结点指针
    } LinkQueue;  //定义队列
    
    int InitQueue(LinkQueue *Q )  //初始化队列
    {
        Q->front=(LinkQueueNode * )malloc(sizeof(LinkQueueNode));
        if(Q->front != NULL)
        {
            Q->rear=Q->front;
            Q->front->next=NULL;
            return 1;
        }
        else return 0;//溢出
    }
    
    int EnterQueue(LinkQueue *Q,QueueElementType x) //元素x入链队列 尾插法
    {
        LinkQueueNode * newnode;
        newnode=(LinkQueueNode *) malloc(sizeof(LinkQueueNode));
        if(newnode != NULL)
        {
    
            newnode->data=x;
            newnode->next=NULL;
            Q->rear->next=newnode;
            Q->rear=newnode;
            return 1;
        }
        else return 0;
    }
    
    int DeleteQueue(LinkQueue *Q,QueueElementType *x ) //链队列出队 从开始的头开始取
    {
        LinkQueueNode *p;
        if(Q->front==Q->rear)
            return 0;
        p=Q->front->next;
        Q->front->next=p->next;
        if(Q->rear==p )
    
             Q->rear=Q->front;  //如果去掉结点p后，队列为空 不要忘记将队列置空
        *x=p->data;
        free(p);
        return 1;
    }
    
    int IsEmpty(LinkQueue *Q) //队列为空返回1  不为空返回0
    {
        if(Q->front==Q->rear ) return 1;
        else return 0;
    }
    
    typedef struct ANode
    {
    	int adjvex;  //定义该弧指向顶点的位置
    	struct Node *nextarc; //定义下一条弧上网指针
    } ANode;
    
    typedef struct VertexNode
    {
    	char data; //定义顶点的数据
    	ANode *firstarc;  //定义该顶点第一条弧的指针
    } VertexNode;
    typedef struct{
    	VertexNode vertex[max_vertex_num];
    	int vexnum,arcnum;
    } AdjList;  //定义邻接表
    
    void CreateList(AdjList *G) //用邻接表创建无向图
    {
    	int i,j,k,weight;
    	char v1,v2;
    	printf("用邻接表来创建图 请输入图的顶点个数和弧数\n") ;
    	scanf("%d%d",&G->vexnum,&G->arcnum);
    	printf("请输入图的各个顶点\n");
    	getchar();
    	for(i=0;i<G->vexnum;i++)
        {
            scanf("%c",&G->vertex[i].data); //输入图的各个顶点
            G->vertex[i].firstarc=NULL;
        }
    	printf("请输入弧两端的序号顶点\n");
    	int a1,a2;
    	for(i=0;i<G->arcnum;i++)
    	{
    
    	    scanf("%d%d",&a1,&a2);
    	    ANode *temp=(ANode *)malloc(sizeof(ANode));
    	    temp->adjvex=a2;
    	    temp->nextarc=G->vertex[a1].firstarc; //前插法
    	    G->vertex[a1].firstarc=temp;
    
    	    ANode *temp1=(ANode *)malloc(sizeof(ANode));
    	    temp1->adjvex=a1;
    	    temp1->nextarc=G->vertex[a2].firstarc;
    	    G->vertex[a2].firstarc=temp1;
    	}
    
    }
    
    void BFS(AdjList G,int v0)
    {
        LinkQueue Q;
        int v;
        printf("%c ",G.vertex[v0].data);
        visit[v0]=1;
        InitQueue(&Q);
        EnterQueue(&Q,v0);
        while(!IsEmpty(&Q))
        {
            DeleteQueue(&Q,&v);
            ANode *p=(ANode *)malloc(sizeof(ANode));
            p=G.vertex[v].firstarc;
            while(p)
            {
                if(!visit[p->adjvex])
                {
                    printf("%c ",G.vertex[p->adjvex].data);
                    visit[p->adjvex]=1;
                    EnterQueue(&Q,p->adjvex);
                }
                p=p->nextarc;
    
            }
    
        }
    }
    void TravelBFS(AdjList G)
    {
        int i;
        for(i=0;i<G.vexnum;i++) visit[i]=0;
        for(i=0;i<G.vexnum;i++)
            if(!visit[i]) BFS(G,i);
    }
    
    int main()
    {
        AdjMatrix G;
        CreateMatrix(&G);
        printf("从第一个顶点开始深度优先遍历的结果为\n");
        TravelDFS(G);
    
        printf("\n");
        AdjList AG;
        CreateList(&AG);
        printf("从第一个顶点开始广度优先遍历的结果为\n");
        TravelBFS(AG);
    
        return 0;
    }