1. 判断一个无向图G是否为一棵树。若是一棵树，则算法返回true，否则返回false。

• 算法思想：一个无向图G是一棵树的条件是，G必须是无回路的连通图或有n-1条边的连通图，这里采用后者作为判断条件。对连通的判定，可用能否遍历全部顶点来实现。可以采用深度优先搜索算在遍历图的过程中统计可能访问到的顶点个数和边的条数，若一次遍历就能访问到n个顶点和n-1条边，则可断定此图是一棵树。

int FirstNeighbor(MGraph g, int x) //求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
{
	if (x >= g.vexnum) return -1; //图中不存在值为x的顶点
	int y=0;
	while (y < g.vexnum)
	{
		if (g.Edge[x][y] == 1) return y; //返回顶点号
		else y++;
	}
	if (y >= g.vexnum) return -1; //x没有邻接点
}

int NextNeighbor(MGraph g, int x, int y)
{
	if (x >= g.vexnum || y >= g.vexnum) return -1; //不存在顶点x或顶点y
	y = y + 1; //从[x][y+1]开始遍历
	while (y < g.vexnum)
	{
		if (g.Edge[x][y] == 1) return y; //返回顶点号
		else y++;
	}
	if (y >= g.vexnum) return -1; //x没有邻接点
}

bool visited[MaxVertenNum]; //访问标记数组
void DFS(MGraph& g, int v, int& Vnum, int& Enum, bool visited[])
//深度优先遍历图G，统计访问过的顶点数和边数，通过Vnum和Enum返回
{
	visited[v] = true; //作访问标记
	Vnum++; //顶点计数
	for (int w = FirstNeighbor(g, v); w >= 0; w = NextNeighbor(g, v, w))
	//取v的第一个邻接顶点
	{
		Enum++; //边存在，边计数
		if (!visited[w]) DFS(g, w, Vnum, Enum, visited); //当该邻接顶点为访问过
	}
}

bool isTree(MGraph g)
{
	for (int i = 0; i < g.vexnum; i++) visited[i] = false; //访问标记数组初始化
	int Vnum = 0, Enum = 0; //记录顶点数和边数
	DFS(g, 0, Vnum, Enum, visited);
	if (Vnum == g.vexnum && Vnum == Enum/2 + 1) return true; //符合树的条件
	else return false; //不符合树的条件
}

运行结果

2. 写出图的深度优先搜索DFS算法的非递归算法(图采用邻接表形式)。

• 算法思想：在深度优先搜索的非递归算法中使用了一个栈S来记忆下一步可能访问的顶点，同时使用了个访问标记数组visited[i]来记忆第i个顶点是否在栈内或曾经在栈内，若是则它以后不能再进栈。

bool visited[MaxVertexNum]; //访问标记数组
void DFS_Non_Rc(AdjGraph g, int v)
{
	SqStack st;
	InitStack(st); //初始化栈
	
	Push(st, v); //v入栈
	visited[v] = true;
	while (!StackEmpty(st))
	{
		Pop(st, v); //栈中退出一个顶点
		printf("%c ", g.adjlist[v].data); //先访问，再将其子结点入栈
		for (int w = FirstNeighbor(g, v); w >= 0; w = NextNeighbor(g, v, w)) //v的所有邻接点
		{
			if (!visited[w]) //未进过栈的顶点进栈
			{
				visited[w] = true; //做标记，以免再次入栈
				Push(st, w);
			}
		}
	}
}

void DFSTraverse(AdjGraph g)
{
	int i;
	for (i = 0; i < g.vexnum; i++) visited[i] = false; //初始化标记数组
	for (i = 0; i < g.vexnum; i++)
		if (!visited[i]) DFS_Non_Rc(g, i); //对每个连通分量调用一次DFS_Non_Rc
}

运行结果

• ！注意： 由于使用了栈，使得遍历的方式从右端到左端进行，不同于常规的从左端到右端，但仍然是深度优先遍历。

3. 分别采用基于深度优先遍历和广度优先遍历算法判别以邻接表方式存储的有向图中是否存在由顶点i到顶点j的路径(i≠j)。

基于深度优先遍历

int visited[MaxVertexNum] = { 0 }; //访问标记数组
void DFS(AdjGraph g, int v, int u, bool &can_reach)
//深度优先判断有向图G中顶点vi到顶点vj是否有路径，是则返回1，否则返回0
{
	visited[v] = 1; //置访问标记
	for (int w = FirstNeighbor(g, v); w >= 0; w = NextNeighbor(g, v, w))
		//递归检测邻接点
	{
		if (w == u) can_reach = true;
		if (!visited[w]) DFS(g, w, u, can_reach);
	}
}

运行结果

基于广度优先遍历

bool visited[MaxVertenNum]; //访问标记数组
bool BFS(MGraph g, int v, int u)
//广度优先判断有向图G中顶点vi到顶点vj是否有路径，是则返回1，否则返回0
{
	int i;
	for (i = 0; i < g.vexnum; i++) visited[i] = false;
	SqQueue* qu;
	InitQueue(qu); //初始化队列
	enQueue(qu, v); //顶点i入队
	visited[v] = true; //置访问标记
	while (!EmptyQueue(qu)) //非空循环
	{
		deQueue(qu, v); //队头顶点出队
		for (int w = FirstNeighbor(g, v); w >= 0; w = NextNeighbor(g, v, w))
			//检测所有邻接点
		{
			if (w == u) return true; //如果w==u，则查找成功
			if (!visited[w]) //否则，顶点w入队
			{
				visited[w] = true;
				enQueue(qu, w);
			}
		}
	}
	return false;
}

