精华内容
下载资源
问答
  • 图___求无向图连通分量个数

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

    求无向图连通分量个数方法:

       基于DFS,从某一顶点出发遍历图,for循环,改变起始顶点,count计数。

    代码如下:

    void DFSTraverse(ALGraph G){										//深度遍历图
    	void DFS(ALGraph G,int i);
    	int count=0;
    	for(int i = 0; i < G.vexnum; i++)  //初始化visited[]数组,设为都未访问过
    		visited[i]=0;
    	for(int j = 0; j < G.vexnum; j++){
    		if(!visited[j]){
    			 DFS(G,j);	
    		     count++;
    		}                //未访问,则访问结点	    
    	}
    	printf("连通分量的个数:%d \n",count);					
    }//DFSTraverse
    void DFS(ALGraph G,int i)  
    {		
    	printf("%d ",i);  
        fflush(stdout);  
        visited[i]=1;  
    
    	ArcNode * p;
    	p=G.adjlist[i].firstarc;//边表头指针
       while (p!=NULL)                   //边表 
       { 
    	   if (!visited[p->adjvex])  
              DFS(G,p->adjvex);
    
    	     p=p->nextarc;  
       }//while  
    } 
    


    展开全文
  • 对于一个无向连通图,从图中某一顶点出发,...然而图的深度优先搜索(DFS)算法一般采用递归算法来实现,鉴于二叉树遍历算法可以转换为非递归算法来实现,试编写基于DFS的非递归遍历算法的无向图连通分量的识别程序。
  • 无向图连通分量 #include #include #include using namespace std; int maps[105][105]; int flag[1005]={0},n; void dfs(int x,int y) { int i; for(i=0;i;i++) { if(flag[i]==0 && maps[y][i]>0) ...

    无向图连通分量


    #include <stdio.h>
    #include <stdlib.h>
    #include <iostream>
    using namespace std;
    int maps[105][105];
    int flag[1005]={0},n;
    void dfs(int x,int y)
    {
    	int i;
    	for(i=0;i<n;i++)
    	{
    		if(flag[i]==0 && maps[y][i]>0)
    		{
    			flag[i]=1;
    			dfs(y,i);
    		}
    	}
    }
    int main()
    {
    	int i,j;
    	cin>>n;
    	for(i=0;i<n;i++)
    	{
    		for(j=0;j<n;j++)
    		{
    			cin>>maps[i][j];
    		}
    	}
    	int cnt=0;
    	for(i=0;i<n;i++)
    	{
    		if(flag[i]==0)
    		{
    			cnt++;
    			flag[i]=1;
    			dfs(0,i);
    		}
    	}
    	cout<<cnt;
    	return 0;
    }


    展开全文
  • #include #define MAX_VERTEX_NUM 50 using namespace std; typedef char VerType; typedef struct ArcNode //定义弧结点所在位置, ... cout为非连通,连通分量为"; else cout为连通通"; return 0; }
    #include<iostream>
    #define MAX_VERTEX_NUM 50
    
    using namespace std;
    
    typedef char VerType;
    
    typedef struct ArcNode                 //定义弧结点所在位置,
    {
      int adj;
      int info;
      ArcNode *next;
    }ArcNode;
    
    typedef struct VerNode          //定义顶点(顶点数据,顶点所指向第一条弧的指针)
    {
      VerType data;
      ArcNode *first;
    }VerNode;
    
    typedef struct AdjList      //图的定义
    {
      VerNode VerNodes[MAX_VERTEX_NUM]; //顶点集
      int verNum,arcNum;        //顶点数,弧数
    }AdjList;
    
    typedef struct Queue      //FIFO队列
    {
      int Item[MAX_VERTEX_NUM];
      int front,rear;
    }Queue;
    
    int visited[MAX_VERTEX_NUM];    //顶点访问标志数组
    
    //定位某一结点的位置,找不到返回0
    int LocateGraph(const AdjList *g,const char data)
    {
      for(int i=1;i<=g->verNum;i++)
      {
         if(g->VerNodes[i].data==data)
             return i;
      }
      return 0;
    }
    
    //初始化队列
    void InitQueue(Queue *Q)
    {
      for(int i=1;i<=MAX_VERTEX_NUM;i++)
      {
         Q->Item[i]=0;
      }
      Q->front=Q->rear=1;
    }
    
    
    //创建图的邻接表
    void CreateAdjList(AdjList *g)
    {
      int s,d,weigth;
      char sChar,dChar;
      ArcNode *q=NULL;
      cout<<"输入图的顶点数,弧数\n";
      cin>>g->verNum>>g->arcNum;
      cout<<"输入每个顶点的信息\n";
      //初始化顶点
      for(int i=1;i<=g->verNum;i++)
      {
         cin>>g->VerNodes[i].data;
         g->VerNodes[i].first=NULL;
      }
      //初始化弧
      for(i=1;i<=g->arcNum;i++)
      {
         cout<<"输入第"<<i<<"条弧的起始,目的,弧的权值"<<endl;
         cin>>sChar>>dChar>>weigth;
         s=LocateGraph(g,sChar);
         d=LocateGraph(g,dChar);       //定位该顶点的位置
         q=(ArcNode *)malloc(sizeof(ArcNode));
         q->adj=d;q->info=weigth;
         q->next=g->VerNodes[s].first;
         g->VerNodes[s].first=q;
      }
    }
    
    //初始化访问标志数组,0为未访问过相应的顶点i
    void InitVisited(AdjList *g)
    {
      for(int i=1;i<=g->verNum;i++)
      {
         visited[i]=0;
      }
    }
    
    //访问顶点值
    void visit(AdjList *g,int v)
    {
      cout<<g->VerNodes[v].data<<endl;
    }
    
    //广度遍历图从v顶点开始
    void BFS(AdjList *g,int v)
    {
      ArcNode *q=NULL;
      Queue *Q=(Queue *)malloc(sizeof(Queue));
      InitQueue(Q);       
      Q->Item[Q->rear]=v;visit(g,v);visited[v]=1;
      Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;
      while(Q->front!=Q->rear)                   //队列不为空
      {
         v=Q->Item[Q->front];                   //取队首元素
         Q->front=(Q->front+1)%MAX_VERTEX_NUM;
         q=g->VerNodes[v].first;
         while(q!=NULL)                         //同一层上(广度搜索的层)还有其他元素,则访问顶点,入队
         {
           if(!visited[q->adj])
          {
             visit(g,q->adj);
             visited[q->adj]=1;
             Q->Item[Q->rear]=q->adj;
             Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;
             q=q->next;
          }
       }
    }
    
    }
    
    //广度遍历图
    int BFSTransfer(AdjList *g)
    {
      int count=0;
      InitVisited(g);
      for(int i=1;i<=g->verNum;i++)
      {
         if(!visited[i])
         {
            BFS(g,i);
            count++;
         }
      }
      return count;
    }
    
    int main()
    {
      int count;
      AdjList *g=(AdjList*)malloc(sizeof(AdjList));
      CreateAdjList(g);
      if((count=BFSTransfer(g))!=1)
         cout<<"为非连通图,连通分量为"<<count<<endl;
      else
        cout<<"为连通通"<<endl;
       return 0;
    }
    展开全文
  • 题目地址:POJ 1144 求割点。判断一个点是否是割点有两种判断情况: 如果u为割点,当且仅当满足下面的1条 1、如果u为树根,那么u必须有多于1棵子树 2、如果u不为树根,那么(u,v)为树枝边,当Low[v]>=DFN[u]时...

    题目地址:POJ 1144

    求割点。判断一个点是否是割点有两种判断情况:

    如果u为割点,当且仅当满足下面的1条

    1、如果u为树根,那么u必须有多于1棵子树

    2、如果u不为树根,那么(u,v)为树枝边,当Low[v]>=DFN[u]时。

    然后根据这两句来找割点就可以了。

    代码如下:

    #include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <stdlib.h>
    #include <math.h>
    #include <ctype.h>
    #include <queue>
    #include <map>
    #include <set>
    #include <algorithm>
    
    using namespace std;
    int head[200], cnt, index1, ans;
    int vis[200], low[200], dfn[200], ge[200];
    struct node
    {
        int u, v, next;
    }edge[2000];
    void add(int u, int v)
    {
        edge[cnt].v=v;
        edge[cnt].next=head[u];
        head[u]=cnt++;
    }
    void tarjan(int u, int fa)
    {
        int son=0, i;
        low[u]=dfn[u]=++index1;
        vis[u]=1;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            son++;
            if(!vis[v])
            {
                tarjan(v,u);
                low[u]=min(low[v],low[u]);
                if(u==1&&son>1||dfn[u]<=low[v]&&u!=1)
                {
                    ge[u]++;
                }
            }
            else if(v!=fa)
                low[u]=min(low[u],dfn[v]);
        }
    }
    void init()
    {
        memset(head,-1,sizeof(head));
        cnt=0;
        index1=ans=0;
        memset(vis,0,sizeof(vis));
        memset(dfn,0,sizeof(dfn));
        memset(ge,0,sizeof(ge));
    }
    int main()
    {
        int n, i, j, u, v;
        while(scanf("%d",&n)!=EOF&&n)
        {
            init();
            while(scanf("%d",&u)!=EOF&&u)
            {
                while(getchar()!='\n')
                {
                    scanf("%d",&v);
                    add(u,v);
                    add(v,u);
                }
            }
            tarjan(1,-1);
            for(i=1;i<=n;i++)
            {
                if(ge[i])
                    ans++;
            }
            printf("%d\n",ans);
        }
        return 0;
    }
    



    展开全文
  • 不过仔细一想,那个每个割点所分成一次子不就都能找到这个割点一次吗,那么只要记录下它作为割点的次数再+1不就行了。也算是求割点的裸题吧。这个题的输出很坑。。。需要注意一下。。 代码如下: #include #...
  • 图论算法——无向图连通分量

    万次阅读 2019-05-22 19:19:37
    引言 深度优先搜索的一个直接应用就是找出一幅的所有连通分量
  • 数据结构的无向图连通分量 生成树:DFS生成树和BFS生成树以及相关算法
  • 这是一个求无向图连通分量的题目,然后看了几篇博客,才有点懂了。首先,要了解两个概念,欧拉图:是指含有欧拉回路的图,欧拉回路,是指经过每一条边一次且仅一次的的回路,如果是开路的话叫做欧拉路,含有欧拉路的...
  • 无向图连通分量

    2014-09-18 11:09:54
    无向图连通分量 一、对无向图进行遍历时 (一)对于连通图,仅需要从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。 (二)对于非连通图,则需从多个顶点出发进行搜索,而...
  • Tarjan算法求有向图连通分量 常用场景: 求顶点基:求出强连通分量后缩点,得到DAG。在入度为0的点中,每个强连通分量中任取一个点,可构成顶点基。 核心思想: 注意每个节点在一个且仅在一个强连通...
  • 给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图连通分量的数目。 示例 1: 输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]  0 3  | |  1 — 2 4  ...
  • 1.图的连通性与连通分量 无向图中若任意两个顶点都是可达的,则图是连通的 ...对于判断无向图连通性,直接用并查集(Union-and-FindSet)维护或者利用bfs、dfs即可 而有向图的连通性,根据起点选择不同结果不同,在...
  • 无向图连通分量计算

    千次阅读 2018-04-26 15:00:24
    题目:无向图连通分量计算连通分量即为连通子图的个数。用一个flag数组来存放每个点的标记0点i从0-n,每次遇到flag[]==0计数器++,每次将与点I邻接的点J进行标记,然后采用深度优先搜索的方式递归得标记与J邻接的...
  • 求一个无向图连通分量

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

    2015-05-10 14:56:02
    无向图连通分支(连通子图): 判断一个无向图是否连通,如果进行dfs或者bfs之后,还有未访问到的顶点,说明不是连通图,否则连通。 求解无向图的所有连通分支: 只需要重复调用dfs或者bfs 就可以解决:遍历顶点,...
  • 不是标题党,之前我也写...双连通分量分为点双连通(V-BCC)和边双连通(E-BCC),这是图论学习中一个很重要的知识点,也是的变形转化的一个主要方法。通过V-BCC缩点可以求割边(桥),也可以通过E-BCC缩点求割点...
  • 无向图dfs求连通分量

    千次阅读 2016-07-12 18:38:01
    无向图dfs求连通分量:  1 : 类比森林,一个图也可能由多个子图构成,每个子图就是一个连通分量。  2:所以即是找到 这些子图 各自的顶点集合。  3:dfs可以遍历一个连通图。所以每次dfs都可以求得一个连通分量...
  • 今天看理一下无向图的双连通分量,有点晕了,边连通分量跟点连通分量不用
  • 向图的强连通分量 1.强连通 代表的是 这个连通块中的每两个点互相都是有一条路径是可以走到的 2.分量 就是子图; 从这张图上可以看出 A B C这三个点都是互相可以走到的 所以他们就是一个联通块 D E F 三个点都是...
  • 无向图连通分量计算 5000(ms) 10000(kb) 2555 / 5521 假设无向图G采用邻接矩阵存储,编写一个算法求连通分量的个数。 输入 第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1),接下来是为一个n*n大小的整数...
  • 假设无向图G采用邻接矩阵存储,编写一个算法求连通分量的个数。 输入 第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1),接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,1表示不...
  • 1065: 无向图连通分量计算 题目描述 假设无向图G采用邻接矩阵存储,编写一个算法求连通分量的个数。 输入 第一行为一个整数n,表示顶点的个数(顶点编号为0到n-1),接下来是为一个n*n大小的整数矩阵,表示图的...
  • 一、无向图的割点,桥,双连通分量
  • 时间戳 dfs_clock :说白了就是记录下访问每个结点的次序。假设我们用 pre 保存,那么如果 pre[u] > pre[v], 那么就可以知道先访问的 v ,后访问的 u ...相互可达的节点称为一个连通分量; #include #include #i

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,775
精华内容 5,910
关键字:

无向图的连通分量