m0_56489057
2021-06-26 16:24
采纳率: 100%
浏览 11

怎样实现无向图的创建算法

1、编写一个函数让用户输入这张图,用邻接表存储。
2、编写函数实现此图的深度优先搜索遍历。
3、编程实现循环队列,编写初始化、创建、入队、出队等算法。
4、利用循环队列对图实现广度优先搜索遍历。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • CSDN专家-黄老师 2021-06-26 16:26
    已采纳
    #include<stdio.h>
    #include<stdlib.h>
    #define MAX_VERTEX_NUM 100
    typedef struct ArcNode{
    	int adjvex;//该边的另一个顶点的位置 
    	struct ArcNode *nextarc; //指向下一条边 
    }ArcNode;
    typedef struct VNode{
    	int data;//顶点的值 
    	ArcNode *firstarc;//指向第一条依附该顶点的边的指针 
    }VNode,AdjList[MAX_VERTEX_NUM];
    typedef struct{
    	AdjList vertices;//顶点数组 
    	int vexnum,arcnum;
    }ALGraph;
    int LocateVex(ALGraph G,int v){//定位函数 
    	for(int i=0;i<G.vexnum;i++){
    		if(v==G.vertices[i].data)return i;
    	} 
    }
    void CreateUDG(ALGraph &G){
    	ArcNode *p,*q;
    	int i,j,k,v1,v2;
    	printf("分别输入顶点个数和边的数目:\n");
    	scanf("%d%d",&G.vexnum,&G.arcnum);
    	printf("分别输入各个顶点值:\n");
    	for(i=0;i<G.vexnum;i++){
    	scanf("%d",&G.vertices[i].data);
    	G.vertices[i].firstarc=NULL;//初始化 
    	} 
    	printf("分别输入各条边的两个顶点:\n");
    	for(k=0;k<G.arcnum;k++){
    		scanf("%d%d",&v1,&v2);
    		i=LocateVex(G,v1);j=LocateVex(G,v2);//定位 
    		p=(ArcNode*)malloc(sizeof(ArcNode));//申请一个结点 
    		p->adjvex=j;p->nextarc=NULL;//赋值 
    		p->nextarc=G.vertices[i].firstarc;//连接结点 
    		G.vertices[i].firstarc=p;//连接结点 
    		q=(ArcNode*)malloc(sizeof(ArcNode));
    		q->adjvex=i;q->nextarc=NULL;
    		q->nextarc=G.vertices[j].firstarc;
    		G.vertices[j].firstarc=q;
    	}
    }
    void PrintUDG(ALGraph G){//输出邻接表 
        int i,j;
    	for(i=0;i<G.vexnum;i++){
    		printf("%d:",i);
    		ArcNode *p;
    		p=G.vertices[i].firstarc;
    		while(p!=NULL){
    			printf("->%d",p->adjvex);
    			p=p->nextarc;
    		}
    		printf("\n");
    	}
    }
    int main(){
    	ALGraph G;
    	CreateUDG(G);
    	PrintUDG(G);
    	return 0;
    }

    如果对你有帮助,可以点击我这个回答右上方的【采纳】按钮,给我个采纳吗,谢谢
     

    点赞 1 打赏 评论

相关推荐 更多相似问题