图的博客作业

0.PTA得分截图

1.本周学习总结（6分）

1.1 图的存储结构

1.1.1 邻接矩阵

一个无向图的邻接矩阵：

一个网图的邻接矩阵：

邻接矩阵的结构体定义：

#define MAXV<最大顶点个数>
typedef struct
{
 int no;//顶点编号
 InfoType info;//顶点其他信息
}VertexType;

typedef struct //图的定义
{
 int edges[MAXV][MAXV];//邻接矩阵
 int n,e;//顶点数，边数
 VertexType vexs[MAXV];//存放顶点信息
}MatGraph

建图函数：

//邻接矩阵创建图
void CreateMGraph(MGraph &g,int n,int e)//n顶点个数，e边个数
{  
  int i,j,a,b;
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
      g.edges[i][j]=0;
  for(i=1;i<=e;i++)
  {
     cin>>a>>b;
     g.edges[a-1][b-1]=1;
     g.edges[b-1][a-1]=1;
   }
 g.n=n;
 g.e=e;
}

1.1.2 邻接表

有向图：

该图的邻接表：

邻接矩阵的结构体：

typedef struct ANode
{
 int adjvex;//该边的邻接点编号
 struct ANode * nextarc;//指向下一条边的指针
 int weight;//权值
}ArcNode;//边结点类型

typedef struct Vnode
{
 InfoType info;//顶点的其他信息
 ArcNode * firstarc;//指向第一个边结点
}VNode；//邻接表的头结点类型

typedef struct
{
 VNode adjlist[MAXV];//邻接表的头结点数组
 int n，e；//n顶点数，e边数
}AdjGraph;//完整图邻接表类型

建图函数:

void CreatrAdj(AdjGraph *&G,int n,int e)//创建图邻接表
{ 
  int i,j,a,b;
  ArcNode *p;
  G=new AdjGrapg;
  for(i=0;i<n;i++)
     G->adjlist[i].firstarc=NULL;
//给邻接表中所有头结点的指针域置初值
 for（i=1;i<e;i++)//根据输入边建图
   {
      cin>>a>>b;
      p=new ArcNode;//创建一个结点p
      p->adjvex=b;//存放邻接点
      p->nextarc=G->adjlist[a].firstarc;//采用头插法插入结点p
      G->adjlist[a].firstarc=p;
    }
G->n=n;
G->e=n;
}

1.1.3 邻接矩阵和邻接表表示图的区别

当图为稀疏图、顶点较多，即图结构比较大时，更适宜选择邻接表作为存储结构。当图为稠密图、顶点较少时，或者不需要记录图中边的权值时，使用邻接矩阵作为存储结构较为合适。使用邻接矩阵的时间复杂度为O(n^2)，使用邻接表的时间复杂度为O(n+e)。

1.2 图遍历

1.2.1 深度优先遍历

首先从1开始，1结点处可以访问2，3两个结点，那么按照我们自定义的优先顺序线访问2结点，此时，2结点有4，5两个结点访问，依旧按次序访问呢4结点，4结点可以访问5结点，5结点无法继续向下访问故结束访问，并回退4结点，4结点无法没有其他分支且自己已被访问故又退回2结点，2结点的两个分支4，5结点均已被访问，故再退回1结点，此时只有3结点未被访问，访问3结点，最终得到次序：1-2-4-5-3
深度遍历代码:

void DFS(ALGraph* G, int v)
{
   ArcNode* p;
   visited[v] = 1;//置已访问标记
   printf("%d", v);
   p = G->adjlist[v].firstarc;
   while (p!=NULL)
   {
   	if (visited[p->adjvex] == 0)
   		DFS(G, p->adjvex);
   	p = p->nextarc;	
   }
}

深度遍历适用迷宫问题的求解，生产上广泛用于拓扑排序，寻路(走迷宫)。

1.2.2 广度优先遍历

首先从1开始，1结点处可以访问2，3两个结点，我们访问并以此把两个结点的访问顺序放入队列，然后按照入队顺序（如2，3），之后我们出队状态2，依次访问2结点的下两个结点（4，5结点），并入队4，5结点，再之后我们出队3结点，并依次访问后续，此时发现所有的结点已经被访问完毕了，可以结束搜索，最后我们得到次序：1-2-3-4-5
广度遍历代码：

void BFS(ALGraph* G, int v)//v节点开始遍历
{
   queue<int>q; int w;
   int visited[MAXV];//定义存放节点的访问标志数
   ArcNode* p;
   for (i = 0; i < g.n; i++) visited[i] = 0;//访问标志数组q
   q.push(v); visited[v] = 1; cout << v << " ";
   while (!q.empty())
   {
   	w = q.front(); q.pop();//访问队头
   	p = G.adjlist[w].firstarc;//访问w第一条边
   	while (p!=NULL)
   	{
   		W = P->adjvex;//边的邻接点
   		if (visited[w] == 0)//若当前邻接点未被访问
   		{
   			q.push(w);
   			visited[w] = 1;
   			cout << w << " ";
   		}
   		p = p->nextarc;
   	}
   }
}

