Question

用邻接矩阵存储无向图，并用深度优先和广度优先遍历搜索输出序列，要能运行的，并把运行的结果截图下来

Answer 1

#include<iostream.h>
#include<stdlib.h>
#include<malloc.h>

#define maxsize 50

struct arcnode //定义边结点 链表结点
{
int adjvex; //弧头顶点的位置
struct arcnode *nextarc; //指向相同弧尾的下一条弧的指针
};

struct vnode //定义顶点结点
{
int data; //顶点数据
struct arcnode *firstarc; //指向第一条已该点为弧尾的弧
};

int m,n,v;

void creatgraph (struct vnode a[maxsize]);
void dfstraverse(struct vnode a[maxsize]);
void bfstraverse(struct vnode a[maxsize]);

void main()
{
struct vnode adjlist[maxsize];
int cord;
do
{
cout<<"——主菜单——"<<endl;
cout<<"1.建立无向图的邻接表"<<endl;
cout<<"2.深度遍历图"<<endl;
cout<<"3.广度遍历图"<<endl;
cout<<"4.结束程序运行"<<endl;
cout<<"————————————"<<endl;
cout<<"请输入你的选择(1, 2, 3, 4:)"<<endl;

cin>>cord;
switch(cord)
{
case 1:creatgraph(adjlist);
break;
case 2:dfstraverse(adjlist);
break;
case 3:bfstraverse(adjlist);
break;
case 4:exit(0);
}
}while(cord<=4);
}

void creatgraph(struct vnode a[maxsize])
{
//a[maxsize]存放顶点
int i,j,k;
struct arcnode *p;
cout<<"请输入边数和顶点数:"<<endl;
cin>>m>>n;
for(k=0;k<n;k++) //初始化
{
a[k].data=k+1;
a[k].firstarc=NULL;
}

cout<<"输入两个相关联的顶点:"<<endl;
for(k=0;k<m;k++) //m代表边数
{
cin>>i>>j;
//输入为无向图
p=(struct arcnode*)malloc(sizeof(struct arcnode));
p->adjvex=j; //弧头顶点的位置
p->nextarc=a[i-1].firstarc; //把指向第一条以该点为弧尾的弧给指向相同弧尾的下一条弧的指针
a[i-1].firstarc=p;

p=(struct arcnode*)malloc(sizeof(struct arcnode));
p->adjvex=i;
p->nextarc=a[j-1].firstarc;
a[j-1].firstarc=p;
}
cout<<endl;

for(k=0;k<n;k++)
{
cout<<"顶点"<<a[k].data<<"相关联的顶点是:";
p=a[k].firstarc;
while(p)
{
cout<<p->adjvex<<" ";
p=p->nextarc;
}
cout<<endl;
}
}

void dfstraverse(struct vnode a[maxsize]) //深搜
{
struct arcnode *p,*ar[maxsize]; //ar[maxsize]作为顺序栈，存放遍历过程中边结点的地址
int x,y,i,top=-1;
int visited[maxsize]; //用做存放已遍历过顶点的标记

for(i=0;i<n;i++) //初始化，标记为0
visited[i]=0;

cout<<"输入遍历的第一个顶点"<<endl; //输入遍历的初始点
cin>>x; //输入图遍历的始顶点的编号
cout<<x;
visited[x-1]=1; //标记已访问的顶点

//下一个要遍历的顶点所关联的边结点，向量表的下标从0开始
p=a[x-1].firstarc; //指向第一条已该点为弧尾的弧

while((p) || (top>=0))
{
if(!p)
{
p=ar[top]; //ar[maxsize]作为顺序栈，存放遍历过程中边结点的地址
top--;
}
y=p->adjvex; //弧头顶点的位置
if(visited[y-1]==0) //若未遍历过，则遍历，并且下一个顶点进栈，从本顶点出发继续按深度遍历
{
visited[y-1]=1; //访问后进行标记
cout<<"->"<<y; //输出该顶点

p=p->nextarc; //指向相同弧尾的下一条弧的指针
if(p)
{
top++;
ar[top]=p; //ar[maxsize]作为顺序栈，存放遍历过程中边结点的地址
}
p=a[y-1].firstarc;
}
else
p=p->nextarc;
}
cout<<endl;
}

void bfstraverse(struct vnode a[maxsize]) //广搜
{
//数组a[max]为顺序栈列存放刚遍历过的顶点号
struct arcnode *p;
int x,y,i,front=-1,rear=-1,ar[maxsize],visited[maxsize];//数组ar[maxsize]为顺序队列存放刚遍历过的顶点号

for(i=0;i<n;i++) //初始化标记数组
visited[i]=0;

cout<<"输入遍历的第一个顶点"<<endl;
cin>>x;
cout<<x;
visited[x-1]=1;
p=a[x-1].firstarc; //指向第一条已该点为弧尾的弧

while((p) || (front!=rear))
{
if(!p)
{
front++;
y=ar[front];
p=a[y-1].firstarc; //指向第一条已该点为弧尾的弧
}
y=p->adjvex; //弧头顶点的位置

if(visited[y-1]==0) //遍历顺点并插入队列
{
visited[y-1]=1;
cout<<"->"<<y;

rear++;
ar[rear]=y;
}
p=p->nextarc; //指向相同弧尾的下一条弧的指针
}
cout<<endl;
}

Answer 2

这个应该可以
//插入排序
#ifndef LIST_H
#define LIST_H
#include<iostream>
using namespace std;

template<class number>
class List
{
public: