#include "head.h"
#include "Queue.h"
int visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(VertexType v);
//采用邻接矩阵表示法,构造图G
Status CreateGraph(MGraph &G)
{
printf("请输入图的类型(0为有向图,1为有向网,2为无向图,3为无向网):");
scanf("%d", &G.kind);
switch(G.kind)
{
case DG: return CreateDG(G);
// case DN: return CreateDN(G);
// case UDG:return CreateUDG(G);
// case UDN:return CreateUDN(G);
}
return FALSE;
}
//采用邻接矩阵表示法,构造有向图G
Status CreateDG(MGraph &G)
{
int i, j;
int x, y;
VertexType e1, e2;
printf("请输入顶点个数和弧的条数如(2,3):");
scanf("%d,%d",&G.vexnum, &G.arcnum);
for(i = 0; i < G.vexnum; i++)
{
getchar();
printf("请输入第%d个顶点:", i+1);
scanf("%c", &G.vexs[i]);//输入顶点
}
for(j = 0; j < G.vexnum; j++)//初始化邻接矩阵
{
for(i = 0; i < G.arcnum; i++)
{
G.arcs[j][i].adj = 0;
}
}
for(i = 0; i < G.arcnum; i++)//构造边
{
getchar();
printf("请输入第%d弧,格式如(c,d):", i+1);
scanf("%c,%c", &e1,&e2);//输入边两个顶点
x = LocateVex(G, e1);//确定e1,e2在G中的位置
y = LocateVex(G, e2);
G.arcs[x][y].adj = 1;
}
return TRUE;
}
//确定顶点e在G中的位置
int LocateVex(MGraph &G, VertexType e)
{
int i;
for(i = 0; i < G.vexnum; i++)//循环查找e
{
if(G.vexs[i] == e) //找到则跳出循环
{
break;
}
}
return i; //返回e在图中的位置
}
//v为G中的结点,则返回V的值.否则返回NULL
VertexType GetVex(MGraph &G, VertexType v)
{
int i;
int found = 0;
for(i = 0; i < G.vexnum && !found; i++)//循环查找e
{
if(G.vexs[i] == v)//是否找到
{
found = 1;
}
}
if(found)
{
return v;//找到返回V的值
}
else
{
return NULL;//没找到,返回NULL
}
}
//销毁图G
Status DestroyGraph(MGraph &G)
{
G.arcnum = 0; //边数为0
G.vexnum = 0; //顶点数为0
return TRUE;
}
//v是图G中某个顶点.对v赋值为value
Status PutVex(MGraph &G, VertexType v, VertexType value)
{
int i;
int found = 0;
for(i = 0; i < G.vexnum; i++)//循环查找e
{
if(G.vexs[i] == v)//是否找到
{
found = 1;
break;
}
}
if(found)
{
G.vexs[i] = value;//修改结点的值
return TRUE;
}
else
{
return FALSE;//没找到,返回FLASE
}
}
//v为G中某个顶点,返回v的第一个邻接顶点,若没有
//邻接顶点,则返回NULL
VertexType FirstAdjVex(MGraph G, VertexType v)
{
int i, j;
int found = 0;
i = LocateVex(G, v);//取得v要图G中的位置
for(j = 0; j < G.vexnum; j++)//循环查找第一邻接点
{
if(G.arcs[i][j].adj)
{
found = 1;
break;
}
}//for
if(found)
{
return G.vexs[j];
}//if
else
{
return NULL;
}//else
}
//v为G中的某个顶点,w是v的邻接顶点
//返回v相对于w的下一个邻接顶点.如果w是v的最后一个邻接顶点
//则返回NULL
VertexType NextAdjVex(MGraph G, VertexType v, VertexType w)
{
int i, j;
int found = 0;
i = LocateVex(G, v);//取得v要图G中的位置
j = LocateVex(G, w);//取得w要图G中的位置
for(j++; j < G.vexnum; j++)//循环查找下一个邻接点
{
if(G.arcs[i][j].adj)
{
found = 1;
break;
}
}//for
if(found)
{
return G.vexs[j];
}
else
{
return NULL;
}
}
//在图G中添加顶点v
Status InsertVex(MGraph &G, VertexType v)
{
int i;
if(G.vexnum >= MAX_VERTEX_NUM)//顶点数是否超过最大值
{
return FALSE;
}
G.vexs[G.vexnum] = v;
G.vexnum++; //顶点数加1
for(i = 0; i < G.vexnum; i++)//更新邻接矩阵
{
G.arcs[G.vexnum-1][i].adj = 0;
G.arcs[i][G.vexnum-1].adj = 0;
}
return TRUE;
}
//在图G中删除顶点v
Status DeleteVex(MGraph &G,VertexType v)
{
int i, j, k;
i = LocateVex(G,v);//取得v要图G中的位置
for(j = i; j < G.vexnum; j++)
{
G.vexs[j] = G.vexs[j+1];
for(k = 0; k < G.vexnum; k++)
{
G.arcs[j][k] = G.arcs[j+1][k];
G.arcs[k][j] = G.arcs[k][j+1];
}
}
G.vexnum--; //顶点数减1
return TRUE;
}
//v和w是G中的某个顶点,添加新弧<v,w>无向图时多添加对称弧<w,v>
Status InsertArc(MGraph &G, VertexType v, VertexType w)
{
int i, j;
i = LocateVex(G, v);//取得v要图G中的位置
j = LocateVex(G, w);//取得w要图G中的位置
if(G.kind == DG || G.kind == DN)//图是否是无向的
{
G.arcs[i][j].adj = 1;
}
else
{
G.arcs[i][j].adj = 1;//无向图,则多添加对称弧
G.arcs[j][i].adj = 1;
}
G.arcnum++;//弧数加1
return TRUE;
}
//v和w是G中的某个顶点,删除弧<v,w>,无向图时多删除对称弧<w,v>
Status DeleteArc(MGraph &G, VertexType v, VertexType w)
{
int i, j;
i = LocateVex(G, v);//取得v要图G中的位置
j = LocateVex(G, w);//取得w要图G中的位置
if(G.kind == DG || G.kind == DN)//图是否是无向的
{
G.arcs[i][j].adj = 0;
}
else
{
G.arcs[i][j].adj = 0;//无向图,则多删除对称弧
G.arcs[j][i].adj = 0;
}
G.arcnum--;//弧数减1
return TRUE;
}
//对图作深度优先遍历
void DFSTraverse(MGraph G, Status (*Visit)(VertexType v))
{
int i;
VisitFunc = Visit;
for(i = 0; i < G.vexnum; i++)//访问标志数组初始化
{
visited[i] = 0;
}
for(i = 0; i < G.vexnum; i++)
{
if(!visited[i])
DFS(G, G.vexs[i]);//对尚未访问的顶点调用DFS
}
}
//从第v个顶点出发递归深度优先遍历图G
void DFS(MGraph G, VertexType v)
{
VertexType w;
visited[LocateVex(G,v)] = 1;
VisitFunc(v);//访问第i个结点
for(w = FirstAdjVex(G, v); w; w = NextAdjVex(G, v, w))
{
if(!visited[LocateVex(G, w)])
DFS(G, w);//对尚未访问的顶点递归调用DFS
}
}
//访问顶点v
Status Visit(VertexType v)
{
printf("%c ", v);
return TRUE;
}
//按广度优遍历图G
void BFSTraverse(MGraph G, Status (*Visit)(VertexType v))
{
int i;
VertexType v, w;
LinkQueue Q;
InitQueue(Q);//初始化队列
for(i = 0; i < G.vexnum; i++)//初始化访问标志数组
{
visited[i] = 0;
}
for(i = 0; i < G.vexnum; i++)
{
if(!visited[i]) //i尚未访问
{
visited[i] = 1;
Visit(G.vexs[i]);
EnQueue(Q, G.vexs[i]);//v入队列
while(!QueueEmpty(Q))
{
DeQueue(Q, v); //队列元素出队并置v
for(w = FirstAdjVex(G, v); w; w = NextAdjVex(G, v, w))
{
if(!visited[LocateVex(G, w)])
{
visited[LocateVex(G, w)] = 1;
Visit(w);
EnQueue(Q, w);
}//if
}//for
}//while
}//if
}//for
}//BFSTraverse
int main()
{
int select;
MGraph G;
VertexType v,v1;
CreateGraph(G);
while(1)
{
system("cls");
do{
printf("\n\n\n");
printf("----------------图的抽象数据类型----------------------------\n");
printf("\t\t1.图的深度优先遍历\n");
printf("\t\t2.树的广度优先遍历\n");
printf("\t\t3.添加新顶点\n");
printf("\t\t4.删除顶点\n");
printf("\t\t5.添加新弧\n");
printf("\t\t6.删除弧\n");
printf("\t\t0.退出\n");
printf("-------------------------------------------------------------\n");
printf("Input:");
}while(scanf("%d", &select) && select < 0 && select > 6);
switch(select)
{
case 0:exit(1);
case 1:DFSTraverse(G, Visit);break;
case 2:BFSTraverse(G, Visit);break;
case 3:printf("请输入新顶点:");
getchar();
scanf("%c", &v);
InsertVex(G, v);break;
case 4:printf("请输入要删除的顶点:");
getchar();
scanf("%c", &v);
DeleteVex(G, v);break;
case 5:printf("请输入新弧如(a,b):");
getchar();
scanf("%c,%c", &v,&v1);
InsertArc(G, v, v1);break;
case 6:printf("请输入要删除的弧如(a,b):");
getchar();
scanf("%c,%c", &v,&v1);
DeleteArc(G, v, v1);break;
}
getch();
}
return 1;
}
评论6
最新资源