DS博客作业04--图

0.PTA得分截图

1.本周学习总结（0-5分）

1.1 总结图内容

1.1.1图存储结构：

• 定义：图的存储结构相对于线性表和树来说更为复杂，因为图中的顶点具有相对概念，没有固定的位置。
• 分类：两种比较常见和重要的图的存储结构：邻接矩阵和邻接表。
• 邻接矩阵：顾名思义，是一个矩阵，一个存储着边的信息的矩阵，而顶点则用矩阵的下标表示。对于一个邻接矩阵M，如果M(i,j)=1，则说明顶点i和顶点j之间存在一条边，对于无向图来说，M (j ,i) = M (i, j)，所以其邻接矩阵是一个对称矩阵；对于有向图来说，则未必是一个对称矩阵。邻接矩阵的对角线元素都为0。如图
  
  
• 邻接表：数组于链表相结合的存储方法称为邻接表。如图
  

1.1.2图遍历及应用。

• 图的深度遍历（DFS）
  • 基本思想：递归
    （1）访问顶点A；
    （2）从A的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
    （3）重复上面两步，直至所有顶点均被访问过。
  • 辅助数组：visited[ ]
    用来记录每个顶点是否被访问过。1，访问过；0，未访问过。
  • 算法实现：
    邻接矩阵：

void DFS(MGraph &G, int v, int visited[]) {
    int i;
    printf("%c
", G.vexs[v]);
    visited[v] = 1;
    for(i=0; i<G.vexNum; i++) {
        if (G.arcs[v][i] != 0 && G.arcs[v][i] != INFINITY && !visited[i]) {
            DFS(G, i, visited);
        }
    }
}

邻接表：

void DFS(ALGraph &G, int v, int visited[]) {
    ArcNode *p = G.adjList[v].firstArc;
    printf("%c	", G.adjList[v].vertex);
    visited[v] = 1;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

• 图的广度遍历（BFS）
  • 基本思想：
    （1）访问初始顶点A，并将其顶点序号入队；
    （2）队列不空，则出队；依次访问它的每一个未被访问过的邻接点，并将其编号入队；
    （3）重复（2）直至队列空，遍历结束。
  • 算法实现：
    队列操作：

typedef struct {
    int front, reer;
    int data[MAXSIZE];
} Queue;

void initQueue(Queue &Q) {
    Q.front = Q.reer = 0;
    for(int i=0; i<MAXSIZE; i++) {
        Q.data[i] = INFINITY;
    }
}

void enterQueue(Queue &Q, int v) {
    if((Q.front+1)%MAXSIZE == Q.reer) {
        printf("Queue full
");
        return;
    }
    Q.data[Q.front] = v;
    Q.front = (++Q.front)%MAXSIZE;
}

int deletQueue(Queue &Q) {
    int i = Q.data[Q.reer];
    Q.data[Q.reer] = INFINITY;
    Q.reer = (++Q.reer)%MAXSIZE;
    return i;
}

int emptyQueue(Queue Q) {
    if(Q.front == Q.reer) {
        return 0;
    }
    return 1;
}

邻接矩阵：

void BFS(MGraph G, Queue &Q, int v, int visited[]) {
    int a, i = 0;
    enterQueue(Q, v);
    while(emptyQueue(Q)) {
        a = deletQueue(Q);
        visited[a] = 1;
        printf("%c	", G.vexs[a]);
        i=0;
        while(i<G.vexNum) {
            if(G.arcs[a][i] == 1) {
                if(visited[i]==0) {
                    enterQueue(Q, i);
                    visited[i] = 1;
                }
            }
            i++;
        }
    }
}

邻接表：

void BFS(ALGraph G, Queue &Q, int v, int visited[]) {
    int a;
    ArcNode *p=NULL;
    initQueue(Q);
    enterQueue(Q, v);
    
    visited[v] = 1;
    while (emptyQueue(Q)) {
        a = deletQueue(Q);
        printf("%c	", G.adjList[a].vertex);
        p = G.adjList[a].firstArc;
        while (p) {
            if(!visited[p->adjvex]) {
                enterQueue(Q, p->adjvex);
                visited[p->adjvex] = 1;
            }
            p = p->next;
        }
    }
}

• 如何判断图是否连通:
  • 思想：若用DFS，只需要判断最后count的值是否是全部的节点就可以，如果小于总节点数，则证明是不连通的，如果相等，则证明是连通的。若用BFS，同样只要有未访问到的节点，那么该图一定是不连通的。
  • DFS：

int count = 0;
void DFS(MGrap G. int i)
{
    int j = 0;
    visited[i] = 1;
    count++;
    for(j=0; j<G.numVertexes; j++)
    {
        if(G.arc[i][j]==1 && !visited[j])//i和j有关系相邻，并且j顶点没有被访问过
        {
            DFS(G, j);
        }
    }
}

• BFS:

void bfs(int s){            //用队列广搜
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=true;
        for(int i=0;i<g[x].size();++i){
            if(vis[g[x][i]]) g[x].erase(g[x].begin()+i);//删除图中已经遍历过的点，可提高遍历速度
            else q.push(g[x][i]);
        }
    }
}

bool judge(){                   //判断是否所有点已被遍历过
    for(int i=1;i<=n;++i)
        if(!vis[i])
            return false;
    return true;
}

• 图的路径：
  • 定义：由顶点和相邻顶点序偶构成的边所形成的序列
  • 关键路径：具有最大路径长度的路径称为关键路径。
• 如何找最短路径：
  • Dijkstra（狄克斯特拉）算法
    算法思想：对于给定的顶点a，将其放入顶点集合U中，然后找到以顶点集合U中的点为顶点的所有边中权值最小的边，将这条边的终点也加入到顶点集合U中，然后更新从给定点a到顶点集合U中能够直接关联到的顶点的已知最短路径的值；重复以上步骤，直到顶点集合U中包含所有n个顶点。
  • Floyd算法
    算法思想：采用动态规划的思想：从任意节点i到任意节点j的最短路径有2种可能：1)直接从i直接到j，2)从i经过若干个节点k到j。所以，我们假设arcs(i,j)为节点i到节点j的最短路径的距离，对于每一个节点k，我们检查arcs(i,k) + arcs(k,j) < arcs(i,j)是否成立，如果成立，证明从节点i到节点k再到节点j的路径比节点i直接到节点j的路径短，我们便设置arcs(i,j) = arcs(i,k) + arcs(k,j)，这样一来，当我们遍历完所有节点k，arcs(i,j)中记录的便是节点i到节点j的最短路径的距离。

