C++数据结构 上机实验 图的建立与遍历 公交线路咨询

Question

1、图的建立与遍历
输入图的顶点和边的信息建立图，并对其进行深度和广度遍历，输出遍历结果。
图以邻接表为存储结构。对建立的图采用邻接矩阵的形式输出。以用户指定的结点为起点，分别输出深度和广度遍历下的结点访问序列和相应生成树的边集。
图中每个顶点用一个编号表示（如果一个图有n个结点，则它们的编号分别为0、1、…、n-1）。每条边对应一对顶点的编号，可以对边的输入顺序作出某种限制，使建立的邻接表中边结点按顶点编号大小排列，以方便邻接矩阵的输出。

2、公交线路咨询
有一区域的公交线路网，已知区域中各场所之间的公交线路和各线路的花费时间，试设计一个交通指南系统，指导前来咨询者以最少的时间从区域中的某一场所到达另一场所。
区域中的每个场所用一个字母表示，输入出发地和目的地顶点的字母，输出行走的路线（经过的场所）和最少的时间。
注意出发地到目的地顶点之间不存在路径的情况。
公交线路网可以用一个带权有向图表示。图中每个顶点代表一个场所，弧代表已有的公交线路，弧上的权表示搭乘该线路所需的时间。然后再利用Dijkstra算法求解该问题。
我要代码，不要和我讲看什么书

Answer 1

#include<stdio.h>
#include<malloc.h>
#define FALSE 0
#define TRUE 1
#define max 10
typedef char vextype;
typedef int adjtype;
typedef struct
{
vextype vexs[max];
adjtype arcs[max][max];
}graph;
graph g;
int n,e;
int visited[max];
int Q[max];
//建立无向图的邻接矩阵;
void creategraph(graph *ga)
{ int i,j,k;
printf("输入顶点数和边数:");
scanf("%d%d",&n,&e);
printf("输入顶点信息:"); getchar();
for(i=0;i<n;i++) ga->vexs[i]=getchar();
getchar();
for(i=0;i<n;i++)
for(j=0;j<n;j++)
ga->arcs[i][j]=0;
printf("输入边的两个顶点\n");
for(k=0;k<e;k++)
{ scanf("%d%d",&i,&j);
ga->arcs[i][j]=ga->arcs[j][i]=1;
}
}
//深度优先搜索;
void DFS(int i)
{
int j;
printf("node:%c\n",g.vexs[i]);
visited[i]=1;
for(j=0;j<n;j++)
if((g.arcs[i][j]==1)&&(!visited[j]))
DFS(j);
}
//广度优先搜索;
void BFS(int m)
{
int i,j;
int rear=-1,front=-1;
printf("node:%c\n",g.vexs[m]);
visited[m]=1;
rear++;
Q[rear]=m;
while(front!=rear)
{
front++;
i=Q[front];
for(j=0;j<n;j++)
if((g.arcs[i][j]==1)&&(!visited[j]))
{
printf("node:%c\n",g.vexs[j]);
visited[j]=1;
rear++;
Q[rear]=j;
}
}
}
//主函数;
int main()
{ int i,j,k,m;
creategraph(&g);
printf("顶点信息: ");
for(i=0;i<n;i++)
printf("%c",g.vexs[i]);
printf("\n");
printf("图的邻接矩阵是:\n");
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
printf(" %d",g.arcs[i][j]);
printf("\n");
}
for(i=0;i<n;i++)
visited[i]=0;
printf("请输入深度优先搜索的开始结点序号:\n");
scanf("%d",&k);
printf("深度优先搜索的结果是:\n");
DFS(k);
for(i=0;i<n;i++)
visited[i]=0;
printf("请输入广度优先搜索的开始结点序号:\n");
scanf("%d",&m);
printf("广度优先搜索的结果是:\n");
BFS(m);
system("pause");
}

