数据结构——图-有向图的邻接矩阵

青旅半醒 2022-12-29 04:47 201阅读 0赞

![在这里插入图片描述][20201220105802714.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]

#include<stdio.h>
    #include<string.h>
    #define INF 32767
    #define MAXVEX 30
    typedef char VertexType;
    typedef struct graph
    {
        
    	int n,e;
    	VertexType vexs[MAXVEX];
    	int edges[MAXVEX][MAXVEX];
    }MGraph;
    
    void CreateMGraph(MGraph &G)
    {
        
    	int n,e;
    	int value;
    
    	char temp_i;
    	char temp_j;
    	
    	printf("请输入图的顶点数和边数（以空格分隔）：");
        scanf("%d%d",&n,&e);
        G.n=n;G.e=e;
        
        
        
        for(int i=0;i<n;i++)
        {
        
        	for(int j=0;j<n;j++)
        	{
        
        		if(i==j)
        			G.edges[i][j]=0;
        		else
        			G.edges[i][j]=32767;
    		}
    		
    	}
    	
    	
    	
    			printf("输入顶点信息：");
    		for(int j=0;j<G.n;j++)
    		{
        
    			getchar();
    			scanf("%c",&G.vexs[j]);
    			
    		}
    		
    			
    		
    		int temp_number_i;
    		int temp_number_j;
    		
    		printf("请输入每条边的权值：\n");
    		for(int j=0;j<e;j++)
    		{
        
    			getchar();
    			scanf("%c %c %d",&temp_i,&temp_j,&value);
    			for(int i=0;i<n;i++)
    			{
        
    				if(G.vexs[i]==temp_i)
    					temp_number_i=i;
    				if(G.vexs[i]==temp_j)
    					temp_number_j=i;
    			}
    			G.edges[temp_number_i][temp_number_j]=value;
    		}
    	
    	
    
    		
    		
    	
    }
    
    void DispMGraph(MGraph &G)
    {
        
    	printf("输出顶点信息：\n");
    	for(int i=0;i<G.n;i++)
    	{
        
    		printf("%c",G.vexs[i]);
    	} 
    	printf("\n输出邻接矩阵：\n");
    	printf("\t");
        for(int i=0;i<G.n;i++)
            printf("%8c",G.vexs[i]); 
            
        for(int i=0;i<G.n;i++)
        {
        
        	printf("\n%8c",G.vexs[i]);
        	for(int j=0;j<G.n;j++)
        	{
        
        		if(G.edges[i][j]==32767) 
            //两点之间无连接时权值为默认的32767，
           // 在无向图中一般用"0"表示，在有向图中一般用"∞",
           // 这里为了方便统一输出 "∞"
                printf("%8s", "∞");
            else
                printf("%8d",G.edges[i][j]);
    		}
    		printf("\n");
    	}
    }
    
    void Degree(MGraph G,VertexType v)
    {
        
    
    	int temp;
    	int enter_degree=0;
    	int out_degree=0; 	
    
    	for(int i=0;i<G.n;i++)
    	{
        
    		if(G.vexs[i]==v)
    			{
        
    				temp=i;
    				break;
    			}
    	}
    	
    
    	
    	for(int i=0;i<G.n;i++)
    	{
        
    		if(G.edges[temp][i]>0&&G.edges[temp][i]<32767)
    			out_degree++;
    		if(G.edges[i][temp]>0&&G.edges[i][temp]<32767)
    			enter_degree++;
    	}
    	printf("该有向图%c的顶点入度为：%d\n",v,enter_degree);
    	printf("该有向图%c顶点的出度为：%d\n",v,out_degree); 
    	
    	return ;
    }
    void InsertVex(MGraph &G,VertexType v)
    {
        
    //向邻接矩阵中添加一个新顶点 
    	G.n=G.n+1;
    	G.vexs[G.n-1]=v;
    	for(int i=0;i<G.n;i++)
    	{
        
    		G.edges[i][G.n-1]=32767;
    		G.edges[G.n-1][i]=32767;
    	}
    	G.edges[G.n-1][G.n-1]=0;
    	
    	
    }
    
    void DeleteVex(MGraph &G,VertexType v) 
    {
        
    	int temp=0;
    	for(int i=0;i<G.n;i++)
    	{
        
    		if(G.vexs[i]==v)
    		{
        
    			temp=i;
    			break;
    		}
    	}
    	for(int i=0;i<G.n;i++)
    		for(int j=0;j<G.n;j++)
    		{
        
    			if(i>temp&&j>temp)
    				G.edges[i-1][j-1]=G.edges[i][j];
    			if(i>temp)
    				G.edges[i-1][j]=G.edges[i][j];
    			if(j>temp)
    				G.edges[i][j-1]=G.edges[i][j];
    		}
    		for(int i=0;i<G.n;i++)
    		{
        
    			if(i>temp)
    				G.vexs[i-1]=G.vexs[i];
    				
    		}
    		
    	
    	
    	
    	G.n=G.n-1;
    }
    void InsertArc(MGraph &G,VertexType v,VertexType w)
    {
        
    	//向邻接矩阵里添加一个新的边； 
    	int value;
    	printf("输入新加入边的权值：");
    	scanf("%d",&value);
    		int temp_number_i;
    		int temp_number_j;
    	for(int i=0;i<G.n;i++)
    	{
        
    			if(G.vexs[i]==v)
    				temp_number_i=i;
    			if(G.vexs[i]==w)
    				temp_number_j=i;
    	}
    	G.edges[temp_number_i][temp_number_j]=value;
     } 
    
    void DeleteArc(MGraph &G,VertexType v,VertexType w)
    {
        
    	//删除一条指定的边 
    		int temp_number_i;
    		int temp_number_j;
    	for(int i=0;i<G.n;i++)
    	{
        
    			if(G.vexs[i]==v)
    				temp_number_i=i;
    			if(G.vexs[i]==w)
    				temp_number_j=i;
    	}
    	G.edges[temp_number_i][temp_number_j]=32767;
    } 
    
    int main()
    {
        
    	MGraph G;
    	CreateMGraph(G);
    	DispMGraph(G);
    	char v,w;
    	printf("输入要求(入度出度)的顶点：");
    	getchar();
    	scanf("%c",&v);
    	Degree(G,v);
    	
    	
    	printf("输入新加入的顶点：");
    	getchar();
    	scanf("%c",&v);
    	InsertVex(G,v);
    	DispMGraph(G);
    	
    	
    	
    	getchar();
    	printf("输入新加入的边：");
    	scanf("%c %c",&v,&w);
    	InsertArc(G,v,w);
    	DispMGraph(G);
    	
    	
    	
    	printf("输入删除的边：");
    	getchar();
    	scanf("%c %c",&v,&w);
    	DeleteArc(G,v,w);
    	DispMGraph(G);
    	
    	
    	printf("输入要删除的顶点及其相关的边：");
    	getchar();
    	scanf("%c",&v); 
    	DeleteVex(G,v);
    	DispMGraph(G);
     }

[20201220105802714.png]: /images/20221120/a70ffa542e3f4f0fb500da67cead0d2a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221120/a2b77120fb4843b3a8dd28159a86a121.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]: /images/20221120/cc9c930b1af74eb1bb2bc240604bcb24.png