图的基本操作和实现

图的基本操作与实现

（1）自选存储结构,输入含n个顶点（用字符表示顶点）和e条边的图G；

（2）求每个顶点的度,输出结果；

（3)  指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列(提示:使用一个栈实现DFS)；

  (4)  指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶点序列(提示:使用一个队列实现BFS)；

  (5)  输入顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历(执行操作3)；否则输出信息“无x”；

  (6)  判断图G是否是连通图，输出信息“YES”/“NO”；

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define maxSize 100
using namespace std;
int Count=0;
const int Max=50;
typedef char type;
bool visited[100] = { false };
typedef struct
///定义数据结构：栈
{
int *top;
int *base;
int Size;
}Stack;
typedef struct
///定义数据结构：队列
{
int *Front;
int *Rear;
int Size;
} Queue;
typedef struct
///定义数据结构：图
{
type vexs[Max];
bool arcs[Max][Max];
int vexnum,arcnum;
} graph;
void InitStack(Stack &s)
///对栈进行初始化
{
if(!(s.top=s.base=(int *)malloc(maxSize*sizeof(int))))
return ;
s.Size=maxSize;
}
void push(Stack &s,int e)
///入栈：将元素e压入栈
{
*s.top=e;
s.top++;
}
void pop(Stack &s)
///出栈：栈顶指针减一
{
if(s.base==s.top)
return ;
s.top--;
}
int top(Stack s)
///返回栈顶元素
{
s.top--;
return *s.top;
}
void InitQueue(Queue &q)
///初始化队列
{
if(!(q.Front=q.Rear=(int *)malloc(maxSize*sizeof(int))))
return ;
q.Size=maxSize;
}
void Q_push(Queue &q,int e)
///入队列：将元素e入队列
{
*q.Rear=e;
q.Rear++;
}
int Q_pop(Queue &q)
///出队列：返回队头元素，队头指针加一
{
int e;
if(q.Front==q.Rear)
return 0;
e=*q.Front;
q.Front++;
return e;
}
void Create(graph *g)
///建立邻接矩阵并输出
{
int i,j;
memset(g->arcs,0,sizeof(g->arcs));
for(i=0; i<g->arcnum; ++i)
{
int x,y;
cin>>x>>y;
g->arcs[x][y]=1;
g->arcs[y][x]=1;
}
cout<<"无向邻接表矩阵为:"<<endl;
for(i=0; i<g->vexnum; i++)
{
for(j=0; j<g->vexnum; j++)
cout<<g->arcs[i][j]<<" ";
cout<<endl;
}
}
void Du(graph *g)
///统计每个顶点的度
{
int i,j;
for(i=0; i<g->vexnum; i++)
{
int amount=0;
for(j=0; j<g->vexnum; ++j)
if(g->arcs[i][j])
++amount;
cout<<"顶点"<<g->vexs[i]<<"的度为"<<amount<<endl;
}
}
void DFS(graph *g,int k)
///DFS深度优先搜索
{
int t,i;
Stack s;
InitStack(s);
cout<<g->vexs[k]<<" ";
visited[k]=true;
push(s,k);
while(s.base!=s.top)
{
t=top(s);
if(i==g->vexnum)
///如果內层循环未找到没被访问的元素，则出栈
pop(s);
for(i=0; i<g->vexnum; i++)
{
if(g->arcs[t][i]==1&&visited[i]==false)
///找出邻接矩阵第t+1行中第一个未被访问的元素
{
visited[i]=true;
///找到后标志为1，并输出，入栈
cout<<g->vexs[i]<<" ";
push(s,i);
break;
///找到之后跳出內层循环，返回外层循环起始处，重复之前操作
}
}
}
}
void BFS(graph *g, int k)
///BFS广度优先搜索
{
Queue q;
InitQueue(q);
visited[k]=true;
cout<<g->vexs[k]<<" ";
Q_push(q,k);
while(q.Front!=q.Rear)
{
int t=Q_pop(q);
for(int w=0; w<g->vexnum; w++)
{
if (g->arcs[t][w]!=0&&visited[w]==false)
///找出邻接矩阵中t+1行所有未被访问的元素
{
visited[w]=true;
///每找到一个标志为1并入队列
cout<<g->vexs[w]<<" ";
Q_push(q,w);
}
}
}
}
void Is_in_graph(graph *g,char ch)
///查询图中是否存在顶点ch
{
int i,j,k;
for(i=0; i<g->vexnum; i++)
///遍历顶点数组
if(ch==g->vexs[i])
break;
if(i==g->vexnum)
///如果循环正常结束则i=g->vexnum,此时说明不存在该顶点
{
printf("无%c",ch);
return ;
}
else
{
for(j=0; j<g->vexnum; j++)
///如果存在，则将与顶点相关的边覆盖
for(k=0; k<g->vexnum; k++)
{
if(j>=i&&k>=i)
g->arcs[j][k]=g->arcs[j+1][k+1];
if(j>=i&&k<i)
g->arcs[j][k]=g->arcs[j+1][k];
if(j<i&&k>=i)
g->arcs[j][k]=g->arcs[j][k+1];
}
}
for(j=0; j<g->vexnum; j++)
///覆盖该顶点
if(j>=i)
g->vexs[j]=g->vexs[j+1];
g->vexnum--;
cout<<"删除该顶点后剩余顶点为：n";
for(j=0; j<g->vexnum; j++)
cout<<g->vexs[j]<<" ";
cout<<endl;
cout<<"删除后邻接矩阵为：n";
for(j=0; j<g->vexnum; j++)
{
for(k=0; k<g->vexnum; k++)
cout<<g->arcs[j][k]<<" ";
cout<<endl;
}
cout<<"从第一个顶点开始的DFS遍历为：n";
DFS(g,0);
}
void Is_connect(graph *g,int k)
///利用DFS搜索的思想遍历图，每遍历一个顶点计数加一
{
visited[k]=true;
Count++;
for(int i=0; i<g->vexnum; i++)
if(g->arcs[k][i]==1&&visited[i]==false)
{
Is_connect(g,i);
}
}
void main_menu()
///主菜单
{
cout<<"-----------------------------------n";
cout<<"---------程序主菜单----------------n";
cout<<"-----------------------------------n";
cout<<"---------1图的创立及邻接矩阵-------n";
cout<<"---------2查询图中各顶点的度-------n";
cout<<"---------3DFS遍历图----------------n";
cout<<"---------4BFS遍历图----------------n";
cout<<"---------5查询顶点是否在图中-------n";
cout<<"---------6判断是否为连通图---------n";
cout<<"---------7退出---------------------n";
cout<<"---------回车键返回菜单------------n";
cout<<"-----------------------------------n";
cout<<"---------请选择:(1-7)--------------n";
}
int main()
{
int i,num;
char ch;
graph g;
while(1)
{
system("cls");
main_menu();
scanf("%d",&num);
system("cls");
switch(num)
///通过输入1-7调用不同的功能
{
case 1:
printf("1图的创立及邻接矩阵nn");
printf("请输入顶点的个数：");
cin>>g.vexnum;
cout<<endl;
printf("请输入边的条数：");
cin>>g.arcnum;
printf("请输入各顶点：");
for(i=0; i<g.vexnum; ++i)
cin>>g.vexs[i];
cout<<endl;
printf("请输入各条边i-j:n");
Create(&g);
printf("输入任意键返回主菜单：");
system("pause");
break;
case 2:
printf("2查询图中各顶点的度nn");
Du(&g);
printf("输入任意键返回主菜单：");
system("pause");
break;
case 3:
printf("3DFS遍历图nn");
printf("请输入开始的顶点：");
cin>>ch;
cout<<endl;
for(i=0;i<g.vexnum;i++)
if(ch==g.vexs[i])
break;
if(i>=g.vexnum)
{
printf("输入数字有误！");
printf("输入任意键返回主菜单：");
system("pause");
break;
}
printf("从该点开始DFS搜索为：");
DFS(&g,i);
cout<<endl;
memset(visited,0,sizeof(visited));
///将访问标志数组初始化为0
printf("输入任意键返回主菜单：");
system("pause");
break;
case 4:
printf("4BFS遍历图nn");
printf("请输入开始的顶点：");
cin>>ch;
cout<<endl;
for(i=0;i<g.vexnum;i++)
if(ch==g.vexs[i])
break;
if(i>=g.vexnum)
{
printf("输入数字有误！");
printf("输入任意键返回主菜单：");
system("pause");
break;
}
printf("从该点开始BFS搜索为：");
BFS(&g,i);
cout<<endl;
memset(visited,0,sizeof(visited));
///将访问标志数组初始化为0
printf("输入任意键返回主菜单：");
system("pause");
break;
case 5:
printf("5查询顶点是否在图中nn");
printf("请输入要查询的顶点：");
cin>>ch;
cout<<endl;
Is_in_graph(&g,ch);
cout<<endl;
memset(visited,0,sizeof(visited));
///将访问标志数组初始化为0
printf("输入任意键返回主菜单：");
system("pause");
break;
case 6:
printf("6判断是否为连通图nn");
Is_connect(&g,0);
if(Count==g.vexnum)
printf("YES!");
else
printf("NO!");
cout<<endl;
Count=0;
memset(visited,0,sizeof(visited));
///将访问标志数组初始化为0
printf("输入任意键返回主菜单：");
system("pause");
break;
case 7:
printf("退出成功");
return 0;
}
}
}

最后

以上就是甜蜜台灯最近收集整理的关于图的基本操作和实现的全部内容，更多相关图内容请搜索靠谱客的其他文章。