1.1.3最小生成树相关算法及应用

• 概念：一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点和构成一棵树的(n-1)条边。不能回路。　　
• 最小生成数算法：
  • Kruskal算法：
    Kruskal算法是直接建立在上一节中给出的一般最小生成树算法的基础之上的。该算法找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v)作为安全边，并把它添加到正在生长的森林中。设C1和C2表示边(u,v)连结的两棵树。因为(u,v)必是连结C1和其它某棵树的一条轻边，所以由推论1可知(u,v)对C1是安全边。Kruskal算法是一种贪心算法，因为算法每一步添加到森林中的边的权值都尽可能小。
    如图：
    
    代码：

void Kruskal(AdjGraph *g)
{     int i，j，u1，v1，sn1，sn2，k;
      int vset[MAXV]; //集合辅助数组
      Edge E[MaxSize];	//存放所有边
      k=0;			//E数组的下标从0开始计
    for (i=0;i<g.n;i++)	//由g产生的边集E，邻接表
    {   p=g->adjlist[i].firstarc;
        while(p!=NULL)    
	{    E[k].u=i;E[k].v=p->adjvex;
             E[k].w=p->weight;
	     k++; p=p->nextarc;
	}
    }
     Sort(E，g.e);	//用快排对E数组按权值递增排序
     for (i=0;i<g.n;i++) 	//初始化集合
	vset[i]=i;
	k=1;		//k表示当前构造生成树的第几条边，初值为1
	j=0;		//E中边的下标，初值为0
	while (k<g.n)	//生成的顶点数小于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++;		   	//生成边数增1
		for (i=0;i<g.n;i++)  	//两个集合统一编号
		      if (vset[i]==sn2) 	//集合编号为sn2的改为sn1
			vset[i]=sn1;
	      }
	     j++;			   //扫描下一条边
        }
}

