作业16-图的遍历与最小生成树(防止标题重复)

快来打我* 2022-12-27 11:17 116阅读 0赞

作业16-图的遍历与最小生成树  
2-1  
给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：©  
A.22  
B.20  
C.15  
D.8  
\[解析\]求最小生成树,根据prim算法,先加入任意一个顶点到集合U,  
然后每次从 与结合U 相连的边中 找权值最小的边以及 这条边的端点,  
将端点加入到集合U中,直到将所有顶点都加入到U中

2-3  
给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：(A)  
A.24  
B.23  
C.18  
D.17

2-4  
给定有权无向图如下。关于其最小生成树，下列哪句是对的？(A)  
A.最小生成树不唯一，其总权重为23  
B.最小生成树唯一，其总权重为20  
C.边(B, F)一定在树中，树的总权重为23  
D.边(H, G)一定在树中，树的总权重为20

6-1 邻接矩阵存储图的深度优先遍历 (20分)

试实现邻接矩阵存储图的深度优先遍历。  
函数接口定义：

void DFS( MGraph Graph, Vertex V, void (\*Visit)(Vertex) );

其中MGraph是邻接矩阵存储的图，定义如下：

typedef struct GNode *PtrToGNode;
    struct GNode{
        
        int Nv;  /* 顶点数 */
        int Ne;  /* 边数   */
        WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
    };
    typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */

函数DFS应从第V个顶点出发递归地深度优先遍历图Graph，  
遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，  
要求按序号递增的顺序。题目保证V是图中的合法顶点。

#include <stdio.h>
    
    typedef enum {
        false, true} bool;
    #define MaxVertexNum 10  /* 最大顶点数设为10 */
    #define INFINITY 65535   /* ∞设为双字节无符号整数的最大值65535*/
    typedef int Vertex;      /* 用顶点下标表示顶点,为整型 */
    typedef int WeightType;  /* 边的权值设为整型 */
    
    typedef struct GNode *PtrToGNode;
    struct GNode{
        
        int Nv;  /* 顶点数 */
        int Ne;  /* 边数   */
        WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
    };
    typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
    bool Visited[MaxVertexNum]; /* 顶点的访问标记 */
    
    MGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */
    
    void Visit( Vertex V )
    {
        
        printf(" %d", V);
    }
    
    void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
    {
        
    	//注意这里Visit函数的使用
    	Visit(V);
    	Visited[V] = true;
    	for (int i = 0; i < Graph->Nv; i++)
    	{
        
    		if (Visited[i] == false && Graph->G[V][i] != INFINITY)
    		{
        
    			//以及这里将函数作为参数传出
    			DFS(Graph, i, Visit);
    		}
    	}
    }
    
    
    int main()
    {
        
        MGraph G;
        Vertex V;
    
        G = CreateGraph();
        scanf("%d", &V);
        printf("DFS from %d:", V);
        DFS(G, V, Visit);
    
        return 0;
    }

/\* 你的代码将被嵌在这里 \*/

6-2 邻接表存储图的广度优先遍历 (20分)

试实现邻接表存储图的广度优先遍历。  
函数接口定义：

void BFS ( LGraph Graph, Vertex S, void (\*Visit)(Vertex) );

其中LGraph是邻接表存储的图，定义如下：

/* 邻接点的定义 */
    typedef struct AdjVNode *PtrToAdjVNode; 
    struct AdjVNode{
        
        Vertex AdjV;        /* 邻接点下标 */
        PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */
    };
    
    /* 顶点表头结点的定义 */
    typedef struct Vnode{
        
        PtrToAdjVNode FirstEdge; /* 边表头指针 */
    } AdjList[MaxVertexNum];     /* AdjList是邻接表类型 */
    
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{
          
        int Nv;     /* 顶点数 */
        int Ne;     /* 边数   */
        AdjList G;  /* 邻接表 */
    };
    typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */

函数BFS应从第S个顶点出发对邻接表存储的图Graph进行广度优先搜索，  
遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，  
要求按邻接表顺序访问。题目保证S是图中的合法顶点。

