试在无向图的邻接矩阵和邻接链表上实现如下算法
()往图中插入一个顶点
()往图中插入一条边
()删去图中某顶点
()删去图中某条边
下面的伪代码是一个广度优先搜索算法试以图(下图)中的v为源点执行该算法请回答下述问题
()对图中顶点vn+它需入队多少次？它被重复访问多少次?
()若要避免重复访问同一个顶点的错误应如何修改此算法?
void BFS(ALGraph *Gint k)
{//以下省略局部变量的说明visited各分量初值为假
InitQueue(&Q);//置空队列
EnQueue(&Qk);//k入队
while(!QueueEmpty(&Q)){
i=DeQueue(&Q);//vi出队
visited[i]=TRUE;//置访问标记
printf(%cG>adjlist[i]vertex;//访问vi
for(p=G>adjlist[i]firstedge;p;p=p>next)
//依次搜索vi的邻接点vj(不妨设p>adjvex=j)
if(!visited[p>adjvex])//若vj没有访问过
EnQueue(&Qp>adjvex);//vj入队
}//endofwhile
}//BFS
试以邻接表和邻接矩阵为存储结构分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(i<>j)之间是否有路径
试分别写出求DFS和BFS生成树(或生成森林)的算法要求打印出所有的树边
写一算法求连通分量的个数并输出各连通分量的顶点集
设图中各边的权值都相等试以邻接矩阵和邻接表为存储结构分别写出算法
()求顶点vi到顶点vj(i<>j)的最短路径
()求源点vi到其余各顶点的最短路径
要求输出路径上的所有顶点(提示利用BFS遍历的思想)
以邻接表为存储结构写一个基于DFS遍历策略的算法求图中通过某顶点vk的简单回路(若存在)
写一算法求有向图的所有根(若存在)分析算法的时间复杂度
改写节的算法Print使输出的从源点到各终点的最短路径是正向的(提示使用栈暂存路径)
对节的NonSuccFirstTopSort算法求精分别以邻接矩阵和邻接表作为存储结构写出其具体算法并分析算法的时间
设一个有向图DAG试以邻接矩阵和邻接表作为存储结构写出对节的DFSTopSort求精算法为什么有向图不是DAG时该算法不能正常工作?
利用拓扑排序算法的思想写一算法判别有向图中是否存在有向环当有向环存在时输出构成环的顶点
