//图
#include <stdio.h>
#include <stdlib.h>
#define MaxNum 100
typedef char Type;
//邻接矩阵类型定义
typedef struct
{
Type vexs[MaxNum];
int edges[MaxNum][MaxNum];
int Vertex_num,edge_num;
}MGraph;
//邻接表类型定义
typedef struct node
{
int adjvex;
struct node *next;
}EdgeNode;
typedef struct
{
struct
{
Type vertex;
EdgeNode * firstedge;
}VertexNode[MaxNum];
int Vertex_num,edge_num;
}ALGraph;
//为图G建立邻接矩阵
void CreateMGraph(MGraph *G)
{
int i,j,k;
printf("请输入顶点数：");
scanf("%d",&G->Vertex_num);//输入顶点数和边数
printf("请输入边数：");
scanf("%d",&G->edge_num);
printf("请输入顶点数信息（例如：若有5个顶点，则连续输入ABCDE）：");
flushall();
for(i=0;i<G->Vertex_num;i++)
{
scanf("%c",&G->vexs[i]); //输入顶点信息，建立顶点表
}
for(i=0;i<G->Vertex_num;i++) //初始化邻接矩阵各元素值为0
for(j=0;j<G->Vertex_num;j++)
G->edges[i][j]=0;
printf("注意：顶点序列对应点的序号是从0起始编号，即0,1,2,···\n");
printf("请输入每条边对应的两个顶点的序号（输入格式为：i,j<cr>）:\n");
for(k=0;k<G->edge_num;k++)
{
for(i=0;i<G->Vertex_num;i++)
printf("%c(%d)",G->vexs[i],i);
printf("\n");
printf("请输入第%d条边：",k+1);
scanf("%d,%d",&i,&j); //输入e条边，建立邻接矩阵
if(i<0 || i>=G->Vertex_num || j<0 || i>=G->Vertex_num)
{
printf("输入出错！\n");
k--;
continue;
}
printf("(%c--%c)\n",G->vexs[i],G->vexs[j]);
G->edges[i][j]=1;
G->edges[j][i]=1; //若为有向图建立邻接矩阵，该句舍弃
}
}
//深度优先搜索遍历函数
//第一个形参MGraph * G是指要遍历的图的存储结构
//第二个形参int v是指从序号为V的顶点开始深度优先遍历图
//第三个形参int *visited指向访问数组，指示顶点是否被访问过
void dfs(MGraph *G,int v,int *visited)
{
int i;
*(visited+v)=1; //标识序号为v的顶点被访问过
printf("访问过的顶点式：%d---%c\n",v,G->vexs[v]);
for(i=0;i<G->Vertex_num;i++) //查找当前顶点的邻接顶点
if(G->edges[v][i]=1) //邻接顶点找到
if(*(visited+i)!=1)
dfs(G,i,visited);
}
void clear() //清屏
{
system("pause");
system("cls");
}
//深度优先遍历图
void Depth_first_graph(MGraph *G)
{
int visited[MaxNum];
int i;
//初始化visited数组，该数组每一个元素对应图的一个顶点，用来标识顶点是否被访问过
for(int i=0;i<MaxNum;i++)
visited[i]=0;
i=0;
do
{
printf("从顶点%c开始进行深度优先遍历\n",G->vexs[i]);
dfs(G,i,visited); //对图进行深度优先搜索遍历
for(;i<G->Vertex_num;i++)
if(visited[i]==0)
break;
}while(i<G->Vertex_num);
}
//为图G建立邻接表
void CreateALGraph(ALGraph *G)
{
int i,j,k;
EdgeNode *s;
printf("请输入顶点数");
scanf("%d",&G->Vertex_num);
printf("请输入边数:");
scanf("%d",&G->edge_num);
printf("请输入顶点信息（例如：若有5个顶点，则连续输入ABCDE）:");
flushall();
for(i=0;i<G->Vertex_num;i++)
{
scanf("%c",&G->VertexNode[i].vertex);
G->VertexNode[i].firstedge=NULL;
}
printf("注意：顶点的序列对应的序号从0开始编号，即0,1,2,···\n");
printf("请输入每条边对应的两个顶点的序号（输入格式为:ij<cr>）:\n");
for(k=0;k<G->edge_num;k++)
{
for(i=0;i<G->Vertex_num;i++)
printf("%c(%d)",G->VertexNode[i].vertex,i);
printf("\n");
printf("请输入第%d条边:",k+1);
scanf("%d,%d",&i,&j); //读入边的两顶点的对应的序号
if(i<0||i>=G->Vertex_num||j<0||i>=G->Vertex_num)
{
printf("输入出错！\n");
k--;
continue;
}
printf("(%c--%c)\n",G->VertexNode[i].vertex,G->VertexNode[j].vertex);
s=new(EdgeNode);
s->adjvex=j; //邻接点序号为j
s->next=G->VertexNode[i].firstedge;
G->VertexNode[i].firstedge=s;
s=new(EdgeNode); //再申请一个新边表结点
s->adjvex=i; //邻接点序号为i
s->next=G->VertexNode[j].firstedge; //将新边表结点s插入到序号为J的顶点的边表头部
G->VertexNode[j].firstedge=s;
}
}
//孤独优先搜索遍历函数
//第一个形参ALGraph *G是指要遍历的图的存储结构
//第二个形参int V 是指从序号为V的顶点开始广度优先遍历图
//第三个形参int *visited指向访问数组，表示顶点是否被访问过
void bfs(ALGraph *G,int v,int *visited)
{
int quene[MaxNum],front=0,rear=1; //定义一个队列
EdgeNode *p; //定义边指针
*(visited+v)=1;
printf("现在访问的顶点式:%d--%c\n",v,G->VertexNode[v].vertex); //输出正访问的顶点
if(front==rear)
exit(1);//队列满，溢出
quene[rear]=v;//把访问过的点放入队列中
rear=(rear+1)%MaxNum;
while((front+1)!=rear) //队列不空
{
front=(front+1)%MaxNum; //一个顶点出队
v=quene[front];
p=G->VertexNode[v].firstedge;
while(p)
{
if(visited[p->adjvex]==0)//判断p->adjvex是否被访问过
{
visited[p->adjvex]=1; //若没有，则对其进行访问
printf("访问的顶点是:%d--%c\n",p->adjvex,G->VertexNode[p->adjvex].vertex);//输出正访问的结点
if(front==rear)
exit(1);
quene[rear]=p->adjvex;
rear=(rear+1)%MaxNum;
}
p->next;
}
}
}
//广度优先遍历图
void Breadth_first_graph(ALGraph *G)
{
int i,visited[MaxNum];
//初始化visited数组，该数组的每一个元素对应图的每一个顶点是否被访问过
for(i=0;i<MaxNum;i++)
visited[i]=0;
i=0;
do
{
printf("从顶点%c开始进行广度优先搜索遍历\n",G->VertexNode[i].vertex);
bfs(G,i,visited);//对图进行深度优先搜索遍历
for(;i<G->Vertex_num++;i++)
if(visited[i]==0)
break;
}while(i<G->Vertex_num);
}
void showmenu()
{
printf("\n\n\n");
printf(" --图的遍历-- \n");
printf("****************************************************\n");
printf("* 1------用邻接矩阵表表示一个图 *\n");
printf("* 2------深度优先搜索遍历图（邻接矩阵表） *\n");
printf("* 3------用邻接表表示一个图 *\n");
printf("* 4------广度优先搜索遍历图（邻接矩阵表） *\n");
printf("* *\n");
printf("* 0------退出 *\n");
printf("****************************************************\n");
printf("请选择菜单号（0-4）:");
}
void graphOP()
{
char choice ='N';
int adjacency_martrix=0;
int adjacency_list=0;//标志位邻接表是否存在
MGraph G;
ALGraph T;
while(choice!=0)
{
showmenu();
flushall();
scanf("%c",&choice);
switch(choice)
{
case '1':
CreateMGraph(&G);
adjacency_martrix=1;
clear();
break;
case '2':
if(adjacency_martrix)
{
Depth_first_graph(&G);
}
else
{
printf("请先输入图的顶点信息！\n");
}
clear();
break;
case '3':
CreateALGraph(&T);//创建图的邻接表
adjacency_list=1;
clear();
break;
case '4':
if(adjacency_list)
{
Breadth_first_graph(&T);
}
else
{
printf("请输入图的顶点信息！\n");
}
clear();
break;
case '0':
printf("\n\t程序结束！\n");
break;
default:
printf("\n\t输入错误，请重新输入！\n");
}
}
}
void main()
{
graphOP();
}