#include <stdio.h>
    
    typedef enum {
        false, true} bool;
    #define MaxVertexNum 10   /* 最大顶点数设为10 */
    typedef int Vertex;       /* 用顶点下标表示顶点,为整型 */
    
    /* 邻接点的定义 */
    typedef struct AdjVNode *PtrToAdjVNode; 
    struct AdjVNode{
        
        Vertex AdjV;        /* 邻接点下标 */
        PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */
    };
    
    /* 顶点表头结点的定义 */
    typedef struct Vnode{
        
        PtrToAdjVNode FirstEdge; /* 边表头指针 */
    } AdjList[MaxVertexNum];     /* AdjList是邻接表类型 */
    
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{
          
        int Nv;     /* 顶点数 */
        int Ne;     /* 边数   */
        AdjList G;  /* 邻接表 */
    };
    typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */
    
    bool Visited[MaxVertexNum]; /* 顶点的访问标记 */
    
    LGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */
    
    void Visit( Vertex V )
    {
        
        printf(" %d", V);
    }
    
    void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) )
    {
        
    	int queue[1010];
    	int st = 0, ed = 0;
    	Visit(S);
    	Visited[S] = true;
    	queue[ed++] = S;
    	PtrToAdjVNode p = NULL;
    	while (st != ed)
    	{
        
    		p = Graph->G[queue[st++]].FirstEdge;
    		while (p)
    		{
        
    			Vertex pos = p->AdjV;
    			if (Visited[pos] == false)
    			{
        
    				Visit(pos);
    				Visited[pos] = true;
    				queue[ed++] = pos;
    			}
    			p = p->Next;
    		}
    	}
    	
    }
    
    int main()
    {
        
        LGraph G;
        Vertex S;
    
        G = CreateGraph();
        scanf("%d", &S);
        printf("BFS from %d:", S);
        BFS(G, S, Visit);
    
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */

7-3 畅通工程之最低成本建设问题 (30分)

某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了有可能建设成快速路的若干条道路的成本，求畅通工程需要的最低成本。  
输入格式:

输入的第一行给出城镇数目N (1<N≤1000)和候选道路数目M≤3N；随后的M行，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号（从1编号到N）以及该道路改建的预算成本。  
输出格式:

输出畅通工程需要的最低成本。如果输入数据不足以保证畅通，则输出“Impossible”。

输入样例1:

6 15  
1 2 5  
1 3 3  
1 4 7  
1 5 4  
1 6 2  
2 3 4  
2 4 6  
2 5 2  
2 6 6  
3 4 6  
3 5 1  
3 6 1  
4 5 10  
4 6 8  
5 6 3

输出样例1:

输入样例2:

5 4  
1 2 1  
2 3 2  
3 1 3  
4 5 4

输出样例2:

Impossible

//代码是错的,我也不想写了

#include <iostream>
    #include <cstdlib>
    
    using namespace std;
    const int MVNUM = 1e3 + 5;
    const int INF = 65535;
    typedef int cost;
    typedef struct Graph
    {
        
    	int vexnum, arcnum;
    	cost arcs[MVNUM][MVNUM];
    }Graph;
    
    struct 
    {
        
    	int adjvex;
    	int lowcost;
    }closedge[MVNUM];
    
    void CreateGraph(Graph &G)
    {
        
    	int st, ed, cost;
    	cin >> G.vexnum >> G.arcnum;
    	for (int i = 0; i < G.arcnum; i++)
    	{
        
    		cin >> st >> ed >> cost;
    		G.arcs[st][ed] = cost;
    	}
    }
    
    void GetMinVex(int vexnum, int &min_vex)
    {
        
    	int min_cost = INF;
    	for (int i = 1; i <= vexnum; i++)
    	{
        
    		if (closedge[i].lowcost != 0 && closedge[i].lowcost < min_cost)
    		{
        
    			min_vex = i;
    			min_cost = closedge[i].lowcost;
    		}
    	}
    }
    void MiniSpan_Prim(Graph G, int u)
    {
        
    	closedge[u].lowcost = 0;
    	for (int i = 1; i <= G.vexnum; i++)
    	{
        
    		if (i != u && G.arcs[u][i] != INF)
    		{
        
    			closedge[i].adjvex = u;
    			closedge[i].lowcost = G.arcs[u][i];
    		}
    	}
    	for (int i = 1; i <= G.vexnum - 1; i++)
    	{
        
    		int min_vex;
    		GetMinVex(G.vexnum, min_vex);
    		closedge[min_vex].lowcost = 0;
    		for (int i = 1; i <= G.vexnum; i++)
    		{
        
    			if (closedge[i].lowcost != 0 && G.arcs[min_vex][i] < closedge[i].lowcost)
    			{
        
    				closedge[i].adjvex = min_vex;
    				closedge[i].lowcost = G.arcs[min_vex][i];
    			}
    		}
    	}
    }
    int main()
    {
        
    	Graph G;
    	CreateGraph(G);
    	MiniSpan_Prim(G, 1);
    	int flag = 1;
    	for (int i = 0; i < G.vexnum; i++)
    	{
        
    		if (closedge[i].lowcost != 0)
    		{
        
    			flag = 0;
    			break;
    		}
    	}
    	if (flag == 0)
    		cout << "impossible" <<endl;
    	else 
    	{
        
    		int sum = 0;
    		for (int i = 2; i <= G.vexnum - 1; i++)
    		{
        
    			sum += G.arcs[closedge[i].adjvex][i];
    		}
    		cout << sum << endl;
    	}
    	return 0;
    }