• Prim算法：
  正如Kruskal算法一样。Prim算法也是最小生成树一般算法的特例。它的执行非常类似于寻找图的最短通路的Dijkstra算法。Prim算法的特点是集合A中的边总是只形成单棵树。在算法的每一步，树中与树外的结点确定了图的一个割，并且通过该割的轻边被加进树中。树从任意根结点r开始形成并逐渐生长直至该树跨越了V中的所有结点。在每一步，连接A中某结点到V-A中某结点的轻边被加入到树中。因此当算法终止时，A中的边就成为一棵最小生成树。因为每次添加到树中的边都是使树的权尽可能小的边，因此上述策略是“贪心”的。
  如图：
  
  代码：

void Prim(MGraph g,int v)
{  int lowcost[MAXV],min,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++)	//修改数组lowcost和closest
	   if (lowcost[j]!=0 && g.edges[k][j]<lowcost[j])
	   {	
                lowcost[j]=g.edges[k][j];
		closest[j]=k;
	   } 
   }
}

1.1.4最短路径相关算法及应用。

• 最短路径的定义：
  在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。
• Dijkstra算法：解决单源最短路径问题的方法之一就是Dijkstra算法。
  • 展示图：
    
  • 代码实现：(来自于PTA7-6的题目解法中的实际应用代码)

void Dijkstra(Graph G, int dist[], int path[], int s, int cost[]) {
	int vertex[MAXN];
	int v, w;
	for (v = 0; v < G->Nv; v++) {
		if (G->Data1[s][v]) path[v] = s;
		else path[v] = -1;
		dist[v] = G->Data1[s][v];
		cost[v] = G->Data2[s][v];
		vertex[v] = 0;
	}
	vertex[s] = 1;
	dist[v] = 0;
	for (; ; ) {
		v = FindMinDist(G, dist, vertex);
		if (v == -1) break;
		vertex[v] = 1;
		for (w = 0; w < G->Nv; w++) {
			if (!vertex[w] && dist[w] > dist[v] + G->Data1[v][w]) {
				dist[w] = dist[v] + G->Data1[v][w];
				path[w] = v;
				cost[w] = cost[v] + G->Data2[v][w];
			}
			else if (!vertex[w] && dist[w] == dist[v] + G->Data1[v][w]) {
				if (cost[w] > cost[v] + G->Data2[v][w]) {
					path[w] = v;
					cost[w] = cost[v] + G->Data2[v][w];
				}
			}
		}
	}
}

• Bellman-Ford算法：在单源最短路径问题的某些实例中，可能存在权为负的边，当不存在源s可达的负回路时，我们可用Bellman-Ford算法实现。
  • 算法思路：
    第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
    第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
    第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：
    d（v） > d (u) + w(u,v)
    则返回false，表示途中存在从源点可达的权为负的回路。
  • 代码实现：

bool Bellman_Ford()  
{  
    for(int i = 1; i <= nodenum; ++i) //初始化  
        dis[i] = (i == original ? 0 : MAX);  
    for(int i = 1; i <= nodenum - 1; ++i)  
        for(int j = 1; j <= edgenum; ++j)  
            if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~）  
            {  
                dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;  
                pre[edge[j].v] = edge[j].u;  
            }  
            bool flag = 1; //判断是否含有负权回路  
            for(int i = 1; i <= edgenum; ++i)  
                if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)  
                {  
                    flag = 0;  
                    break;  
                }  
                return flag;  
}  

1.1.5拓扑排序、关键路径

