图的刷题..
1.连通无向图以邻接表作为存储结构，设计一个算法，利用图的遍历算法求出图
中结点的最大关键字值。结点类型定义如下:
typedef struct node
{int adjvex;
Struct node *next;
} edgenode; /边表中结点的类型/
Typedef struct
{int vertex; /结点的关键字是整形/
edgenode *link;
} vexnode; /结点表中结点的类型/
int max=0;
void DFS(ALgraph G,int v)
{
Arcnode *p;
int w;
if(G.vertice[i].data>max)
max=G.vertice[i].data;
for(p=G.vertice[i].firstarc;p;p=p->nextarc)
{
w=p->adjvex;
if(!visited[w])
DFS(G,w);
}
}
2.以邻接表 T 作为存储结构，设计一个算法，判断在一个有向图中是否有从顶点
v 到顶点 w 的边。
DFS(ALgraph G,int vi,int vj)
{ Arcnode *p;
int w;
if(vi==vj)
return true;
visited[vi]=TRUE;
for(p=G.vertice[i].firstarc;p;p=p->next)
{
w=p->adjvex;
if(!visited[w])
DFS(G,boolw,vj);
}
}
.
3.设计一个函数完成: 首先输入 i 和 j，然后检查边(vi，vj)是否存在? 如果存在，则
删除该边，函数返回
3.用邻接矩阵表示无向图，类型定义如下:
#define n 32 /图中顶点个数/
typedef char vextype; /顶点的类型
typedef int adjtype; /邻接矩阵中数组元素的类型/
typedef struct
{vextype vexs[n]; /顶点表域/
adjtype arcs[n][n]; /邻接矩阵域/
} graph;
void Delete_x(Graph G,int i,int j)
{
for(int i=0;i<G.vexnum;i++)
for(int j=0;j<G.vexnum;j++)
{
if(G.edge[i][j]==1||G.edge[j][i]==1)
G.edge[i][j]=G.edge[j][i]=0;
else
G.edge[i][j]=G.edge[j][i]=1;
}
}
4.设计算法，求出无向连通图中距离顶点 V 的最短路径长度为 K 的所有的
结点。 (设已经具备两个函数: FirstAdj(g，v)返回顶点 v 的第一个邻接点，
NextAdj(g，v，w)返回顶点 v 当前邻接点 w 的下个邻接点)。//有问题
int DFS(ALgraph G,int vi,int i,int k)
{ static i=0;
Arcnode *p;
int w;
i++;
if(i==k)
return vi ;
visited[vi]=TRUE;
for(w=FirstAdj(G,vi);w>=0;w=NextAdj(G,vi,w))
{
if(!visited[w])
DFS(G,w,i,k);
}
}
5.给定一个具有 n 个顶点的无向图的邻接表，设计一个算法将这个邻接表转换为邻
接矩阵，邻接矩阵转换为邻接表
//邻接表转换为矩阵
void Reverse(ALGraph G1 Graph G2)
{
for(int i=0;i<vexnum;i++)
for（int j=0;j<vexnum;j++）
G2.Edge[i][j]=0; //初始化
for(int i=0;i<vexmun;i++)
{ for(p=G1.vertice[i].firstarc;p;p=p->nextarc)
{
w=p->adjvex;
G2.Edge[i][j]=p->data;
}
}
}
//邻接矩阵转为邻接表
void Reverse(ALGraph &G1,Graph &G2)
{ Arcnode *p;
for(i=0;inum;i++)
for(j=0;jvexnum;j++)
G2.edge[i][j]=0; //初始化
for(int i=0;i<G1.vexnum;i++)
{
for(p=G1.vertice[i].firstarc;p;p=p->next)
{
w=p->adjvex;
G2.Edge[i][j]=1;
}
}
}
6.无向图采用邻接矩阵存储表示，设计算法，求顶点 v 和顶点 w 之间的最短
路径*//迪杰斯特拉
int DFS(ALgraph G,int vi,int vj)
{ Arcnode *p;
int w;
static int i=0;
i++;
if(vi==vj)
{
printf(“%d”,i);
}
for(p=G.vertice[vi].firstarc;p;p=p->nextarc)
{
w=p->adjvex;
if(!visited[w])
DFS(G,w,vj);
}
}
7.有向图采用邻接表存储表示，设计算法，输出各顶点的所有出边及其出度
void Display(ALgraph G)
{ int n=0;
Arcnode *p;
int w;
for(int i=0;i<G.vexnum;i++)
{ n=0;
printf(“%d的出边和出度”,i)
for(p=G.vextice[i].firstarc;p;p=p->next)
{
w=p->adjvex;
printf(“%d “,w);
n++;
}
printf(” %d”,n);
}
}