运行结果

4. 假设图用邻接表表示，设计一个算法，输出从顶点$V_i$到顶点$V_j$的所有简单路径。

int visited[MaxVertexNum] = { 0 }; //访问标记数组
void FindPath(AdjGraph g, int u, int v, int path[], int d)
{
	int w, i;
	ArcNode* p;
	d++; //路径长度增1
	path[d] = u; //将当前顶点添加到路径中
	visited[u] = 1; //置已访问标记
	if (u == v) //找到一条路径则输出
	{
		for (i = 0; i <= d; i++) printf("%c ", g.adjlist[path[i]].data); //输出路径上的结点
		printf("\n");
	}
	p = g.adjlist[u].firstarc; //p指向u的第一个相邻点
	while (p != NULL)
	{
		w = p->adjvex; //若顶点w未访问，递归访问它
		if (!visited[w]) FindPath(g, w, v, path, d);
		p = p->nextarc; //p指向u的下一个相邻点
	}
	visited[u] = 0; //恢复环境，使该顶点可重新使用
}

运行结果

5. 假设一个连通图采用邻接表作为存储结构，试设计一个算法，判断其中是否存在经过顶点v的回路。

• 算法思想：从顶点出发进行深度优先遍历，用d记录走过的路径长度，对每个访问的顶点设置标记为1。若当前访问顶点u，表示v->u存在一条路径，如果顶点的u邻接点w等于v并且d>1，表示顶点u到v有一条边，即构成经过顶点v的回路。Cycle算法中has是布尔值，初始调用时置为false，执行后若为true表示存在经过顶点v的回路，否则表示没有相应的回路。

bool visited[MaxVertexNum]; //访问标记数组
void Cycle(AdjGraph g, int u, int v, int d, bool& has)
{
	ArcNode* p;
	int w;
	visited[u] = true; //置已访问标记
	d++;
	p = g.adjlist[u].firstarc; //p指向顶点u的第一个邻接点
	while (p != NULL)
	{
		w = p->adjvex;
		if (!visited[w]) Cycle(g, w, v, d, has); //若顶点w未访问，递归访问它
		else if (w == v && d > 1) //u到v之间存在一条边且回路长度大于1
		{
			has = true;
			return;
		}
		p = p->nextarc; //找下一个邻接点
	}
}

bool hasCycle(AdjGraph g, int v) //判断连通图G中是否有经过顶点v的回路
{
	bool has = false;
	Cycle(g, v, v, -1, has); //从顶点v开始搜索
	return has;
}

运行结果

6. 设图G采用邻接矩阵存储，设计一个算法采用深度优先遍历方法求有向图的根。若有向图中存在一个顶点v，从v可以通过路径到达图中的其他所有顶点，则称v为该有向图的根。

• 算法思想：由于从有向图的根出发可以到达图中的其他所有顶点，因此可以通过深度优先遍方法来判断一个顶点是否为有向图的根。当采用深度优先遍历方法从顶点出发能够访所有顶点时表示为图的根，若找到这样的顶点i，返回i，否则返回-1。

bool visited[MaxVertenNum]; //访问标记数组
void MDFS(MGraph g,int v) //基于邻接矩阵的深度优先遍历算法
{
	visited[v] = 1; //置访问标记
	for (int w; w < g.vexnum; w++) //找顶点v的所有邻接点
		if (g.Edge[v][w] != 0 && g.Edge[v][w] != INF && visited[w] == 0)
			MDFS(g, w); //找顶点v的未访问过的邻接点w
}

int DGRoot(MGraph g) //基于深度优先遍历求图的根
{
	for (int i = 0; i < g.vexnum; i++)
	{
		for (int j = 0; j < g.vexnum; j++)
			visited[j] = 0;
		MDFS(g, i);
		int n = 0; //累计从顶点i出发访问到的顶点个数
		for (int k = 0; k < g.vexnum; k++)
			if (visited[k] == 1) n++;
		if (n == g.vexnum) return i; //若访问所有顶点，则顶点i为根
	}
	return -1; //图没有根
}

运行结果

7. 对于一个带权连通图，可以采用Prim算法构造出从某个顶点出发的最小生成树。问该最小生成树是否一定包含从顶点到其他所有顶点的最短路径。如果回答是，请予以证明；如果回答不是，请给出反例。

• 答:不一定。从顶点0到顶点2的最短路径为0→2，不是最小生成树中的0→1→2。
  

8. Dijkstra算法用于求单源最短路径，为了求ー个图中所有顶点对之间的最短路径可以以每个顶点作为源点调用Dijkstra算法，Floyd算法和这种算法相比有什么优势?

• 答：对于有n个顶点的图，求所有顶点对之间的最短路径，若调用Dijkstra算法n次，其时间复杂度为$O(n^3)$。Floyd算法的时间复杂度也是$O(n^3)$。但Floyd算法更快，这是因为前者每次调用Dijkstra算法时都是独立执行的，路径比较中得到的信息没有共享，而Floyd算法中每考虑一个顶点时所得到的路径比较信息保存在A数组中，会用于下次的路经比较，从而提高了整体查找最短路径的效率。