存档：
#include <stdio.h>
#include <stdlib.h>
#define maxv 10
#define max 10
typedef char elem;
typedef int elemtype;
#include "queue.h"
#include "mgraph.h"
void main()
{
mgraph g;
printf("1.初始化函数测试:\n");
initial(g);
printf("2.创建函数测试:\n");
create(g);
printf("3.输出函数测试:\n");
printg(g);
printf("4.输出顶点度函数测试:\n");
degree(g);
printf("5.深度优先遍历函数测试:\n");
dfstraverse(g);
printf("6.广度优先遍历函数测试:\n");
bfs(g);
}
//有向图的邻接矩阵,顶点数据为字符型
typedef struct MGraph
{
elem vexes[maxv];//顶点表
int edges[maxv][maxv];//邻接矩阵
int n,e;//顶点数n和边数e
}mgraph;
bool visited[maxv];//访问标志数组
void initial(mgraph &g)//初始化函数
{
int i,j;
g.e=;
g.n=;
for(j=;j<maxv;j++)
g.vexes[j]=;//建立顶点表
for(i=;i<maxv;i++)
{
for(j=;j<maxv;j++)
{
g.edges[i][j]=;//初始化邻接矩阵
}
}
}
int locate(mgraph g,elem u)//查找顶点对应的数组下标值
{
for(int i=;i<g.n;i++)
{
if(g.vexes[i]==u)
return i;
}
return -;
}
void create(mgraph &g)//创建图的邻接矩阵存储
{
int i,j,k;
elem u,v;
printf("请输入有向图的顶点数:");
scanf("%d",&g.n);
printf("请输入有向图的弧数:");
scanf("%d",&g.e);
fflush(stdin);//清空缓存中的数据
printf("请输入字符型顶点数据,如ABCD:");
for(j=;j<g.n;j++)
scanf("%c",&g.vexes[j]);//建立顶点表
fflush(stdin);
printf("请输入弧的信息,格式:弧尾,弧头\n");
for(k=;k<g.e;k++)
{
scanf("%c,%c",&u,&v);
i=locate(g,u);
j=locate(g,v);
g.edges[i][j]=;
fflush(stdin);
}
}
void printg(mgraph g)//输出有向图的邻接矩阵
{
int i,j;
printf("输入图的邻接矩阵存储信息:\n");
printf("顶点数据:\n");
for(i=;i<g.n;i++)
printf("%d:%c\n",i,g.vexes[i]);
printf("邻接矩阵数据:\n");
for(i=;i<g.n;i++)
{
for(j=;j<g.n;j++)
{
printf("%3d",g.edges[i][j]);
}
printf("\n");
}
}
void degree(mgraph g)//输出顶点的度
{
int i,j,in,out;
for(i=;i<g.n;i++)
{
in=;
out=;
for(j=;j<g.n;j++)
{
if(g.edges[i][j]!=)
out++;
if(g.edges[j][i]!=)
in++;
}
printf("顶点%c的出度为%d---入度为%d---度为%d\n",g.vexes[i],out,in,in+out);
}
}
int firstadjvex(mgraph g,int v)//顶点v的第一个邻接顶点
{
for(int i=;i<g.n;i++)
{
if(g.edges[v][i]==)
return i;
}
return -;
}
int nextadjvex(mgraph g,int v,int w)//顶点v的相对于w的下一个邻接顶点
{
for(int i=w+;i<g.n;i++)
{
if(g.edges[v][i]==)
return i;
}
return -;
}
void dfs(mgraph g,int v)//遍历一个连通分量
{
int w;
visited[v]=true;
printf("%c ",g.vexes[v]);
for(w=firstadjvex(g,v);w>=;w=nextadjvex(g,v,w))
{
if(!visited[w])
dfs(g,w);
}
}
void dfstraverse(mgraph g)//深度优先遍历
{
int v;
for(v=;v<g.n;v++)
visited[v]=false;//标志访问数组初始化
for(v=;v<g.n;v++)
{
if(!visited[v])
dfs(g,v);
}
}
void bfs(mgraph g)//广度优先遍历
{
int u=,v=,w=;
queue q;
for(v=;v<g.n;v++)
visited[v]=false;
initqueue(q);
for(v=;v<g.n;v++)
{
if(!visited[v])
{
visited[v]=true;
printf("%c ",g.vexes[v]);
enqueue(q,v);
while(!queueempty(q))
{
dequeue(q,u);
for(w=firstadjvex(g,u);w>=;w=nextadjvex(g,u,w))
{
if(!visited[w])
{
visited[w]=true;
printf("%c ",g.vexes[w]);
enqueue(q,w);
}
}
}
}
}
destroyqueue(q);
}
typedef struct
{
elemtype *base;//动态分配存储空间
int front;//头指针,若队列不空指向队列头元素
int rear;//尾指针,若队列不空指向队列尾元素的下一个位置
}queue;
void initqueue(queue &q)//初始化队列
{
q.base=new elemtype[max];//分配存储空间
if(!q.base)
{
printf("队列分配失败\n");
exit(-);
}
else
q.front=q.rear=;
}
int queueempty(queue q)//判断队列是否为空
{
if(q.front==q.rear)
return ;
else
return ;
}
void enqueue(queue &q,elemtype e)//入队列操作
{
if((q.rear+)%max==q.front)
{
printf("队满,无法插入新元素!\n");
exit(-);
}
else
{
q.base[q.rear]=e;
q.rear=(q.rear+)%max;
}
}
void dequeue(queue &q,elemtype e)//出队列操作
{
if(q.front==q.rear)//判断队列是否为空
{
printf("空队列,无法删除头元素!\n");
exit(-);
}
else
{
e=q.base[q.front];
q.front=(q.front+)%max;
}
}
void destroyqueue(queue &q)//销毁队列
{
free(q.base);
q.base=NULL;
q.front=;
q.rear=;
printf("\n");
}
运行结果如下：