#include<iostream.h>
#include<stdlib.h>
#define defaultvertices 30
typedef char T;
typedef int E;
const E maxweight=999;
class graphmtx
{
public:
graphmtx(int sz=defaultvertices);
// ~graphmtx(){delete []verticeslist;delete []edge;}
bool isempty()//图空
{
if(numedges==0)return true;
else return false;
}
bool isfull()//图满
{
if(numvertices==maxvertices||numedges==maxvertices*(maxvertices-1)/2)return true;
else return false;
}
int numofvertices(){return numvertices;}//顶点数
int numofedges(){return numedges;}//边数
T getvalue(int i){return i>=0&&i<=numvertices?verticeslist[i]:NULL;}//取顶点值
E getweight(int v1,int v2){return v1!=-1&&v2!=-1?edge[v1][v2]:0;}
int getfirstneighbor(int v);
int getnextneighbor(int v,int w);
bool insertvertex(const T&vertex);
bool insertedge(int v1,int v2,E cost);
bool removevertex(int v);
bool removeedge(int v1,int v2);
int getvertexpos(T vertex)//取顶点在图中的位置
{
int i;
for(i=0;i<numvertices;i++)
{
// cout<<vertex;
// cout<<verticeslist[i];
if(verticeslist[i]==vertex)
{
return i;
}
}
return -1;
}
int maxvertices;
int numedges;
int numvertices;
private:
T *verticeslist;
E **edge;
};
//构造
graphmtx::graphmtx(int sz)
{
maxvertices=sz;
numvertices=0;
numedges=0;
int i,j;
verticeslist=new T[maxvertices];
edge=(E**)new E*[maxvertices];
for(i=0;i<maxvertices;i++)
edge[i]=new E[maxvertices];
for(i=0;i<maxvertices;i++)
for(j=0;j<maxvertices;j++)
edge[i][j]=(i==j)?0:maxweight;
}
//插入顶点
bool graphmtx::insertvertex(const T &vertex)
{
if(numvertices==maxvertices) return false;
verticeslist[numvertices++]=vertex;
return true;
}
//删除顶点
bool graphmtx::removevertex(int v)
{
if(v<0||v>numvertices) return false;
if(numvertices==1) return false;
int i,j;
verticeslist[v]=verticeslist[numvertices-1];
for(i=0;i<numvertices;i++)
{ if(edge[i][v]>0&&edge[i][v]<maxweight) numedges--;}
for(i=0;i<numvertices;i++)
edge[i][v]=edge[i][numvertices-1];
numvertices--;
for(j=0;j<numvertices;j++)
edge[v][i]=edge[numvertices][i];
for(i=0;i<numvertices;i++)
edge[i][numvertices]=edge[numvertices][i]=maxweight;
return true;
}
//插入边
bool graphmtx::insertedge(int v1,int v2,E cost)
{
if(v1>-1&&v1<numvertices&&v2>-1&&v2<numvertices&&edge[v1][v2]==maxweight)
{
edge[v1][v2]=edge[v2][v1]=cost;
numedges++;
return true;
}
else return false;
}
//删除边
bool graphmtx::removeedge(int v1,int v2)
{
if(v1>-1&&v1<numvertices&&v2>-1&&v2<numvertices&&edge[v1][v2]>0&&edge[v2][v1]<maxweight)
{
edge[v1][v2]=edge[v1][v2]=maxweight;
numedges--;
return true;
}
else return false;
}
//取第一个邻接点
int graphmtx::getfirstneighbor(int v)
{
if(v!=1)
{
for(int col=0;col<numvertices;col++)
{if(edge[v][col]>0&&edge[v][col]<maxweight) return col;}
}
return -1;
}
//取第二个邻接点
int graphmtx::getnextneighbor(int v,int w)
{
if(v!=-1&&w!=-1)
{
for(int col=w+1;col<numvertices;col++)
{ if(edge[v][col]>0&&edge[v][col]<maxweight) return col;}
}
return -1;
}
istream& operator>>(istream& in,graphmtx& g)
{
int i,j,k,n,m;
T e1,e2;
E weight;
cout<<"请输入区域内场所数以及路线数"<<endl;
cin>>n>>m;
cout<<"请输入场所（以一个字母表示）"<<endl;
for(i=0;i<n;i++)
{

cin>>e1;
g.insertvertex(e1);
}
i=0;
cout<<"请输入有公交线路的两地及时间"<<endl;
while(i<m)
{
in>>e1>>e2>>weight;
j=g.getvertexpos(e1); k=g.getvertexpos(e2);
if(j==-1||k==-1)
cout<<"error"<<endl;
else{ g.insertedge(j,k,weight); i++;}
}
return in;
}
//求最短路径长度
void shortespath(graphmtx& g,int& v,int &vv,E dist[],int path[])//dist[]最短距离 path[]最短路径中前一顶点
{
int n=g.numofvertices();
bool * s=new bool[n];//true表示顶点的最短路径已确定
int i,j,k,m=vv;
E w,min;//min未确定的点中 路径最短的顶点的距离
for(i=0;i<n;i++)
{
dist[i]=g.getweight(v,i);
s[i]=false;
if(i!=v&&dist[i]<maxweight)path[i]=v;
else path[i]=-1;
}
s[v]=true;
dist[v]=0;
int u;//确定最短路径的顶点
for(i=0;i<n-1;i++)
{
min=maxweight;
u=v;
for(j=0;j<n;j++)
{
if(s[j]==false&&dist[j]<min)
{
u=j;
min=dist[j];
}
s[u]=true;
for(k=0;k<n;k++)
{
w=g.getweight(u,k);
if(s[k]==false&&w<maxweight&&dist[u]+w<dist[k])
{
dist[k]=dist[u]+w;
path[k]=u;
}
}
}
}
for(m=vv;m!=v;m=path[m])
{
cout<<g.getvalue(m)<<"→";
}
cout<<g.getvalue(m)<<endl;
}
int main()
{
graphmtx graph(10);
int k,n,v,vv;
T v0,v00;
E *dist;
int *path;
cout<<"请建立公交线路网"<<endl;
cin>>graph;
cout<<"求两地最短路径"<<endl<<"继续请输入1,退出请输入0"<<endl;
while(1)
{
cin>>k;
switch(k)
{
case 1:
cout<<"请输入起点"<<endl;
cin>>v00;
// cout<<v00;
vv=graph.getvertexpos(v00);
// cout<<vv;
cout<<"请输入终点"<<endl;
cin>>v0;
// cout<<v0;
v=graph.getvertexpos(v0);
// cout<<v;

cout<<"乘车方法如下"<<endl;
n=graph.numofvertices();
dist=new E[n];
path=new int[n];
shortespath(graph,v,vv,dist,path);
cout<<"最短时间为："<<dist[vv]<<endl;
cout<<"继续请输入1,退出请输入0"<<endl;
// printshortestpath(graph,v,vv,dist,path);

break;
case 0:
exit(0);
default:
break;
}
}
return 0;
}