1.3 最小生成树

最小生成树是一副连通加权无向图中一棵权值最小的生成树。在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且 (V, T) 为树，使得的 w(T) 最小，则此 T 为 G 的最小生成树。

1.3.1 Prim算法求最小生成树

基于上述图结构求Prim算法生成的最小生成树的边序列:

假设从顶点0出发，0到3的权值最小，为3；继续找，3到1的权值最小为1，找到1；继续，1到2的权值最小，找到2；最后找到4。所以改图的一个Prim算法生成的最小生成树边序列：{（0，3），（3，1），（1，2），（2，4）}

实现Prim算法的2个辅助数组是什么？其作用是什么？Prim算法代码。

1.closest[i]:最小生成树的边依附在U中顶点编号。
2.lowcost[i]表示顶点i到U中顶点的边权重，取最小权重的顶点k加入U。并规定lowcost[k]=0表示这个顶点在U中
3.(closest[k]，k）构造最小生成树的一条边。

void Prim(MatGraph g,int v)
{
 int lowcost[MAXV];
 int MIN;
 int closest[MAXV],i,j,k;
 for(i=0;i<g.n;i++)//给lowcost[]和closest[]置初值
    {
       lowcost[i]=g.edges[v][i];
       closest[i]=v;
     }
 for(i=1;i<g.n;i++)//找出（n-1)个顶点
    {
        MIN=INF;
        for(j=0;j<g.n;j++)//在（V-U）中找出离U最近的顶点k
           if（lowcost[j]!=0&&lowcost[j]<MIN)
              {
                 MIN=lowcost[j];
                 K=J;//K记录最近顶点的编号
               }
       printf("边（%d,&d)权为：%d
",closest[k],k,MIN);//输出最小生成树的一条边
       lowcost[k]=0;//标记k已经加入U
       for（j=0;j<g.n;j++)//对（V-U）中的顶点j进行调整
           if（lowcost[j]!=0&&g.edges[k][j]<lowcost[j]）
             {
                  lowcost[j]=g.edges[k][j]
                  closest[j]=k;//修改数组lowcost和closest
              }
     }
}

分析Prim算法时间复杂度，适用什么图结构，为什么？

Prim()算法中有两重for循环，所以时间复杂度为O(n^2),其中n为图的顶点个数。Prim（）算法的执行时间与图中的边数e无关，所以它特别适合用稠密图求最小生成树。

1.3.2 Kruskal算法求解最小生成树

基于上述图结构求Kruskal算法生成的最小生成树的边序列

所有边按照权值大小排序，按照从小到大的顺序进行判断，首先最小是（0，3），其次是（1.2），然后是（1，3），两点不在同一棵树上，可以连接，然后是（2，4），同样不在一棵树上，进行连接。所以改图用Kruskal算法生成的最小生成树的边序列为{(0,3),(1,2),(1,3),(2,4)}。

实现Kruskal算法的辅助数据结构是什么？其作用是什么？Kruskal算法代码。

1.设置一个辅组数组vset[0,n-1],vset[i]用于记录一个顶点i所在的连通分量编号
2.用一个数组E[]存放图G中的所有边，要求它们是按照权值从小到大的顺序排序的，为此先从图G的邻接矩阵中获取所有边集E，再采用直接插入排序法对边集E按权值递增排序。

