#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100
#define MAXEDGE 100
#define INFINITY 65535
#define MAXSIZE 100
typedef int Status; /* Status是函数的类型 */
typedef int VertexType; /* 顶点类型 */
typedef int EdgeType; /* 边上的权值类型 */
typedef int Boolean;
Boolean visited[MAXVEX];
typedef struct
{
VertexType vexs[MAXVEX]; /* 顶点表 */
EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵，看作边表 */
int numNodes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;
typedef struct EdgeNode /* 边表结点 */
{
int adjvex; /* 邻接点域,存储该顶点对应的下标 */
int weight; /* 用于存储权值,对于非网图可以不需要(手绘图） */
struct EdgeNode *next; /* 链域,指向下一个邻接点 */
}EdgeNode;
typedef struct VertexNode /* 顶点表结点 */
{
int in; /* 顶点入度 */
int data; /* 顶点域,存储顶点信息 */
EdgeNode *firstedge;/* 边表头指针 */
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numNodes, numEdges; /* 图中当前顶点数和边数 */
}graphAdjList,*GraphAdjList;
typedef struct /*对边集数组Edge结构的定义*/
{
int begin;
int end;
int weight;
}Edge;
typedef struct
{
int data[MAXSIZE];
int front; /* 头指针 */
int rear; /* 尾指针 */
}Queue;
Status InitQueue(Queue *Q) /* 初始化空队列Q */
{
Q->front=0;
Q->rear=0;
return OK;
}
Status QueueEmpty(Queue Q) /*判断队列是否为空*/
{
if(Q.front==Q.rear) /* 队列空的标志 */
return TRUE;
else
return FALSE;
}
Status EnQueue(Queue *Q,int e) /*队列插入操作*/
{
if ((Q->rear+1)%MAXSIZE == Q->front) /* 队列满的判断 */
return ERROR;
Q->data[Q->rear]=e; /* 将元素e赋给队尾 */
Q->rear=(Q->rear+1)%MAXSIZE; /* rear指针向后移一位置， */
/* 若到最后则转到数组头部 */
return OK;
}
Status DeQueue(Queue *Q,int *e) /*队列删除操作*/
{
if (Q->front == Q->rear) /* 队列空的判断 */
return ERROR;
*e=Q->data[Q->front]; /* 将队头元素赋值给e */
Q->front=(Q->front+1)%MAXSIZE; /* front指针向后移一位置， */
/* 若到最后则转到数组头部 */
return OK;
}
Status CreateMGraph(MGraph *G) /* 无向网图邻接矩阵表示 */
{
int i,j,k,w;
//char v[1000];
printf("输入顶点数和边数:\n");
scanf("%d%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */
for(i=0;i<G->numNodes;i++)
//scanf(&G->vexs[i]);
G->vexs[i]=i; /* 建立顶点表 */
for(i=0;i<G->numNodes;i++)
for(j=0;j<G->numNodes;j++)
{
if(i==j)
G->arc[i][j]=0;
else
G->arc[i][j]=INFINITY;
}
printf("对于非网图另权为1\n"); /* 邻接矩阵初始化 */
for(k=0;k<G->numEdges;k++) /* 建立邻接矩阵 */
{
printf("输入第%d条边(vi,vj)上的下标i，下标j和权w:\n",k+1);
scanf("%d%d%d",&i,&j,&w);
G->arc[i][j]=w;
G->arc[j][i]= G->arc[i][j]; /* 无向图，矩阵对称 */
}
PrintGraph(G);
return OK;
}
Status CreateDGraph(MGraph *G) /* 有向网图邻接矩阵表示 */
{
int v1,v2,i,j,k,w;
//char ch;
printf("图顶点数和弧数："); /*确定图顶点数和边数*/
scanf("%d%d",&G->numNodes,&G->numEdges);
//ch=getchar();
for(i=0;i<G->numNodes;i++) /*定义顶点名称*/
{
printf("第%d个顶点：v",i+1);
scanf("%d",&G->vexs[i]);
//ch=getchar();
}
for(i=0;i<G->numNodes;i++) /*初始化邻接矩阵*/
for(j=0;j<G->numNodes;j++)
{
if(i==j)
G->arc[i][j]=0;
else
G->arc[i][j]=INFINITY;
}
for(k=1;k<=G->numEdges;k++) /*带方向邻接矩阵构建*/
{
printf("输入第%d条边两个顶点，第一个为弧尾，第二个为弧头和权值w：\n",k);
printf("v");
scanf("%d",&v1);
printf("v");
scanf("%d",&v2);
printf("权值w：");
scanf("%d",&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
//printf("%d %d",i,j);
G->arc[i][j]=w; /*赋权*/
}
PrintGraph(G); /*打印出有向图的邻接矩阵*/
return OK;
}
void CreateALGraph(MGraph G,GraphAdjList *G1)
{
int i,j;
EdgeNode *e;
*G1 = (GraphAdjList)malloc(sizeof(graphAdjList));
(*G1)->numNodes=G.numNodes;
(*G1)->numEdges=G.numEdges;
for(i= 0;i <G.numNodes;i++) /* 读入顶点信息,建立顶点表 */
{
(*G1)->adjList[i].in=0;
(*G1)->adjList[i].data=G.vexs[i];
(*G1)->adjList[i].firstedge=NULL; /* 将边表置为空表 */
}
for(i=0;i<G.numNodes;i++) /* 建立边表 */
{
for(j=0;j<G.numNodes;j++)
{
if (G.arc[i][j]==1)
{
e=(EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex=j; /* 邻接序号为j */
e->next=(*G1)->adjList[i].firstedge; /* 将当前顶点上的指向的结点指针赋值给e */
(*G1)->adjList[i].firstedge=e; /* 将当前顶点的指针指向e */
(*G1)->adjList[j].in++;
}
}
}
}
void DispGraphAdjList(GraphAdjList *G1)
{
int i;
EdgeNode *p;
printf("图的邻接表表示如下\n");
printf("%6s%6s%2s%12s\n","编号"," ","顶点","相邻边编号");
for(i=0;i<(*G1)->numNodes;i++)
{
printf("%4d v%d",i,(*G1)->adjList[i].data);//
for(p=(*G1)->adjList[i].firstedge;p!=NULL;p=p->next)
printf("%6d",p->adjvex);
printf("\n");
}
}
Status DestroyMGraph(MGraph G) /*销毁表*/
{
G.numEdges=NULL;
G.numNodes=NULL;
return OK;
}
Status LocateVex(MGraph *G,int v) /*找出任意顶点在顶点集中的编号*/
{
int a=0,i;
for(i=0;i<G->numNodes;i++)
{
if(v==G->vexs[i])
{
return a;
}
else
a++;
}
if(v>=G->numNodes)
{
return FALSE;
}
}
Status PrintGraph(MGraph *G) /*打印图*/
{
int i,j;
printf("图中顶点有%3d个，分别为：",G->numNodes);
for(i=0;i<G->numNodes;i++)
printf("v%d ",G->vexs[i]);
printf("\n邻接矩阵关系：\n");
for(i=0;i<G->numNodes;i++)
{
for(j=0;j<G->numNodes;j++)
{
if(G->arc[i][j]==INFINITY)
printf(" ∞");
else
printf("%6d",G->arc[i][j]);
}
printf("\n");
}
return OK;
}
void DFS(MGraph G,int i) /*邻接矩阵的深度遍历算法*/
{
int j;
visited[i]=TRUE;
printf("v%d ",G.vexs[i]);
for(j=0;j<G.numNodes;j++)
if(G.arc[i][j]==1&&!visited[j])
DFS(G,j);
}
void DFSTraverse(MGraph G) /*邻接矩阵的深度优先递归算法*/
{
int i;
for(i=0;i<G.numNodes;i++)
visited[i]=FALSE;
for(i=0;i<G.numNodes;i++)
if(!visited[i])
DFS(G,i);
}
void DFS1(GraphAdjList G1,int i) /*邻接表的深度遍历算法*/
{
EdgeNode *p;
visited[i]=TRUE;
printf("v%d ",G1->adjList[i].data);
p=G1->adjList[i].firstedge;
while(p)
{
if(!visited[p->adjvex])
DFS1(G1,p->adjvex);
p=p->next;
}
}
void DFSTraverse1(GraphAdjList G1) /*邻接表的深度优先递归算法*/
{
int i;
for(i=0;i<G1->numNodes;i++)
visited[i]=FALSE;
for(i=0;i<G1->numNodes;i++)
if(!visited[i])
DFS1(G1,i);
}
void BFSTraverse(MGraph G) /*邻接矩阵的广度遍历算法*/
{
int i, j;
Queue Q; /*定义队列Q*/
for(i=0; i< G.numNodes; i++)
visited[i] = FALSE;
InitQueue(&Q); /* 初始化队列 */
for(i = 0; i < G.numNodes; i++)
{
if (!visited[i]) /* 未访问过处理 */
{
visited[i]=TRUE; /* 设置当前顶点访问过 */
printf("v%d ", G.vexs[i]); /* 打印顶点*/
EnQueue(&Q,i); /* 顶点入队 */
while(!QueueEmpty(Q)) /* 若当前队列不为空 */
{
DeQueue(&Q,&i); /* 将队对元素出队列，赋值给i */
for(j=0;j<G.numNodes;j++)
{
if(G.arc[i][j] == 1 && !visited[j]) /* 判断其它顶点若与当前顶点存在边且未访问过 */
{
visited[j]=TRUE; /* 将找到的此顶点标记为已访问 */
printf("v%d ", G.vexs[j]); /* 打印顶点 */
EnQueue(&Q,j); /* 将找到的此顶点入队列 */
}
}
}
}
}
}
void BFSTraverse1(GraphAdjList G1) /*邻接表的广度遍历算法*/
{
int i;
EdgeNode *p;
Queue Q;
for(i = 0; i < G1->numNodes; i++)
visited[i] = FALSE;
InitQueue(&Q);
for(i = 0; i < G1->numNodes; i++)
{
if (!visited[i])
{
visited[i]=TRUE;
printf("v%d ",G1->adjList[i].data);/* 打印顶点 */
EnQueue(&Q,i);
while(!QueueEmpty(Q))
{
DeQueue(&Q,&i);
p = G1->adjList[i].firstedge; /* 找到当前顶点的边表链表头指针 */
while(p)
{
if(!visited[p->adjvex]) /* 若此顶点未被访问 */
{
visited[p->adjvex]=TRUE;
printf("v%d ",G1->adjList[p->adjvex].data);
EnQueue(&Q,p->adjvex); /* 将此顶点入队列 */
}
p = p->next; /* 指针指向下一个邻接点 */
}
}
}
}
}
void MiniSpanTree_Prim(MGraph *G)/* Prim算法生成最小生成树 */
{
int min, i, j, k;
int adjvex[MAXVEX]; /* 保存相关顶点下标 */
int lowcost[MAXVEX]; /* 保存相关顶点间边的权值 */
lowcost[0] = 0; /* 初始化第一个权值为0，即v0加入生成树 */
/* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */
adjvex[0] = 0; /* 初始化第一个顶点下标为0 */
for(i = 1; i < G->numNodes; i++) /* 循环除下标为0外的全部顶点 */
{
lowcost[i] = G->arc[0][i]; /* 将v0顶点与之有边的权值存入数组 */
adjvex[i] = 0; /* 初始化都为v0的下标 */
}
for(i = 1; i < G->numNodes; i++)
{
min = INFINITY; /* 初始化最小权值为∞， */
/* 通常设置为不可能的大数字如32767、65535等 */
j = 1;
k = 0;
while(j < G->numNodes) /* 循环全部顶点 */
{
if(lowcost[j]!=0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */
{
min = lowcost[j]; /* 则让当前权值成为最小值 */
k = j; /* 将当前最小值的下标存入k */
}
j++;
}
printf("(%d, %d)\n", adjvex[k], k);/* 打印当前顶点边中权值最小的边 */
lowcost[k] = 0; /* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */
for(j = 1; j < G->numNodes; j++) /* 循环所有顶点 */
{
if(lowcost[j]!=0 && G->arc[k][j] < lowcost[j])
{ /* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
lowcost[j] = G->arc[k][j];/* 将较小的权值存入lowcost相应位置 */
adjvex[j] = k; /* 将下标为k的顶点存入adjvex */
}
}
}
}
void Swapn(Edge *edges,int i, int j)/* 交换权值 以及头和尾 */
{
int temp;
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
void sort(Edge edges[],MGraph *G)/* 对权值进行排序 */
{
int i, j;
for ( i = 0; i < G->numEdges; i++)
{
for ( j = i + 1; j < G->numEdges; j++)
{
if (edges[i].weight > edges[j].weight)
{
Swapn(edges, i, j);
}
}
}
printf("权排序之后的为:\n");
for (i = 0; i < G->numEdges; i++)
{
printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
int Find(int *parent, int f)/* 查找连线顶点的尾部下标 */
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}
void MiniSpanTree_Kruskal(MGraph G)/* 生成最小生成树 */
{
int i, j, n, m;
int k = 0;
int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */
Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 */
for ( i = 0; i < G.numNodes-1; i++)/* 用来构建边集数组并排序*/
{
for (j = i + 1; j < G.numNodes; j++)
{
if (G.arc[i][j]<INFINITY)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G.arc[i][j];
k++;
}
}
}
sort(edges, &G);
for (i = 0; i < G.numNodes; i++)
parent[i] = 0; /* 初始化数组值为0 */
printf("打印最小生成树：\n");
for (i = 0; i < G.numEdges; i++) /* 循环每一条边 */
{
n = Find(parent,edges[i].begin);
m = Find(parent,edges[i].end);
if (n != m) /* 假如n与m不等，说明此边没有与现有的生成树形成环路 */
{
parent[n] = m; /* 将此边的结尾顶点放入下标为起点的parent中。 */
/* 表示此顶点已经在生成树集合中 */
printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
int main()
{
int a,u,m,end_loop=0;
char value;
MGraph G;
GraphAdjList G1;
printf("*******************************************************************\n");
printf("************-> case 0:结束循环退出 ****************\n");
printf("************-> case 1:定义构造图（邻接矩阵）无向图 ****************\n");
printf("************-> case 2:定义构造图（邻接矩阵）有向图 ****************\n");
printf("************-> case 3:定义构造图（邻接表) ****************\n");
printf("************-> case 4:销毁图 ****************\n");
printf("************-> case 5:查找顶点集vex[i]中一点的标号 ****************\n");
printf("************-> case 6:输出当前图(邻接矩阵） ****************\n");
printf("************-> case 7:邻接矩阵的DFS深度优先遍历 ****************\n");
printf("************-> case 8:邻接表的DFS深度优先遍历 ****************\n");
printf("************-> case 9:邻接矩阵的BFS广度优先遍历 ****************\n");
printf("************-> case 10:邻接表的BFS广度优先遍历 ****************\n");
printf("************-> case 11:prim算法求最小生成树 ****************\n");
printf("************-> case 12:kruskal算法求最小生成树 ****************\n");
printf("************-> case 13:邻接表建表生成 ****************\n");
printf("*******************************************************************\n");
while(scanf("%d",&a)!=EOF)
{
switch(a)
{
case 0:end_loop=1;break;
case 1:{
CreateMGraph(&G);
printf("************-> case 4:销毁图 ****************\n");
printf("************-> case 6:输出当前图(邻接矩阵） ****************\n");
printf("************-> case 7:邻接矩阵的DFS深度优先遍历 ****************\n");
printf("************-> case 9:邻接矩阵的BFS广度优先遍历 ****************\n");
printf("************-> case 11:prim算法求最小生成树 ****************\n");
printf("************-> case 12:kruskal算法求最小生成树 ****************\n");
break;
}
case 2:CreateDGraph(&G);break;
case 3:{
CreateMGraph(&G); /*以邻接矩阵读入数据后生成邻接表*/
CreateALGraph(G,&G1);
DispGraphAdjList(&G1);
printf("************-> case 4:销毁图 ****************\n");
printf("************-> case 8:邻接表的DFS深度优先遍历 ****************\n");
printf("************-> case 10:邻接表的BFS广度优先遍历 ****************\n");
printf("************-> case 13:邻接表建表生成 ****************\n");
break;
}
case 4:{
DestroyMGraph(G);
printf("图已销毁！\n");
printf("\n");
break;
}
case 5:{
printf("输入要查找的顶点:v");
scanf("%d",&u);
m=LocateVex(&G,u);
if(m==-1)
printf("出错！\n");
else
printf("查找顶点的数组编号为：%d\n",m);
break;
}
case 6:PrintGraph(&G);printf("\n");break;
case 7:DFSTraverse(G);printf("\n");break;
case 8:DFSTraverse1(G1);printf("\n");break;
case 9:BFSTraverse(G);printf("\n");break;
case 10:BFSTraverse1(G1);printf("\n");break;
case 11:MiniSpanTree_Prim(&G);printf("\n");break;
case 12:MiniSpanTree_Kruskal(G);printf("\n");break;
case 13:DispGraphAdjList(&G1);printf("\n");break;
}
if(end_loop==1)
break;
}
return 0;
}