Answer 2

#include <stdio.h>
#include<malloc.h>
#define maxnode 30
#define null 0
#define m 20
typedef struct st_arc
{
int adjvex; int weight; struct st_arc *nextarc;
}arcnode;
typedef struct
{
int vertex; struct st_arc *firstarc;
}vernode;
typedef vernode adjlist[maxnode];
int queue[maxnode];
void dfs(adjlist g,int k,int visited[]) //从顶点K出发深度优先搜索
{
arcnode *p; int w; visited[k]=1; printf("%d ",g[k].vertex); p=g[k].firstarc;
while(p!=null)
{ w=p->adjvex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}
}

void bfs(adjlist g,int k,int visited[]) //从顶点K出发广度优先搜索
{
int front=0,rear=1,w;
arcnode *p; visited[k]=1; //访问初始顶点
printf("%d ",k);
queue[rear]=k; //初始顶点入队列
while(front!=rear)
{
front=(front+1)%m;
w=queue[front]; //按访问次序依次出队列
p=g[w].firstarc;
while(p!=null)
{
if(visited[p->adjvex]==0)
{ visited[p->adjvex]=1;
printf("%d ",p->adjvex);
rear=(rear+1)%m;
queue[rear]=p->adjvex;
}
p=p->nextarc;
}
}
}
void trave_bfs(adjlist g,int n) //数组visited标志图中的顶点是否已被访问
{
int i,visited[maxnode];
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(visited[i]==0)
bfs(g,i,visited);
}
void trave_dfs(adjlist g,int n) //数组visited标志图中的顶点是否已被访问
{
int i,visited[maxnode];
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(visited[i]==0)
dfs(g,i,visited);
}
void print(adjlist g,int n)
{
arcnode *q; int i;
printf("输出的是所建立无向图的邻接表结构:\n");
for(i=1;i<=n;i++)
{
printf("\t%d\t",i);
printf("%d->",g[i].vertex);
q=g[i].firstarc;
while(q!=null)
{
printf("%d,",q->adjvex);
printf("%d->",q->weight); q=q->nextarc;
}
printf("Null");
printf("\n");
}
}
void main()
{
arcnode *p,*q;
adjlist g;
int i,j,n,k,w,e;
printf("请输入建立的无向图所包含的顶点总个数和总边数(用逗号隔开):"); scanf("%d,%d",&n,&e);
for(k=1;k<=n;k++)
{
getchar();
printf("\t输入每个顶点的信息，必须输入整数值:%d",k);
scanf("%d",&g[k].vertex);
g[k].firstarc=null; //对顺序存储部分初始化
}
for(k=1;k<=e;k++)
{
printf("输入所有边的信息,（起始顶点,终止顶点和该边的权值%d 如1,2,3）:",k);
scanf("%d,%d,%d",&i,&j,&w);
q=(arcnode *)malloc(sizeof(arcnode));
q->adjvex=j;
q->weight=w;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode *)malloc(sizeof(arcnode));
p->adjvex=i;
p->weight=w;
p->nextarc=g[j].firstarc;
g[j].firstarc=p;
}
print(g,n);
printf("\n");
printf("输出深度优先搜索遍历:");
trave_dfs(g,n);
printf("\n");
printf("输出广度优先搜索遍历:");
trave_bfs(g,n);
printf("\n");
}

Answer 3

这应该是计算机三级考试题目吧，很熟悉，忘得差不多了，以前还做过类似的。去看下历年考题应该有这方面的。