• 拓扑排序：
  • 定义：在一个有向图中找一个拓扑序列的过程称为拓扑排序。
  • 由AOV网构造拓扑序列的拓扑排序算法的步骤：
    (1) 选择一个入度为0的顶点并输出之；
    (2) 从网中删除此顶点及所有出边。
    (3) 循环上述操作直到不存在入度为0的顶点为止。
  • 应用：
    拓扑排序可以用来判断图中是否存在回路：利用循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。
• 关键路径：
  • 定义：关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。
  • 意义：优化关键路径是一种提高设计工作速度的有效方法。
  • 步骤：
    (1) 从开始顶点 v1 出发，令 ve(1)=0，按拓扑有序序列求其余各顶点的可能最早发生时间。 [3]
    Ve(k)=max{ve(j)+dut(<j,k>)} , j ∈ T 。其中T是以顶点vk为尾的所有弧的头顶点的集合（2 ≤ k ≤ n）。
    如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，不能求出关键路径，算法结束。
    (2) 从完成顶点 出发，令 ，按逆拓扑有序求其余各顶点的允许的最晚发生时间：
    vl(j)=min{vl(k)-dut(<j,k>)} ,k ∈ S 。其中 S 是以顶点vj是头的所有弧的尾顶点集合（1 ≤ j ≤ n-1）。
    (3) 求每一项活动ai（1 ≤ i ≤ m）的最早开始时间e(i)=ve(j)，最晚开始时间l(i)=vl(k)-dut(<j,k>) 。
    若某条弧满足 e(i)=l(i) ，则它是关键活动。关键活动连接起来就是关键路径

1.2.谈谈你对图的认识及学习体会。

在学习本章前就已经学习了树这种非线性结构，所以对图的学习有了一定的思想基础，相对于树的一对多，图是一种多对多的数据结构
图在实际的生产活动中有着广泛的应用，利用图的遍历可以寻找路径，基于图之上的最小生成树相关算法可以计算出建设道路或者通信网络的最低预算成本等问题
图即是数据结构较难的一部分，也是最重要的一部分，在学习完图的相关知识后，思维又有了一定的创新和拓展

2.阅读代码（0--5分）

2.1 题目及解题代码

• 题目：
  

• 解题代码：

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool: 
        def DFSFind(graph,start,nodes,preColor):

            if nodes[start] == preColor:
                return False
            if nodes[start] != -1 and nodes[start] != preColor:
                return True

            nodes[start] = 1 - preColor
            flag = True
            for neighboor in graph[start]:
                flag = flag and DFSFind(graph,neighboor,nodes,nodes[start])

            return flag

        nodes = [-1] * len(graph)
        flag = True
        for i in range(len(graph)):
            if nodes[i] == -1:
                flag = flag and DFSFind(graph,i,nodes,1)
        return flag

2.1.1 该题的设计思路

用深度优先搜索对图进行遍历，用涂色法进行判断是否为二分图，其中运用了递归的方法
时间复杂度为O（n）
空间复杂度为O（n²）

2.1.2 该题的伪代码

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool: 
        def DFSFind(graph,start,nodes,preColor):
            if nodes[start]不等于preColor then 返回False
            if nodes[start]不为-1并且nodes[start]不等于preColor then 返回True

            nodes[start]赋值为1-preColor用于表示另一种颜色
            flag赋值为True
            for neighboor 在 graph[start]内:
                  flag = flag and DFSFind(graph,neighboor,nodes,nodes[start])

            返回flag
            

      node赋值为-1乘图的长度
      flag赋值为True
      for i在range(len(graph))内：
            if nodes[i] 等于-1 then  flag = flag and DFSFind(graph,neighboor,nodes,nodes[start])
      返回flag

2.1.3 运行结果

2.1.4 分析该题目解题优势及难点。

用了DFS算法，能让我们近期刚学的人能够理解，涂色法也是简单易懂
但他的代码很多不是我们刚学C++的能够理解的，比如for循环的那个和if的条件

2.2 题目及解题代码

• 题目：
  
