数据结构练习题——图(算法设计题)

​
（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：

① 增加一个新顶点v，InsertVex(G, v)；

② 删除顶点v及其相关的边，DeleteVex(G, v);

③ 增加一条边，InsertArc(G, v, w);

④ 删除一条边，DeleteArc(G, v, w)。

[算法描述]

假设图G为有向无权图，以邻接矩阵作为存储结构四个算法分别如下：
① 增加一个新顶点v

Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v
{
	if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE;
	G.vexs[++G.vexnum]=v;
	return OK;
}//Insert_Vex
1
2
3
4
5
6

② 删除顶点v及其相关的边，

Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v
{
	n=G.vexnum;
	if((m=LocateVex(G,v))<0) return ERROR;
	G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点
	for(i=0;i<n;i++)
	{
		G.arcs[m]=G.arcs[n];
		G.arcs[m]=G.arcs[n]; //将边的关系随之交换
	}
	G.arcs[m][m].adj=0;
	G.vexnum--;
	return OK;
}//Delete_Vex
1
2
3
4
5
6
7
8
9
10
11
12
13
14

分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加。

③ 增加一条边

Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w)
{
	if((i=LocateVex(G,v))<0) return ERROR;
	if((j=LocateVex(G,w))<0) return ERROR;
	if(i==j) return ERROR;
	if(!G.arcs[j].adj)
	{
		G.arcs[j].adj=1;
		G.arcnum++;
	}
	return OK;
}//Insert_Arc
1
2
3
4
5
6
7
8
9
10
11
12

④ 删除一条边

Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w)
{
	if((i=LocateVex(G,v))<0) return ERROR;
	if((j=LocateVex(G,w))<0) return ERROR;
	if(G.arcs[j].adj)
	{
		G.arcs[j].adj=0;
		G.arcnum--;
	}
	return OK;

}//Delete_Arc
1
2
3
4
5
6
7
8
9
10
11
12

以邻接表作为存储结构，本题只给出Insert_Arc算法.其余算法类似。

Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w)
{
	if((i=LocateVex(G,v))<0) return ERROR;
	if((j=LocateVex(G,w))<0) return ERROR;
	p=new ArcNode;
	p->adjvex=j;p->nextarc=NULL;
	if(!G.vertices.firstarc) G.vertices.firstarc=p;
	else
	{
		for(q=G.vertices.firstarc;q->q->nextarc;q=q->nextarc)
		if(q->adjvex==j) return ERROR; //边已经存在
		q->nextarc=p;
	}
	G.arcnum++;
	return OK;
}//Insert_Arc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（2）一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。

[算法描述]

Void DFSn(Graph G,int v)
{  //从第v个顶点出发非递归实现深度优先遍历图G
	Stack s;
	SetEmpty(s);
	Push(s,v);
	While(!StackEmpty(s))
	{       //栈空时第v个顶点所在的连通分量已遍历完
		Pop(s,k);
		If(!visited[k])
		{        
			visited[k]=TRUE;
			VisitFunc(k);          //访问第k个顶点
			//将第k个顶点的所有邻接点进栈
			for(w=FirstAdjVex(G,k);w;w=NextAdjVex(G,k,w))
			{       
				if(!visited[w]&&w!=GetTop(s)) Push(s,w);    //图中有环时w==GetTop(s)
			}
	    }
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（3）设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。

[题目分析]

利用Dijkstra算法求v0到其它所有顶点的最短路径，分别保存在数组D[i]中，然后求出D[i]中值最大的数组下标m即可。

[算法描述]

int ShortestPath_MAX(AMGraph G, int v0){
    //用Dijkstra算法求距离顶点v0的最短路径长度最大的一个顶点m
    n=G.vexnum;                                   //n为G中顶点的个数
    for(v = 0; v<n; ++v){                     //n个顶点依次初始化
       S[v] = false;                                 //S初始为空集
       D[v] = G.arcs[v0][v];                 //将v0到各个终点的最短路径长度初始化
       if(D[v]< MaxInt)  Path [v]=v0;          //如果v0和v之间有弧，则将v的前驱置为v0
       else Path [v]=-1;                      //如果v0和v之间无弧，则将v的前驱置为-1
      }//for
      S[v0]=true;                                   //将v0加入S
      D[v0]=0;                                    //源点到源点的距离为0
      /*开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集*/
      for(i=1;i<n; ++i){                    //对其余n−1个顶点，依次进行计算
        min= MaxInt;
        for(w=0;w<n; ++w)
          if(!S[w]&&D[w]<min)  
              {v=w; min=D[w];}                 //选择一条当前的最短路径，终点为v
        S[v]=true;                                  //将v加入S
        for(w=0;w<n; ++w)                       //更新从v0到V−S上所有顶点的最短路径长度
        if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){
             D[w]=D[v]+G.arcs[v][w];     //更新D[w]
             Path [w]=v;                          //更改w的前驱为v
        }//if
    }//for
/*最短路径求解完毕，设距离顶点v0的最短路径长度最大的一个顶点为m */       
	Max=D[0];
	m=0;
	for(i=1;i<n;i++)
	if(Max<D[i]) m=i;           
	return m;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

（4）试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。

[题目分析]

引入一变量level来控制递归进行的层数

[算法描述]

int visited[MAXSIZE]; //指示顶点是否在当前路径上
int level＝1;//递归进行的层数
int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
  if(i==j) return 1; //i就是j
  else
  {
    visited[i]=1;
    for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--)
    { level++;
      k=p->adjvex;
      if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径
}//for
  }//else
if (level==1)  return 0;
}//exist_path_DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（5）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。

[算法描述]

int visited[MAXSIZE];
int exist_path_len(ALGraph G,int i,int j,int k)
//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径
{if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求
 else if(k>0)
  {visited[i]=1;
   for(p=G.vertices[i].firstarc;p;p=p->nextarc)
    {l=p->adjvex;
     if(!visited[l])
        if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一
    }//for
   visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中
  }//else
 return 0; //没找到
}//exist_path_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15