void Kruskal(AdjGraph *g)
{
 int i,j,u1,v1,sn1,sn2,k;
 int vest[MAXV];//集合辅组数组
 Edge E[MaxSize];//存放所有边
 k=0;//E数组的下标从0开始计
 for(i=0;i<g.n;i++)
   {
      p=g->adjlist[i].firstarc;
      while(p!=NULL)
      {
        E[k].u=i;E[k].v=p->adjlist;
        E[k].w=p->weight;
        k++;p=p->nextarc;
       }
    InsertSort(E,g.e);
    for(i=0;i<g.n;i++)
        vest[i]=i;
    k=1;
    j=0;
    while(k<g.n)
    {
       u1=E[j].u;v1=E[j].v;
       sn1=vset[u1];
       sn2=vset[v1];
       if(sn1!=sn2)
         {
           printf("(%d,%d):%d
",u1,v1,E[j].w);
           k++;
           for(i=0;i<g.n;i++)
              if(vest[i]==sn2)
                 vest[i]=sn1;
          }
         j++;
      }
}

分析Kruskal算法时间复杂度，适用什么图结构，为什么？

如果给定的带全连通图G有n个顶点，e条边，在上诉算法中，对边集E采用直接插入排序的时间复杂度为O（e2)。while循环是在e条边中选取（n-1）条边，而其中的for循环执行n次，因此while循环的时间复杂度为O(n2+e2)。对于连通无向图，e>=(n-1),那么用Krusakl算法构造最小生成树的时间复杂度的为O(e2)。Kruskal算法的执行时间仅与图中的边数有关，与顶点数无关，所以它特别适合用稀疏图求最小生成树。

1.4 最短路径

1.4.1 Dijkstra算法求解最短路径

基于上述图结构，求解某个顶点到其他顶点最短路径。（结合dist数组、path数组求解）
Dijkstra算法需要path[],dist[]。其中path[j]存放源点v->j的最短路径上顶点j的前一个顶点编号，其中源点v是默认的；dist[j]表示源点v->j得到最短路径长度，其中源点v是默认的。
算法代码：

void Dijkstra(MatGraph g, int v)//Dijkstra算法
{
	int dist[MAXV], path[MAXV];
	int S[MAXV];//S[i]=1表示顶点i在S中，S[i]=0表示顶点i在U中
	int MINdis, i, j, u;
	for (i = 0;i < g.n;i++)
	{
		dist[i] = g.edges[v][i];//距离初始化
		S[i] = 0;//S[]置空
		if (g.edges[v][i] < INF)//路径初始化
			path[i] = v;//顶点v到顶点i有边时，置顶点i的前一个顶点为v
		else path[i] = -1;//顶点v到顶点i无边时，置顶点i的前一个顶点为-1
	}
	S[v] = 1; path[v] = 0;//源点编号v放入S中
	for (i = 0;i < g.n - 1;i++)//循环直到所有顶点的最短路径都求出
	{
		MINdis = INF;//MINdis置最大长度初值
		for(j=0;j<g.n;j++)//选取不在S中(即在U中)且具有最小最短路径长度的顶点u
			if (S[j] == 0 && dist[j] < MINdis)
			{
				u = j;
				MINdis = dist[j];
			}
		S[u] = 1;//顶点u加入S中
		for(j=0;j<g.n;j++)//修改不在S中(即在U中)的顶点的最短路径
			if(S[j]==0)
				if (g.edges[u][j] < INF && dist[u] + g.edges[u][j] < dist[j])
				{
					dist[j] = dist[u] + g.edges[u][j];
					path[j] = u;
				}
	}
	Dispath(g, dist, path, S, v);//输出最短路径
}
void Dispath(MatGraph g, int dist[], int path[], int S[], int v)
{//输出从顶点v出发的所有最短路径
	int i, j, k;
	int apath[MAXV], d;//存放一条最短路径(逆向)及其顶点个数
	for(i=0;i<g.n;i++)//循环输出从顶点v到i的路径
		if (S[i] == 1 && i != v)
		{
			printf("从顶点%d到顶点%d的路径长度为：%d	路径为：", v, i, dist[i]);
			d = 0; apath[d] = i;//添加路径上的终点
			k = path[i];
			if (k == -1)//没有路径的情况
				printf("无路径
");
			else//存在路径时输出该路径
			{
				while (k != v)
				{
					d++; apath[d] = k;
					k = path[k];
				}
				d++; apath[d] = v;//添加路径上的起点
				printf("%d", apath[d]);//先输出起点
				for (j = d - 1;j >= 0;j--)//在输出其他顶点
					printf(",%d", apath[j]);
				printf("
");
			}
		}
}

时间复杂度为O(n^2),Dijkstra适用于有向无环图。

1.4.2 Floyd算法求解最短路径

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似，用于解决多源最短路径、无负权回路即可、边权可正可负、运行一次算法即可求得任意两点间最短路。
Floyd算法需要二维数组path[][]保存最短路径，同时它与当前迭代的次数有关。path[i][j]存放着考查顶点0、1、...、k之后得到的i->j的最短路径中顶点j的前一个顶点编号。
Floyd算法优势：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单，时间复杂度为O(n^2)。

1.5 拓扑排序

找一个有向图，并求其对要的拓扑排序序列
实现拓扑排序代码，结构体如何设计？
书写拓扑排序伪代码，介绍拓扑排序如何删除入度为0的结点？
如何用拓扑排序代码检查一个有向图是否有环路？

1.6 关键路径

什么叫AOE-网？
什么是关键路径概念？
什么是关键活动？

2.PTA实验作业（4分）

2.1 六度空间（2分）

选一题，介绍伪代码，不要贴代码。请结合图形展开分析思路。