1、分析并回答下列问题:

①图中顶点的度之和与边数之和的关系?

②有向图中顶点的入度之和与出度之和的关系?

③具有n个顶点的无向图,至少应有多少条边才能确保是一个连通图?若采用邻接矩阵表示,则该矩阵的大小是多少?

④具有n个顶点的有向图,至少应有多少条弧才能确保是强连通图?为什么?

  ①顶点的度之和 = 边数之和 × 2。因为每一条边的两端即为顶点的两个度。
  ②入度之和 = 出度之和。因为每一条有向边的两端分别为某一顶点的入度和另一顶点的出度。
  ③至少要有 $\frac{(n-1)(n-2)}{2} + 1$ 条边才能保证该图是一个连通图。该图中就算有 $n-1$ 个点构成了一个完全图,仍然有至少一条边连接到第 $n$ 个点,因此一定是一个连通图。采用邻接矩阵表示,该矩阵大小为 $n×n$。
  ④至少要有 $(n-1)(n-2)+n$ 条弧才能确保是强连通图。该图中就算有 $n-1$ 个点构成了一个完全有向图,仍然有 $n$ 条边连接在第 $n$ 个点上,则就算其中 $n-1$ 条边均是以第 $n$ 个点为起点/终点,仍然存在至少一条边是以第 $n$ 个点为终点/起点,保证了每个点都具有入度和出度,且为一个连通图,则一定为一个强连通图。

2、设一有向图 $G=(V,E)$ ,其中 $V={a,b,c,e,d}, E={<a,b>,<a,d>,<b,a>,<c,b>,<c,d>,<d,e>,<e,a>,<e,b>,<e,c>}$

①请画出该有向图,并求各顶点的入度和出度。

②分别画出有向图的正邻接链表和逆邻接链表。

  ① 如图所示

   a: 入度2 出度2
   b: 入度3 出度1
   c: 入度1 出度2
   d: 入度2 出度1
   e: 入度1 出度3
  ② 如图所示


正邻接链表




逆邻接链表

3、对图1所示的带权无向图。

①写出对应的邻接矩阵表示。

②写出相应的边表表示。

③求出各顶点的度。


图1 带权无向图


  ① 如图所示

  ② 如图所示

  ③ 如下所示
   顶点1 度数3
   顶点2 度数3
   顶点3 度数4
   顶点4 度数4
   顶点5 度数3
   顶点6 度数3

4、已知有向图的逆邻接链表如图2所示。

①画出该有向图。

②写出相应的邻接矩阵表示。

③写出从顶点 $V_1$ 开始的深度优先和广度优先遍历序列。

④画出从顶点 $V_1$ 开始的深度优先和广度优先生成树。


图2 有向图的逆邻接链表


  ① 如图所示

  ② 如图所示

  ③ 从$V_1$开始的深度优先遍历序列:$V_1 V_4 V_3 V_5 V_2$
    从$V_1$开始的广度优先遍历序列:$V_1 V_4 V_2 V_3 V_5$
  ④ 如图所示


深度优先生成树             广度优先生成树     

5、一个带权连通图的最小生成树是否唯一?在什么情况下可能不唯一?

  不唯一。当各边权值均相等时,最小生成树不唯一。

6、对于图1所示的带权无向图。

①按照Prime算法给出从顶点2开始构造最小生成树的过程。

②按照Kruskal算法给出最小生成树的过程。


图1 带权无向图


  ① 如图所示


  ② 如图所示

7、已知带权有向图如图3所示,请利用Dijkstra算法从顶点$V_4$出发到其余顶点的最短路径及长度,给出相应的求解步骤。


图3 带权有向图


  如表格所示。

  $ V_1 : V_4 \rightarrow V_2 \rightarrow V_1 \qquad 30 $
  $ V_2 : V_4 \rightarrow V_2 \qquad 20 $
  $ V_3 : V_4 \rightarrow V_2 \rightarrow V_1 \rightarrow V_3 \qquad 45 $
  $ V_5 : V_4 \rightarrow V_2 \rightarrow V_5 \qquad 50 $
  $ V_6 : V_4 \rightarrow V_6 \qquad 15 $

8、已知带权有向图如图4所示,请利用Floyd算法求出每对顶点之间的最短路径及路径长度。


图4 带权有向图


  如图所示。

9、一个AOV网用邻接矩阵表示,如图5。用拓扑排序求该AOV网的一个拓扑序列,给出相应的步骤。


图5 一个AOV网的邻接矩阵


  先画出该AOV网。然后选择没有直接前驱的顶点并输出,从图中删去该点和其发出的所有有向边。不断重复这个过程,如下图所示。

  拓扑排序序列为 $ V_0 \rightarrow V_1 \rightarrow V_2 \rightarrow V_3 \rightarrow V_4 \rightarrow V_5 \rightarrow V_6 $。

