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

#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 

*/

运行结果：

不输出领接矩阵

输出领接矩阵