#include<stdio.h>
#include<malloc.h>
typedef struct node//表结点
{
int adjvex;//邻接点域 存放顶点序号
struct node *next;//指向下一个邻接点的指针域
int info;//权重
}EdgeNode;
typedef struct vnode
{
int vertex; // 顶点域
EdgeNode *firstedge; // 边表头指针
}VertexNode;
typedef struct
{
VertexNode adjlist[10]; //邻接表
int n,e;//顶点数，边数
char a[10];
}ALGraph; //ALGraph是以邻接表方式存储的图
//以出度和入读建立邻接表
void CreateALGraph(ALGraph *G,ALGraph *G2)
{
int i,j,k,qz;
EdgeNode *s,*d;
printf("请输入顶点数:");
scanf("%d",&(G->n));G2->n=G->n;
printf("请输入边数:");
scanf("%d",&(G->e));G2->e=G->e;
printf("-------------------------------------\n");
printf("请输入顶点信息(输入格式为:<回车>顶点号,顶点):\n");
for(i=0;i<G->n;i++)
{
printf("请输入第%d个顶点的信息:",i+1);
scanf("\n%d,%c",&(G->adjlist[i].vertex),&G->a[i]);//读入顶点信息
G->adjlist[i].firstedge=NULL;//顶点的边表头指针设为空
G2->adjlist[i].vertex=G->adjlist[i].vertex;
G2->a[i]=G->a[i];//读入顶点信息
G2->adjlist[i].firstedge=NULL;//顶点的边表头指针设为空
}
printf("-------------------------------------\n");
printf("请输入边表的信息(输入格式为:i,j,权重):\n");
for(k=0;k<G->e;k++) //建立边表
{
printf("请输入第%d个边表的信息:",k+1);
scanf("%d,%d,%d",&i,&j,&qz); //读入边<vi,vj>的顶点对应序号
//以出度---建立G1
s=(EdgeNode *)malloc(sizeof(EdgeNode));//生成新边表结点
s->adjvex=j; //邻接点序号为j
s->next=G->adjlist[i].firstedge;//将边表插入到顶点的边表表头
s->info=qz; //权值
G->adjlist[i].firstedge=s;
//以入度---建立G2
d=(EdgeNode *)malloc(sizeof(EdgeNode));//生成新边表结点
d->adjvex=i; //邻接点序号为i
d->next=G2->adjlist[j].firstedge;//与出度相同的操作
G2->adjlist[j].firstedge=d;
}
printf("邻接表方式存储图建立成功\n\n");
printf("-------------------------------------\n");
}
//计算各顶点的出度入度总度
void Degree(ALGraph *G,ALGraph *G2)
{
int i;
//出度以G中第i个链表中结点的个数
//入度以G2
for(i=0;i<G->n;i++)//i<边数
{
int outnum=0;
int innum=0;
struct node *q,*p;
q=G->adjlist[i].firstedge;
while(q!=NULL)
{
outnum++;q=q->next;
}
p=G2->adjlist[i].firstedge;
while(p!=NULL)
{
innum++;p=p->next;
}
printf("%c顶点的出度是%d\n",G->a[i],outnum);
printf("%c顶点的入度是%d\n",G->a[i],innum);
printf("%c顶点的总度是%d\n\n",G->a[i],outnum+innum);
}
printf("顶点度输出完毕\n\n");
printf("-------------------------------------\n");
}
//计算权值最大的边
void Weights(ALGraph *G)
{
int i,maxi=0,max=0,maxj=0;
struct node *q;
for(i=0;i<G->n;i++)
{
q=G->adjlist[i].firstedge; //遍历每条邻接链表
while(q!=NULL)
{
if(max<G->adjlist[i].firstedge->info) //记录下权值最大的maxi和maxj
{
maxi=i;
maxj=G->adjlist[i].firstedge->adjvex;
max=G->adjlist[i].firstedge->info;
}
q=q->next;
}
}
printf("\n权值最大的边是:%c--->%c 权值为%d\n",G->a[maxi],G->a[maxj],max);
printf("\n");
}
//输出邻边
void Print(ALGraph *G)
{
struct node *q;
int i,j,k,cnt,t;
int b[10];
for(i=0;i<G->n;i++)
{
q=G->adjlist[i].firstedge;
for(cnt=0,j=0;q!=NULL;j++)
{
b[j]=q->adjvex; //保存下标
q=q->next; cnt++;
}
if(cnt==1) ;
else //多于1个排序
for(j=0;j<cnt-1;j++)
for(k=0;k<cnt-i-1;k++)
if(b[k]>b[k+1])
{
t=b[k];
b[k]=b[k+1];
b[k+1]=t;
}
for(j=0;j<cnt;j++) //输出
{
printf("%c---->%c\n",G->a[i],G->a[b[j]]);
}
}
printf("邻边输出完毕.......\n");
printf("-------------------------------------\n");
}
void main()
{
ALGraph G;
ALGraph G2;//创建一个新图---以入度
CreateALGraph(&G,&G2); // 邻接表
Degree(&G,&G2);//每个顶点的出度 入度 总度
Print(&G);//输出邻边
Weights(&G);//权重最大的边
}