10、拓扑排序的结果不是唯一的,请给出如图6所示的有向图的所有可能的拓扑序列。


图6 有向图

  设计一个递归算法,遍历所有可能的情况,代码如下(已附上代码解释)。

#include <iostream>
FILE *out = fopen("result.txt", "w"); //将结果存入到result.txt里面 
using namespace std;

int totalcount = 0; //所有的情况总数 

//findnext函数 寻找拓扑排序下一个输出的点
//count 记录当前拓扑排序已经输出了多少个点 
//result[9] 记录本次拓扑排序的输出序列
//print[10] 记录v1-v9中的点是否已经输出(使用下标1-9) 
//edge[10][2] 记录当前的边情况 edge[i][0]指向edge[i][1], (0,0)表示已经输出(该边被删除) 
void findnext(int count, bool print[10], int edge[10][2], int result[9]){
	
	//若当前拓扑排序已经得到9个点,进行本次排序输出 
	if(count == 9){
		for(int i = 0; i < 9; i++){
			fprintf(out, "%d ", result[i]);
		}
		fprintf(out, "\n");
		totalcount++; //情况次数+1 
		return;
	}
	
	int can[10] = {0};
	//使用下标1-9.记录该点是否为入度为0的点。0表示符合,1表示不符合 
	
	for(int i = 0; i < 10; i++){
		if(edge[i][1] != 0) can[edge[i][1]] = 1;
		//存在未输出的边指向该点,该点不为入度为0的点 
	}
	//遍历所有点,下标1-9 
	for(int i = 1; i < 10; i++){
		//若i是入度为0的点,且i仍未输出 
		if(can[i] == 0 && print[i] == false){
			int newedge[10][2]; //创建边情况的副本 
			bool newprint[10]; //创建输出情况的副本 
			for(int j = 0; j < 10; j++){
				//删除所有该点发出的边,即置为(0,0)
				if(edge[j][0] == i){
					newedge[j][0] = 0;
					newedge[j][1] = 0;
				}
				else{
					newedge[j][0] = edge[j][0];
					newedge[j][1] = edge[j][1];
				}
				
				
				newprint[j] = print[j]; //复制输出情况 
			}
			newprint[i] = true; //将当前输出的点记录为已输出,即删除该点 
			
			result[count] = i; //记录当前输出点 
			
			findnext(count+1, newprint, newedge, result);
			//count+1,采用处理后的副本表示当前数据,进行递归调用 
		}
	}
	return;
}

int main(){
	int edge[10][2] = {1, 2, 2, 4, 4, 3, 3, 5, 4, 7, 7, 6, 6, 5, 9, 7, 9, 8, 8, 6};
	//输入初始的边情况
	
	bool print[10] = {false, false, false, false, false, false, false, false, false, false};
	//输入初始的点输出情况(均为未输出)使用下标1-9
	
	int result[9]; //用于记录拓扑排序结果 
	
	findnext(0, print, edge, result);
	
	fprintf(out, "%d", totalcount); //输出总情况次数
	return 0;
	
} 

  运行程序得到结果如下:(共52种情况)
    $ V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_3 \rightarrow V_9 \rightarrow V_7 \rightarrow V_8 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_3 \rightarrow V_9 \rightarrow V_8 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_9 \rightarrow V_3 \rightarrow V_7 \rightarrow V_8 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_9 \rightarrow V_3 \rightarrow V_8 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_9 \rightarrow V_7 \rightarrow V_3 \rightarrow V_8 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_9 \rightarrow V_7 \rightarrow V_8 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_9 \rightarrow V_7 \rightarrow V_8 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_9 \rightarrow V_8 \rightarrow V_3 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_9 \rightarrow V_8 \rightarrow V_7 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_9 \rightarrow V_8 \rightarrow V_7 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_9 \rightarrow V_4 \rightarrow V_3 \rightarrow V_7 \rightarrow V_8 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_9 \rightarrow V_4 \rightarrow V_3 \rightarrow V_8 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_9 \rightarrow V_4 \rightarrow V_7 \rightarrow V_3 \rightarrow V_8 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_9 \rightarrow V_4 \rightarrow V_7 \rightarrow V_8 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_9 \rightarrow V_4 \rightarrow V_7 \rightarrow V_8 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_9 \rightarrow V_4 \rightarrow V_8 \rightarrow V_3 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_9 \rightarrow V_4 \rightarrow V_8 \rightarrow V_7 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_9 \rightarrow V_4 \rightarrow V_8 \rightarrow V_7 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_9 \rightarrow V_8 \rightarrow V_4 \rightarrow V_3 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_9 \rightarrow V_8 \rightarrow V_4 \rightarrow V_7 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_2 \rightarrow V_9 \rightarrow V_8 \rightarrow V_4 \rightarrow V_7 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_2 \rightarrow V_4 \rightarrow V_3 \rightarrow V_7 \rightarrow V_8 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_2 \rightarrow V_4 \rightarrow V_3 \rightarrow V_8 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_3 \rightarrow V_8 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_8 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_8 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_2 \rightarrow V_4 \rightarrow V_8 \rightarrow V_3 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_2 \rightarrow V_4 \rightarrow V_8 \rightarrow V_7 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_2 \rightarrow V_4 \rightarrow V_8 \rightarrow V_7 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_2 \rightarrow V_8 \rightarrow V_4 \rightarrow V_3 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_2 \rightarrow V_8 \rightarrow V_4 \rightarrow V_7 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_2 \rightarrow V_8 \rightarrow V_4 \rightarrow V_7 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_8 \rightarrow V_2 \rightarrow V_4 \rightarrow V_3 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_8 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_1 \rightarrow V_9 \rightarrow V_8 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_3 \rightarrow V_7 \rightarrow V_8 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_3 \rightarrow V_8 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_3 \rightarrow V_8 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_8 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_8 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_8 \rightarrow V_3 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_8 \rightarrow V_7 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_8 \rightarrow V_7 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_2 \rightarrow V_8 \rightarrow V_4 \rightarrow V_3 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_2 \rightarrow V_8 \rightarrow V_4 \rightarrow V_7 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_2 \rightarrow V_8 \rightarrow V_4 \rightarrow V_7 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_8 \rightarrow V_2 \rightarrow V_4 \rightarrow V_3 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_8 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_1 \rightarrow V_8 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $
    $ V_9 \rightarrow V_8 \rightarrow V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_3 \rightarrow V_7 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_8 \rightarrow V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_3 \rightarrow V_6 \rightarrow V_5 $
    $ V_9 \rightarrow V_8 \rightarrow V_1 \rightarrow V_2 \rightarrow V_4 \rightarrow V_7 \rightarrow V_6 \rightarrow V_3 \rightarrow V_5 $