• 解题代码：

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> rp(1001);
        int sz = edges.size();
        // 初始化各元素为单独的集合，代表节点就是其本身
        for(int i=0;i<sz;i++)
            rp[i] = i;
        for(int j=0;j<sz;j++){
            // 找到边上两个节点所在集合的代表节点
            int set1 = find(edges[j][0], rp);
            int set2 = find(edges[j][1], rp);
            if(set1 == set2)  // 两个集合代表节点相同，说明出现环，返回答案
                return edges[j]; 
            else    // 两个集合独立，合并集合。将前一个集合代表节点戳到后一个集合代表节点上
                rp[set1] = set2;
        }
        return {0, 0};
    }

    // 查找路径并返回代表节点，实际上就是给定当前节点，返回该节点所在集合的代表节点
    // 之前这里写的压缩路径，引起歧义，因为结果没更新到vector里，所以这里改成路径查找比较合适
    // 感谢各位老哥的提议
    int find(int n, vector<int> &rp){
        int num = n;
        while(rp[num] != num)
            num = rp[num];
        return num;
    }
};

2.2.1 该题的设计思路:

1.初始化集合
2.读取（1，2）
3.读取（3，4）
4.读取（3，2）
5.读取（1，4）
时间复杂度：O（n）
空间复杂度：O（n）

2.2.2 该题的伪代码

主函数：
      初始化各元素为单独的集合
      for循环初始化rp数组
      for循环用find函数找到边上两个节点所在集合的代表节点
      if 两个节点相等 then 返回答案edges[j]
      else rp[set1] = set2
      返回{0, 0}
find函数：
      while rp[num]不等于num
            num=rp[num]
      返回num

2.2.3 运行结果：

2.2.4 分析该题目解题优势及难点。

时间复杂度和空间复杂度均为O(n)算法的速率相对较快
思路清晰便于小白理解

2.3 题目及解题代码

• 题目：
  

• 解题代码：

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n==1 && edges.size()==0)return {0};//面向测试用例编程
        vector<int>res;
        vector<int>indegree(n);
        vector<vector<int>> graph(n,vector<int>());
        queue<int>q;

        //构造临接表
        for(auto item:edges){
            graph[item[0]].push_back(item[1]);
            graph[item[1]].push_back(item[0]);
        }

        //构造入度表
        for(auto item:edges){
            indegree[item[0]]++;
            indegree[item[1]]++;
        }

        //将叶子节点，也就是入度数为1的点加入队列
        for(int i=0;i<n;i++){
            if(indegree[i]==1)q.push(i);
        }
        while(n>2){
            int count=q.size();
            n-=count;
            //每次将所有的叶子节点去除，并且将新的叶子节点加入队列
            while(count--){
                int item=q.front();
                q.pop();
                int size=graph[item].size();
                for(int i=0;i<size;i++){
                    //既然是无向边，那么要将两个节点的入度数都要减一
                    --indegree[item];
                    --indegree[graph[item][i]];
                    //将新的叶子节点入队
                    if(indegree[graph[item][i]]==1)q.push(graph[item][i]);
                }
            }
        }

        //此时队列中的节点便是要返回的值，不论是一个还是两个节点。
        while(!q.empty()){
            res.push_back(q.front());
            q.pop();
        }
        
        return res;
    }
};

2.3.1 该题的设计思路：

时间复杂度：O（n²）
空间复杂度：O（1）

2.3.2 该题的伪代码：

      if n为1且edges的长度为0 then 返回{0}
      for循环构建邻接表
      for循环构建入度表
      for循环将入度数为1的叶子节点加入队列
      while n大于2
            n-=count      //每次将所有的叶子节点去除，并且将新的叶子节点加入队列
            while count递减至0
                  将队列首赋值给item并将队首出列
                  for循环将两个节点的入度数减1并将新的叶子节点入队
      while循环将剩余的1到2个节点存入res
      返回res

2.3.3 运行结果：

2.3.4 该题的优势及难点

该题的作者用上了大量的注释易于读者的阅读
代码涉及了队列，邻接表等知识点，易于初学者回顾所学知识，促进对知识的掌握
该题有些条件的编译不是很明白，需要去百度查找才能理解