PTA 6-1 求采用邻接矩阵作为存储结构的无向图各顶点的度 (6分)

刺骨的言语ヽ痛彻心扉 2023-02-10 03:35 10阅读 0赞

# PTA 6-1 求采用邻接矩阵作为存储结构的无向图各顶点的度 (6分) #

## 函数接口定义： ##

函数接口为：
    void dgree(MGraph G);

G为采用邻接矩阵作为存储结构的有向图

## 裁判测试程序样例： ##

#include <stdio.h>
    #define MVNum 100                 //最大顶点数 
    typedef struct{
         
      char vexs[MVNum];           //存放顶点的一维数组 
      int arcs[MVNum][MVNum];     //邻接矩阵 
      int vexnum,arcnum;          //图的当前顶点数和边数 
    }MGraph; 
    void dgree(MGraph G);
    void CreatMGraph(MGraph *G);/* 创建图 */
    int main()
    {
        
    	MGraph G;
    	CreatMGraph(&G);
            dgree(G);
    	return 0;
    }
    void CreatMGraph(MGraph *G)
    {
        
    	int i,j,k;
    	scanf("%d%d",&G->vexnum,&G->arcnum);
    	getchar();
    	for(i=0;i<G->vexnum;i++)
               scanf("%c",&G->vexs[i]);
    	for(i=0;i<G->vexnum;i++)
    	   for(j=0;j<G->vexnum;j++)
    	        G->arcs[i][j]=0;
    	for(k=0;k<G->arcnum;k++)
    	  {
          
    	   scanf("%d%d",&i,&j);     
    	   G->arcs[i][j]=1; 
    	   G->arcs[j][i]=1; 
    	  }
    }
    
    /* 请在这里填写答案 */

## 输入样例： ##

第一行给出图的顶点数n和边数e。第二行给出n个字符，表示n个顶点的数据元素的值。后面是e行，给出每一条边的两个顶点编号。

4 5
    ABCD
    0 1
    0 2
    1 2
    1 3
    2 3

## 输出样例： ##

输出n个顶点的元素值，顶点的数据类型为字符型。以及各顶点的度值

A:2
    B:3
    C:3
    D:2

## 【程序实现】 ##

void dgree(MGraph G) {
        
    	for(int i = 0; i < G.vexnum; i++) {
        
    		int c = 0;
    		for(int j = 0; j < G.vexnum; j++)
    			if(G.arcs[i][j] == 1)
    				c++;
    		printf("%c:%d\n",G.vexs[i],c);
    	}
    }