11、请在深度优先搜索算法的基础上设计一个对有向无环图进行拓扑排序的算法。

// enDegree表示每个顶点的入度
// relayVec是一个二维数组,relayVec[i][j]表示依赖于i的第j个元素的编号
// a依赖于b表达的意思是,拓扑排序中必须先输出b,然后才能输出a
void topSort(vector<vector<int>>& relayVec, vector<int>& enDegree){
    queue<int> myQueue;
    for(int i = 0; i < enDegree.size(); i++){
	    if(enDegree[i] == 0){
		    myQueue.push(i);
	    }
    }
    while(!myQueue.empty()){
        int top = myQueue.front();
        //所有依赖于编号为top的元素的入度减小1,如果减小后刚好为0,入队
        for(int i = 0; i < relayVec[top].size(); i++){
    	    if(--enDegree(relayVec[top][i]) == 0)
    		    myQueue.push(relayVec[top][i]);
    	}
        myQueue.pop();
    }
}

12、设计一个算法利用图的遍历方法输出一个无向图G中从顶点$V_i$到$V_j$的长度为S的简单路径,设图采用邻接链表作为存储结构。

int visit[MAX_VERTEX_NUM]; //记录某个点是否被访问以及是第几个被访问的
int nodeNum = 0; //第几个被访问的结点
Status ExistPathLenS(ALGraph G, int i, int j, int s) {
    ArcNode *p;
	
    visit[i] = ++nodeNum; //长度为nodeNum时访问到
	if (i == j && s == 0) return TRUE; //找到长度为s的简单路径
	else if (s > 0) {
	    //从i的邻边开始找
	    for (p = G.vers[i].firstarc; p; p = p->next) {
	    	if (visit[p->adjV] == 0) { //没有访问过
	    		if (ExistPathLenK(G, p->adjV, j, s-1))
	    			return TRUE; //从邻边p中找到了
	    		else {
	    			visit[p->adjV] = 0; //邻边p中没有找到,从p->adj退出来
                    nodeNum--; //退一步,继续找
                }
	    	}
            else { //已经访问过了
	    		continue;
	    	}
    	}
    }
    return FALSE;
}

13、假设一个工厂的进度计划用AOE网表示,如图7所示。

①求出每个事件的最早发生时间和最晚发生时间。

②该工程完工至少需要多少时间?

③求出所有关键路径和关键活动。


图7 一个AOE网

  ①如图所示

  ②该工程完工至少需要的时间为30
  ③关键路径 $V_0 \rightarrow V_2 \rightarrow V_3 \rightarrow V_6 \rightarrow V_8 \rightarrow V_9 $
   关键活动 $V_0, V_2, V_3, V_6, V_8, V_9 $