精华内容
下载资源
问答
  • 2题意:给定一个连通无向图,判断这个连通无向图的最小生成树是否是唯一的 3错误反思: 4思路: 1>思路1:第一遍Prim算法求出路径最小权值和且记录路径,然后逐一试探删掉一条记录的路径之后图是否连通,若图连通...
    字节跳动校招内推码: C4BDSMC
    投递链接: https://job.toutiao.com/s/J691fRK
    内推交流QQ群:1049175720
    

    Think:
    1知识点:判断一个连通无向图的最小生成树是否是唯一的+最小生成树_Prim算法+记录路径
    2题意:给定一个连通无向图,判断这个连通无向图的最小生成树是否是唯一的
    3错误反思:
    4思路:
    1>思路1:第一遍Prim算法求出路径最小权值和且记录路径,然后逐一试探删掉一条记录的路径之后图是否连通,若图连通则判断当前状态最小生成树最小边权和是否和之前的最小权值和相等,逐一遍历完成后若无最小边权和等于第一遍Prim算法求出的最小权值和,则说明最小生成树唯一,反之则说明最小生成树不唯一
    2>思路2:通过Kruskal算法构建最小生成树,第一次构建时标记构建边,之后类似思路1逐一试探每一条边的影响,若存在次小生成树最小权值和等于最小生成树权值和则说明最小生成树不唯一,反之则说明最小生成树唯一

    vjudge题目链接

    以下为Wrong Answer代码——思路1Prim算法——暂未找到错误所在

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 114;
    
    struct Edge{
        int u, v, w;
    }link[5014];
    
    int tp, vis[N], dis[N], path[N], e[N][N];
    
    void Prim(int n);
    
    int main(){
        int T, n, m, i, u, v, w;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            memset(e, inf, sizeof(e));
            for(i = 0; i < n; i++){
                scanf("%d %d %d", &u, &v, &w);
                if(w < e[u][v])
                    e[u][v] = e[v][u] = w;
            }
            Prim(n);
        }
        return 0;
    }
    void Prim(int n){
        int i, miv, v, num, ans, sum;
        memset(vis, 0, sizeof(vis));
        for(i = 1; i <= n; i++){
            dis[i] = e[1][i];
            path[i] = 1;
        }
        vis[1] = 1, dis[1] = 0, num = 1, sum = 0;
        tp = 0;
        while(num < n){
            miv = inf;
            for(i = 1; i <= n; i++){
                if(!vis[i] && dis[i] < miv){
                    miv = dis[i], v = i;
                }
            }
            if(miv == inf){
                printf("Not Unique!\n");
                return;
            }
            vis[v] = 1, num++, sum += miv;
            link[tp].u = path[v], link[tp].v = v, link[tp].w = e[path[v]][v], tp++;
            for(i = 1; i <= n; i++){
                if(!vis[i] && e[v][i] < dis[i]){
                    dis[i] = e[v][i];
                    path[i] = v;
                }
            }
        }
        ans = sum;
        for(int k = 0; k < tp; k++){
            int x = link[k].u;
            int y = link[k].v;
            int z = link[k].w;
            e[x][y] = e[y][x] = inf;
            memset(vis, 0, sizeof(vis));
            for(i = 1; i <= n; i++)
                dis[i] = e[1][i];
            vis[1] = 1, dis[1] = 0, num = 1, sum = 0;
            while(num < n){
                miv = inf;
                for(i = 1; i <= n; i++){
                    if(!vis[i] && dis[i] < miv){
                        miv = dis[i], v = i;
                    }
                }
                if(miv == inf)
                    break;
                vis[v] = 1, num++, sum += miv;
                for(i = 1; i <= n; i++){
                    if(!vis[i] && e[v][i] < dis[i])
                        dis[i] = e[v][i];
                }
            }
            if(num == n && sum == ans){
                printf("Not Unique!\n");
                return;
            }
            e[x][y] = e[y][x] = z;
        }
        printf("%d\n", ans);
    }
    
    

    以下为Accepted代码——思路2Kruskal算法

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 114;
    
    struct Edge{
        int x, y, w;
        int flag;
        bool operator < (const Edge &b) const{
            return w < b.w;
        }
    }edge[5014];
    
    int n, f[N];
    
    void Init(int n);
    int get_f(int v);
    bool Merge(int u, int v);
    int Kruskal(int num, int m);
    
    int main(){
        int T, m, i, sum, ans, cnt;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            Init(n);
            for(i = 0; i < m; i++){
                scanf("%d %d %d", &edge[i].x, &edge[i].y, &edge[i].w);
                edge[i].flag = 0;
            }
            sort(edge, edge+m);
            cnt = 1, ans = 0;
            for(i = 0; i < m; i++){
                if(Merge(edge[i].x, edge[i].y)){
                    edge[i].flag = 1;
                    ans += edge[i].w;
                    cnt++;
                }
            }
            int flag = 0;
            for(i = 0; i < m; i++){
                if(edge[i].flag == 1){
                    sum = 0;
                    Init(n);
                    sum = Kruskal(i, m);
                    if(sum == ans){
                        flag = 1;
                        break;
                    }
                }
            }
            if(flag) printf("Not Unique!\n");
            else printf("%d\n", ans);
        }
        return 0;
    }
    void Init(int n){
        for(int i = 0; i <= n; i++)
            f[i] = i;
    }
    int get_f(int v){
        if(f[v] == v)
            return f[v];
        f[v] = get_f(f[v]);
        return f[v];
    }
    bool Merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        if(t1 == t2)
            return false;
        else {
            f[t2] = t1;
            return true;
        }
    }
    int Kruskal(int num, int m){
        int i;
        int ans = 0, cnt = 1;
        for(i = 0; i < m; i++){
            if(i != num){
                if(Merge(edge[i].x, edge[i].y)){
                    ans += edge[i].w;
                    cnt++;
                }
            }
        }
        if(cnt != n) return -1;
        else return ans;
    }
    
    

    以下为Accepted代码——思路1Prim算法——参考前辈

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 114;
    
    int Map[N][N];/*邻接矩阵存图*/
    int Max[N][N];/*记录最小生成树中i到j的最大边权*/
    bool used[N][N];/*记录当前边是否加入最小生成树*/
    int path[N];/*记录当前下标路的起点*/
    int vis[N], dis[N];
    
    void Init(int n);/*初始化*/
    void Read(int m);/*读入输入数据*/
    int Prim(int n);/*最小生成树Prim算法*/
    int smst(int n, int min_ans);/*次小生成树*/
    void solve(int n);/*判断图的最小生成树是否唯一*/
    
    int main(){
        int T, n, m;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            Init(n);
            Read(m);
            solve(n);
        }
        return 0;
    }
    void Init(int n){
        for(int i = 1; i <= n; i++){
            Map[i][i] = 0;
            for(int j = i+1; j <= n; j++){
                Map[i][j] = Map[j][i] = inf;
            }
        }
    }
    void Read(int m){
        int u, v, w;
        for(int i = 0; i < m; i++){
            scanf("%d %d %d", &u, &v, &w);
            Map[u][v] = Map[v][u] = w;
        }
    }
    int Prim(int n){
        int i, miv, v, num, sum;
        memset(vis, 0, sizeof(vis));
        memset(used, false, sizeof(used));
        memset(Max, 0, sizeof(Max));
        for(int i = 1; i <= n; i++){
            dis[i] = Map[1][i];
            path[i] = 1;
        }
        vis[1] = 1, dis[1] = 0, num = 1, sum = 0;
        while(num < n){
            miv = inf;
            for(i = 1; i <= n; i++){
                if(!vis[i] && dis[i] < miv){
                    miv = dis[i], v = i;
                }
            }
            if(miv == inf) return -1;
            vis[v] = 1, num++, sum += miv;
            used[path[v]][v] = used[v][path[v]] = true;
            for(i = 1; i <= n; i++){
                if(vis[i])
                    Max[i][v] = Max[v][i] = max(Max[i][path[v]], dis[v]);
                if(!vis[i] && Map[v][i] < dis[i]){
                    dis[i] = Map[v][i];
                    path[i] = v;
                }
            }
        }
        return sum;
    }
    void solve(int n){
        int ans = Prim(n);
        if(ans == -1){
            printf("Not Unique!\n");
            return;
        }
        if(smst(n, ans) == ans)
            printf("Not Unique!\n");
        else
            printf("%d\n", ans);
    }
    int smst(int n, int ans){
        int sum = inf;
        for(int i = 1; i <= n; i++){
            for(int j = i+1; j <= n; j++){
                if(Map[i][j] != inf && !used[i][j])
                    sum = min(sum, ans+Map[i][j]-Max[i][j]);
            }
        }
        if(sum == inf) return -1;
        return sum;
    }
    
    
    展开全文
  • 一个无向图连通分量

    千次阅读 2019-12-05 12:34:40
    (注意:判断一个无向图是否连通) 求一个无向图连通分量。 输入描述 第一行输入无向图的顶点数和边的条数,以空格隔开 第二行输入每个顶点的数据,中间没有空格 第三行输入每条边,每条边的格式为i j,中间有空格,...

    问题描述

    已知无向图的顶点为字符型,要求采用邻接矩阵表示,图中顶点序号按字符顺序排列,从键盘输入图中顶点的个数、边的条数、顶点的信息和边的组成等。(注意:判断一个无向图是否连通) 求一个无向图的连通分量。
    输入描述
    第一行输入无向图的顶点数和边的条数,以空格隔开
    第二行输入每个顶点的数据,中间没有空格
    第三行输入每条边,每条边的格式为i j,中间有空格,所有边占一行
    输出描述
    输出该无向图的连通分量,占一行
    输入样例
    5 5
    ABCDE
    0 1 0 4 1 2 2 3 3 4
    输出样例
    1

    问题分析

    首先要清楚什么是无向图,在图的结构中每两个点之间最多只有一条线,这条线即代表了由a指向b,也代表了由b指向a,连通分量的概念:在这里插入图片描述
    在上图中连通分量就是4.所以说连通分量就是在图中非连通子图的数量。

    代码

    #include<iostream>
    using namespace std;
    const int MaxSize = 20;
    struct EdgeNode						//保存边表结点其中有下一个结点的下表和指向下一个结点的指针 
    {
    	int adjvex;						//邻接点域
    	EdgeNode *next;					//下一结点 
    };
    
    struct VertexNode
    {
    	char vertex;					//保存顶点
    	EdgeNode *firstEdge;			//指针域,指向下一个结点 
    };
    
    class AlGraph
    {
    	public:
    		AlGraph();
    		~AlGraph();
    		void BFTraverse(int v);			//广度优先遍历
    		int visited[MaxSize];
    		int EdgeNum,VertexNum; 			//保存顶点和边的个数 
    	private:
    		VertexNode adjlist[MaxSize]; 
    		
    		
    };
    
    AlGraph::AlGraph()
    {	
    	int x, y;								//用来保存边
    	EdgeNode *s = NULL;
    	cin >> VertexNum >> EdgeNum;
    	
    	for(int i =0;i < VertexNum; i++)		//输入顶点 
    	{
    		cin >> 	adjlist[i].vertex;
    		adjlist[i].firstEdge = NULL;
    		visited[i] = 0;
    	}		
    	for(int j = 0; j< EdgeNum; j++)			//尾插法 
    	{
    		cin >> x >> y;
    		s = new EdgeNode;
    		s->adjvex = y;
    		s->next = adjlist[x].firstEdge;
    		adjlist[x].firstEdge = s;
    	}
    }
    
    AlGraph::~AlGraph()								//释放资源 
    {
    	EdgeNode *p = NULL, *q = NULL;
    	for(int i = 0; i < VertexNum; i++)
    	{
    		p = q = adjlist[i].firstEdge;
    		while(p != NULL)
    		{
    			p = p->next;
    			delete q;
    			q = p;
    		}
    	}
    }
    
    void AlGraph::BFTraverse(int v)
    {
    	for(int i = 0; i < VertexNum; i++)
    	{
    		visited[i] = 0;
    	}
    	EdgeNode *p = NULL;
    	char Q[MaxSize];
    	int w,j;
    	int rear,front;
    	rear = front = -1;
    	visited[v] = 1;
    	Q[++rear] = v;
    	while(rear != front)
    	{
    		w = Q[++front];
    		p = adjlist[w].firstEdge;
    		while(p != NULL)
    		{
    			j = p->adjvex;
    			
    			if(visited[j] == 0)
    			{
    				
    				visited[j] = 1;
    				Q[++rear] = j;
    			}
    			p = p->next;
    		}
    	}
    	front = rear = -1;
    	
    }
    
    int main()
    {
    	int i, count = 0;
    	int judge = 1;
    	AlGraph A;
    
    	A.BFTraverse(0);						//广度优先遍历 
    	for(i = 0; i < A.VertexNum; i++)
    	{
    		if(A.visited[i] == 0)				//遍历之后如果还存在未访问的顶点,那就是连通分量的个数 
    		{
    			judge = 0;
    			A.BFTraverse(i);
    			count++;
    		} 
    	}
    	if(judge == 1)
    	{
    		cout << 1;
    	}
    	else
    	{
    		cout << count ;
    	}
    }
    
    展开全文
  • dfs判断一个无向图是不是连通

    千次阅读 2020-01-20 10:05:17
    有n个顶点,编号为1~n,用dfs遍历一遍邻接矩阵,若遍历到的顶点个数等于n,则证明改无向图一个连通图 #include<bits/stdc++.h> using namespace std; const int maxn=1005; bool vis[maxn]; vector<int...

     有n个顶点,编号为1~n,用dfs遍历一遍邻接矩阵,若遍历到的顶点个数等于n,则证明改无向图是一个连通图

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1005;
    bool vis[maxn];
    vector<int>G[maxn];
    int n,m,k,number=0;
    void dfs(int tmp) {
    	vis[tmp]=1;
    	cnt++;
    	for(int i=0; i<G[tmp].size(); i++) {
    		if(!vis[G[tmp][i]]) {
    			dfs(G[tmp][i]);
    		}
    	}
    }
    int main(){
    	int a,b;
    	cin>>n>>m;
    	while(m--){
    		cin>>a>>b;
    		G[a].push_back(b);
    		G[b].push_back(a);
    	}
    	dfs(1);
    	if(number==n) cout<<"YES"<<endl;
    	else cout<<"NO"<<endl;
    	return 0;
    }

     

    展开全文
  • 无向图连通分支

    千次阅读 2016-07-18 02:16:38
    ACM模版无向图连通分支/* * 无向图连通分支(dfs/bfs邻接阵) * DFS / BFS / 并查集 * 返回分支数,id返回1.分支数的值 * 传入图的大小n和邻接阵mat,不相邻点边权0 */ #define MAXN 100void search(int n, int mat...

    ACM模版

    无向图连通分支

    /*
     *  无向图连通分支(dfs/bfs邻接阵)
     *  DFS / BFS / 并查集
     *  返回分支数,id返回1.分支数的值
     *  传入图的大小n和邻接阵mat,不相邻点边权0
     */
    #define MAXN 100
    
    void search(int n, int mat[][MAXN], int* dfn, int* low, int now, int& cnt, int& tag, int* id, int* st, int& sp)
    {
        int i, j;
        dfn[st[sp++]=now] = low[now] = ++cnt;
        for (i = 0; i < n; i++)
        {
            if (mat[now][i])
            {
                if (!dfn[i])
                {
                    search(n, mat, dfn, low, i, cnt, tag, id, st, sp);
                    if (low[i] < low[now])
                    {
                        low[now]=low[i];
                    }
                }
                else if (dfn[i] < dfn[now])
                {
                    for (j = 0; j < sp && st[j] != i; j++)
                    {
                        if (j < cnt && dfn[i] < low[now])
                        {
                            low[now] = dfn[i];
                        }
                    }
                }
            }
        }
        if (low[now] == dfn[now])
        {
            for (tag++; st[sp] != now; id[st[--sp]] = tag);
        }
    }
    
    int find_components(int n, int mat[][MAXN], int* id)
    {
        int ret = 0, i, cnt, sp, st[MAXN], dfn[MAXN], low[MAXN];
        for (i = 0; i < n; dfn[i++] = 0);
        for (sp = cnt = i = 0; i < n; i++)
        {
            if (!dfn[i])
            {
                search(n, mat, dfn, low, i, cnt, ret, id, st, sp);
            }
        }
        return ret;
    }
    
    展开全文
  • 无向图连通

    万次阅读 2019-03-04 13:52:55
    **一、 (Graph)**是由顶点(vertex)的有穷非空集合和顶点之间边(edge)的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是G中顶点的...
  • 判断一个无向图是否是连通

    千次阅读 2019-10-03 11:37:13
    void def2(g gra,int &vn,int &en,int v) { vis[v]=1; vn++; arcnode *p; p=gra.vex[v].first; while§ { gn++; if(vis[p->adjex] 0) { def2(gra,vn,en,p->adjex...cout“连通图”; else cout“错误”;
  • 无向图连通分支

    万次阅读 2014-06-21 23:13:31
    虽然暂时用不到,还是花时间学习了...无向图连通分支(连通子图): 判断一个无向图是否连通,如果进行dfs或者bfs之后,还有未访问到的顶点,说明不是连通图,否则连通。 求解无向图的所有连通分支: 只需要重复调
  • 图论——无向图连通

    千次阅读 2019-11-15 16:04:12
    图论——无向图连通性Abstract1. 无向图连通性定义1.1 无向图可达关系的性质2. 点集和割集2.1 点割集2.1.1 例2.2 边割集3. 连通度3.1 点连通度和边连通度例3.2 特殊图的连通度 Abstract 声明:本文只为我闲暇时候...
  • 向图的强连通分量 1.强连通 代表的是 这个连通块中的每两个点互相都是有一条路径是可以走到的 2.分量 就是子图; 从这张图上可以看出 A B C这三个点都是互相可以走到的 所以他们就是一个联通块 D E F 三个点都是...
  • python networkx 有没有函数可以实现 判断一个无向图中两个结点是否连通
  • //设计算法判断一个无向图是否连通 //不连通给出分量个数 //ADT语句 //Auther: //Data:2019/11/26 int visited[MAX-VERTEX-NUM]; //访问标志数组 int count=0; //连通分量个数 int TraverseGraph(Grap g) { ...
  • 找出一个无向图中的联通块的个数 C++版 1.题意 找出一个无向图中的联通块的个数。 2.分析 使用深搜即可 3.案例演示 代码 #include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt...
  • 有向图和无向图

    万次阅读 多人点赞 2019-04-13 18:51:19
    有向图、无向图 有向图和无向图是我们常用到的术语,本文属于简单的科普帖。 全部由无向边构成图称为无向图(Undirected Graph),全部由有向边构成图称为无向图(Directed Graph)。有向,顾名思义,有方向。本文...
  • 无向图保证连通

    千次阅读 2019-09-16 19:43:56
    无向图有8顶点,保证无论何种情况下图都是联通的,则最少的边的数目? 要保证无向图G在任何情况下都是连通的, 即任意变动图G中的边,G始终保持连通。 首先需要图G的任意7结点构成完全连通子图G1,需n(n-1)/2...
  • 无向图连通

    千次阅读 2017-04-02 21:55:05
    判断一个无向图是否为连通图。输入为无向图的邻接矩阵。 输入 输入有若干行 第一行为正整数N(0 接下来N行,每行有N个数据,每个数据以空格分隔,代表邻接矩阵。 输出 一行。连通yes, 否则no. 测试输入 ...
  • 图论算法——无向图连通分量

    万次阅读 2019-05-22 19:19:37
    引言 深度优先搜索的一个直接应用就是找出一幅的所有连通分量。
  • 图___求无向图连通分量

    千次阅读 2016-11-17 20:35:47
    :求无向图连通分量数  基于DFS,count计数。  从某顶点出发遍历图,for循环,改变起始顶点,count计数 void DFSTraverse(ALGraph G){ //深度遍历图 void DFS(ALGraph G,int i); int count=0; ...
  • 无向图连通分量

    2014-09-18 11:09:54
    无向图连通分量 、对无向图进行遍历时 ()对于连通图,仅需要从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。 (二)对于非连通图,则需从多顶点出发进行搜索,而...
  • 无向图连通分量数,及大小

    千次阅读 2018-08-26 18:40:46
    /// 这里是用 vector 存 /// vis[] 用来标记这点是否被访问过 void dfs(int p,int &sz){ for(int i = 0;i < v[p].size();i ++){ int son = v[p][i]; if(!vis[son]){ vis[son] = 1; ...
  • 连通图:如果从任意一个顶点都存在一条路径到达另一个任意顶点,就称为连通图,一个连通图由若干连通的部分组成,都称为极大连通子图。 无向图:即连接两个顶点的边是没有方向的。 无向图的数据结构: 使用...
  • 计算无向图连通子图数,使用dfs遍历,例如 Input : 5 1 2 1 3 1 4 2 5 Output: 1 Input: 5 1 3 1 4 2 5 3 4 Output: 2
  • 有向图,无向图连通图,完全图

    万次阅读 多人点赞 2014-10-11 22:00:58
    立方网笔试题,6顶点的无向图,至少有几
  • 无向图dfs求连通分量

    千次阅读 2016-07-12 18:38:01
    无向图dfs求连通分量:  1 : 类比森林,一个图也可能由多个子图构成,每个子图就是一个连通分量。  2:所以即是找到 这些子图 各自的顶点集合。  3:dfs可以遍历一个连通图。所以每次dfs都可以求得一个连通分量...
  • 所以说啊,割点和桥这概念的应该范围应该只是在无向连通图中的!这一点要十分注意! 二.怎样判定 dfn[u]定义和前面类似,但是low[u]定义为u 或者u的子树中能够通过非父子边(父子边 就是搜索树上的边)追溯到的最早...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 65,866
精华内容 26,346
关键字:

一个连通无向图