C语言有向图的创建、求度、遍历（用领接矩阵存储法）

浅浅的花香味﹌ 2023-06-18 07:59 41阅读 0赞

#include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    #define MAXVEX 20  //最大顶点个数 
    #define INFINTY -1  //表示无穷 
    //∞无穷 
    typedef struct{
    	int arcs[MAXVEX][MAXVEX];//边(弧)信息 
    	char vex[MAXVEX];  //顶点信息 
    	int vexnum;//顶点数目 
    	int arcnum;//边（弧）数目 
    }Adjmatrim; //领接矩阵 (数组表示法)
    
    typedef struct {
    	int in;
    	int out;
    	int total;
    }Degree[MAXVEX];
    
    typedef struct{
    	int vex[MAXVEX]; 
    	int front;
    	int rear;
    }*QUEQUE,QUEQUE_1;
    
    
    int visited[MAXVEX]={0};
    
    Adjmatrim *Create_Adjmatrim();  //创建无向图  
    void Create(Adjmatrim *G);      //创建图 
    int Locate(Adjmatrim *G,char v); //算是否连通 
    void prinf_Adjmatrim(Adjmatrim *G) ;//输出图 
    void Calulate_Degree(Adjmatrim *G);//算每一个结点的度并输出 
    void DFS(Adjmatrim *G,int n);//深度优先遍历连通子图
    void TraverseG(Adjmatrim *G);// 
    int First_Adjmatrim_VEX(Adjmatrim *G,int n);//第一个领接点
    int Next_Adjmatrim_vex(Adjmatrim *G,int n,int w);//下一个领接点
    void TraverseG_BFS(Adjmatrim *G);//广度优先遍历
    void BFS(Adjmatrim *G,int n);//广度优先搜索遍历连通图
    QUEQUE Create_QUEQUE();//创建队列
    int Empty(QUEQUE Q);//队列判空
    void out_QUEQUE(QUEQUE Q,int *w);//出队
    void input_QUEQUE(QUEQUE Q,int w);//入队 
    
    main()
    {
    	Adjmatrim *G=Create_Adjmatrim();
    	Create(G);
    //	prinf_Adjmatrim(G);//输出有向图的领接矩阵 
    	Calulate_Degree(G);//算度 
    	TraverseG(G);//深度优先遍历 
    	printf("\n"); 
    	TraverseG_BFS(G);
    	
    	//算度 测试 
    	/*
    	int n=0;
    	int w=4;
    	printf("%d %c\n",First_Adjmatrim_VEX(G,n),G->vex[First_Adjmatrim_VEX(G,n)]);
    	printf("%d %c",Next_Adjmatrim_vex(G,n,w),G->vex[Next_Adjmatrim_vex(G,n,w)]);
    	*/ 
    }
    
    Adjmatrim *Create_Adjmatrim()  //创建无向图 
    {
    	Adjmatrim *G=(Adjmatrim*)malloc(sizeof(Adjmatrim));
    	return G;
    }
    
    void Create(Adjmatrim *G)  //初始化 
    {
    	int i,j,k,weight;
    	char vex1,vex2;
    	scanf("%d %d",&G->vexnum,&G->arcnum);//输入顶点数目和边数目
    	 
    	for(i=0;i<MAXVEX;i++)
    	for(j=0;j<MAXVEX;j++)
    	G->arcs[i][j]=-1;  //初始化 
    	
    	char  G_vexnum[G->vexnum];
    	scanf("%s",G_vexnum);
    	
    	for(i=0;i<G->vexnum;i++) 
    	{ 
    		G->vex[i]=G_vexnum[i]; // 初始化G->vexnum个结点 
    		
    	}
    	
    	for(i=G->vexnum;i<MAXVEX;i++) //其它结点的信息初始化为NULL 
    	{ 
    		G->vex[i]=NULL;
    		
    	}
    	
    	char vex1_vex2[2];
    	for(k=0;k<G->arcnum;k++)
    	{
    		scanf("%s",vex1_vex2);
    		vex1=vex1_vex2[0];
    		vex2=vex1_vex2[1];
    		i=Locate(G,vex1);
    		j=Locate(G,vex2);
    		G->arcs[i][j]=1;
    	} 
    	 	
    } 
    
    
    int Locate(Adjmatrim *G,char v)//寻找位置 
    {
    	int i;
    	for(i=0;i<G->vexnum;i++)
    	if(G->vex[i]==v)
    	return i;
    	return 0;
    }
    
    void prinf_Adjmatrim(Adjmatrim *G) 
    {
    	int i,j;
    	printf(" ");
    	for(i=0;i<G->vexnum;i++)
    	printf("%c",G->vex[i]);
    	
    	printf("\n");
    	for(i=0;i<G->vexnum;i++)
    	{
    		printf("%c",G->vex[i]);
    		for(j=0;j<G->vexnum;j++)
    		{
    			if(G->arcs[i][j]==-1)//空 
    			printf("0");
    			else
    			printf("%d",G->arcs[i][j]);
    		}
    		printf("\n");
    	}
    	
    }
    
    
    void Calulate_Degree(Adjmatrim *G)
    {
    	int i,j;
    	Degree A;
    	int indext;
    	for(i=0;i<G->vexnum;i++)//算入度 
    	{
    		indext=0;
    		for(j=0;j<G->vexnum;j++)
    		if(G->arcs[i][j]==1)
    		{
    			indext++;	
    		}
    		A[i].out=indext;
    	}
    	
    	for(i=0;i<G->vexnum;i++)//算出度 
    	{
    		indext=0;
    		for(j=0;j<G->vexnum;j++)
    		if(G->arcs[j][i]==1)
    		{
    			indext++;
    		}
    		A[i].in=indext;
    	}
    	
    	
    	for(i=0;i<G->vexnum;i++)//算总度 
    	{
    		A[i].total=A[i].in+A[i].out;
    	}
    	
    	for(i=0;i<G->vexnum;i++)
    	printf("%c %d %d %d\n",G->vex[i],A[i].out,A[i].in,A[i].total);
    }
    
    void DFS(Adjmatrim *G,int n)
    {
    	printf("%c",G->vex[n]);
    	visited[n]=1;
    	int w=First_Adjmatrim_VEX(G,n);
    	while(w!=-1)
    	{
    		if(!visited[w])
    		DFS(G,w);
    		w=Next_Adjmatrim_vex(G,n,w);
    	}
    }
    
    void TraverseG(Adjmatrim *G)  //深度优先遍历 
    {
    	int i;
    	for(i=0;i<MAXVEX;i++)
    	visited[i]=0;
    	for(i=0;i<G->vexnum;i++)
    	if(!visited[i])
    	DFS(G,i);
    }
    
    int Next_Adjmatrim_vex(Adjmatrim *G,int n,int w)//寻找下一个结点 
    {
    	int i;
    	int flag=-1;
    	for(i=w+1;i<G->vexnum;i++)
    	if(G->arcs[n][i]!=-1 )//
    	{
    		flag=i;break;
    	}
    //	printf("Next %d\n",flag);
    	return flag;
    		
    } 
     
    int First_Adjmatrim_VEX(Adjmatrim *G,int n)//寻找第一个结点 
    {
    	int i;
    	for(i=0;i<G->vexnum;i++)
    	{
    		if(G->arcs[n][i]!=-1)
    		{
    //			printf("First %d\n",i);
    			return i;
    		}
    	}
    }
    /*
    void BFS(Adjmatrim *G,int v0) 
    {
    	int w,v;
    	QUEQUE Q=Create_QUEQUE();
    	if(v0<G->vexnum)
    	printf("%c",G->vex[v0]);
    	visited[v0]=1;
    	input_QUEQUE(Q,v0);
    	while(!Empty(QUEQUE(Q)))
    	{
    		out_QUEQUE(Q,&v);
    		w=First_Adjmatrim_VEX(G,v);
    		while(w!=-1)
    		{
    			if(visited[w]!=1)
    			{
    				if(w<G->vexnum)
    				printf("%c",G->vex[w]);
    				visited[w]=1;
    				input_QUEQUE(Q,w);
    			}
    			w=Next_Adjmatrim_vex(G,v,w);	
    		}
    	 } 
    }
    */
    void BFS(Adjmatrim *G,int v0) 
    {
    	QUEQUE Q=Create_QUEQUE();
    	printf("%c",G->vex[v0]);
    	visited[v0]=1;
    	input_QUEQUE(Q,v0);
    	while(!Empty(Q))
    	{
    		int v;
    		out_QUEQUE(Q,&v);
    		int w=First_Adjmatrim_VEX(G,v);
    		while(w!=-1)
    		{
    			if(visited[w]!=1)
    			{
    				printf("%c",G->vex[w]);
    				visited[w]=1;
    				input_QUEQUE(Q,w);
    			}
    			w=Next_Adjmatrim_vex(G,v,w);
    		}
    	}
    }
    
    
    void TraverseG_BFS(Adjmatrim *G)  //深度优先遍历 
    {
    	int i;
    	for(i=0;i<MAXVEX;i++)
    	visited[i]=0;
    	for(i=0;i<G->vexnum;i++)
    	if(!visited[i])
    	BFS(G,i);
    }
    
    
    void out_QUEQUE(QUEQUE Q,int *w)
    {
    	if(!Empty(Q))
    	{
    		*w=Q->vex[Q->rear];
    		Q->rear--;
    	}
    } 
    
    void input_QUEQUE(QUEQUE Q,int w)
    {
    	Q->rear++;
    	Q->vex[Q->rear]=w;
    }
    
    int Empty(QUEQUE Q)
    {
    	if(Q->rear==-1)
    	return 1;
    	else 
    	return 0;
    } 
    
    QUEQUE Create_QUEQUE()
    {
    	QUEQUE Q=(QUEQUE)malloc(sizeof(QUEQUE_1));
    	Q->front=Q->rear=-1;
    	return Q;
    }
    
    
    
    /*
    5 7
    ABCDE
    AB
    AE
    BC
    CD
    DA
    DB
    EC 
    
    */

运行结果：

不输出领接矩阵

![2019120113521793.png][]

输出领接矩阵

![20191201135248983.png][]

[2019120113521793.png]: https://img-blog.csdnimg.cn/2019120113521793.png
[20191201135248983.png]: https://img-blog.csdnimg.cn/20191201135248983.png