精华内容
下载资源
问答
  • 思路:判断一个无向图是否是一棵树,只需要判断该图是否是一个包含n个顶点的连通子图且边数为n-1,只要这两个条件都满足,那么就是一棵树。 因此我们可以采用深度遍历,若图连通,那么只要一次深度遍历就可以遍历出...

    思路:判断一个无向图是否是一棵树,只需要判断该图是否是一个包含n个顶点的连通子图且边数为n-1,只要这两个条件都满足,那么就是一棵树。

    因此我们可以采用深度遍历,若图连通,那么只要一次深度遍历就可以遍历出所有的顶点,于是只需要调用一次dfs,并设置两个计数器记录边和顶点的数目即可。


    编程注意事项:

    1.邻接表在存储无向图的时, 每一条边都存储了两次,所以计数器中得到的是两边的边数

    2.函数的形式参数要是引用

    void DFS_my(ALGraph &G, int v, int &count_vec, int &count_arc, vector<int> &visited) {
    	visited[v] = true;
    	count_vec++;
    	for (ArcNode* p = G.vertices[v].first; p; p = p->next) {
    		count_arc++;
    		if (!visited[p->adjvex]) DFS_my(G, p->adjvex, count_vec, count_arc, visited);
    	}
    }
    
    bool isTree(ALGraph G) {
    	vector<int> visited(G.vecnum, false);
    	int count_vec = 0;
    	int count_arc = 0;
    	DFS_my(G, 0, count_vec, count_arc,visited);
    	//因为无向图在深度遍历的时候,每条边都计算了两次
    	if (count_vec == G.vecnum&&count_arc == 2 * (G.vecnum - 1)) return true;
    	else return false;
    }
    
    
    inr main() {
    	int n, m;
    	cout << "请输入有向图顶点数和边数" << endl;
    	cin >> n >> m;
    	ALGraph G;
    	create(&G, n, m);
    	//判断无向图是否为一棵树,只要无向图的所有顶点能构成一个边为n-1的连通图即可
    	//所有顶点连通,说明只要一次深度搜索即可,用
    	if (isTree(G))cout << "是一棵树";
    	else cout << "不是一棵树";
    
    }

     

    展开全文
  • 采用深度优先搜索算法遍历途中可能访问到的顶点数和边数,如果一次遍历能访问到n顶点和n-1条边,则是一棵树。 代码如下(以5*5的矩阵为例): #include<iostream> using namespace std; int map[5][5]; int...

    算法思想:

    map必须是无回路的连通图或者是n-1条边的连通图。采用深度优先搜索算法遍历途中可能访问到的顶点个数和边数,如果一次遍历能访问到n个顶点和n-1条边,则是一棵树。

    代码如下(以5*5的矩阵为例):

    #include<iostream>
    using namespace std;
    
    int map[5][5];
    int supMap[5][5] = { 0 };//辅助矩阵
    int visited[5] = { 0 };
    
    int vNum = 0;//顶点数量
    int eNum = 0;//边数量
    
    void inData()//输入数据
    {
    	cout << "请输入一个5*5的邻接矩阵:" << endl;
    	for (int i = 0; i < 5; i++)
    	{
    		for (int j = 0; j < 5; j++)
    		{
    			cin >> map[i][j];
    		}
    	}
    }
    void otherEdge(int a,int b)
    {
    	for (int i = 0; i < 5; i++)
    	{
    		/*v的下一个点条件满足map里为1,这个点没有被操作过,且下一个点不和DFS中下一个点相同,
    		  且辅助图里的数据不为0,辅助图为0表示点v与该点没有被计算过边*/
    		if (map[a][i] == 1 && i != b && visited[i] == 0 && supMap[a][i] == 0)
    		{
    			supMap[a][i] = 1;
    			eNum++;
    		}
    	}
    }
    void DFS(int v)
    {
    	visited[v] = 1;
    	vNum++;
    	for (int w = 0; w < 5; w++)
    	{
    		if (visited[w] == 0 && map[v][w] != 0)
    		{
    			if(supMap[v][w] == 0) eNum++;//同理otherEdge函数解释
    			otherEdge(v,w);//统计v点的其他分支上的边
    			DFS(w);
    		}
    	}
    }
    int main()
    {
    	inData();
    	DFS(0);
    	eNum == (vNum - 1) ? cout << "YES" : cout << "NO";
    	return 0;
    }
    
    展开全文
  • 判断无向图是否是一棵树

    万次阅读 2015-10-26 20:43:29
    算法思想: ...采用深度优先搜索算法遍历途中可能访问到的顶点数和边数,如果一次遍历能访问到n顶点和n-1条边,则是一棵树 bool isTree(Graph &G){ for(i =0; i ; i++) visited[i] = False; int

    算法思想:

            G必须是无回路的连通图或者是n-1条边的连通图,这里采用后者作为判断条件。采用深度优先搜索算法遍历途中可能访问到的顶点个数和边数,如果一次遍历能访问到n个顶点和n-1条边,则是一棵树

    bool isTree(Graph &G){
        for(i =0; i < G.VexNum; i++)
            visited[i] = False;
        int Vnum = 0;
        int Enum = 0;
        DFS(G, 1, Vnum, Enum, visited);
        if(Vnum==G.vexnum&&Enum==2*(G.vexnum-1))
            return True;
        else
            return False;
    }
    
    void DFS(Graph &G, int v, int &Vnum, int &Enum, int visited[]){
        visited[v] = True;
        Vnum++;
        int w = FirstNeighbor(G,v);
        while(w!=-1){
            Enum++;
            if(!visited[w])
                DFS(G, w, Vnum, Enum, visited);
            w = NextNeighbor(G, v, W);
        }
    }


    展开全文
  • 一棵树就是拥有n结点,n-1条边的联通无向图 /* * @Descripttion: * @version: * @Author: Nice_try * @Date: 2020-06-03 17:06:39 * @LastEditors: Nice_try * @LastEditTime: 2020-06-03 18:03:34 */ #...

    一棵树就是拥有n个结点,n-1条边的联通无向图

    /*
     * @Descripttion: 
     * @version: 
     * @Author: Nice_try
     * @Date: 2020-06-03 17:06:39
     * @LastEditors: Nice_try
     * @LastEditTime: 2020-06-03 18:03:34
     */ 
    #include<iostream>
    #include<queue>
    using namespace std;
    
    //判断无向图是一棵树的条件是 结点数为n  具有n-1条边的连通图
    //使用邻接矩阵
    bool road[101][101];//两节点之间是否有边存在
    int n, m;//结点数   边数
    bool flag[101];//判断是否在一个连通块中
    int num;//对所遍历的连通块结点计数
    queue<int> q;
    
    void dfs(int node)
    {
        for (int i = 1; i <= n;i++)
            if(road[node][i]==1&&flag[i]==0)
                flag[i] = 1, num++, dfs(i);
    }
    
    void bfs(int st)
    {
        q.push(st);
        int cur;
        while(!q.empty())
        {
            cur = q.front();
            q.pop();
            for (int i = 1; i <= n;i++)
            {
                if(road[cur][i]&&flag[i]==0)
                {
                    flag[i] = 1;
                    num++;
                    q.push(i);
                }
            }
        }
        return;
    }
    
    int init_dfs()
    {
        for (int i = 1; i <= n; i++)
            flag[i] = 0;
        num = 0;
        cin >> n >> m;
        for (int i = 1; i <= n;i++)
            for (int j = 1; j <= n;j++)
                road[i][j] = 0;
        if (m != n - 1)
            return 0;
        int x, y;
        for (int i = 1; i <= m;i++)
            cin >> x >> y, road[x][y] = road[y][x] = 1;
    
        flag[1] = 1;
        num++;
        dfs(1);
        if (num == n)
            return 1;
        else
            return 0;
    }
    
    int init_bfs()
    {
        for (int i = 1; i <= n;i++)
            flag[i] = 0;
        cin >> n >> m;
        num = 0;
        for (int i = 1; i <= n;i++)
            for (int j = 1; j <= n;j++)
                road[i][j] = 0;
        if (m != n - 1)
            return 0;
        int x, y;
        for (int i = 1; i <= m; i++)
            cin >> x >> y, road[x][y] = road[y][x] = 1;
    
        flag[1] = 1;
        num++;
        bfs(1);
        if (num == n)
            return 1;
        else
            return 0;
    }
    
    int main()
    {
        cout << "方法一(bfs遍历):\n";
        if(init_bfs())
            cout << "给定的无向图是一棵树\n";
        else
            cout << "给定的无向图不是一棵树\n";
    
        cout << "方法二(dfs遍历):\n";
        if (init_dfs())
            cout<< "给定的无向图是一棵树\n";
        else cout << "给定的无向图不是一棵树\n";
    
        system("pause");
        return 0;
    }
    
    展开全文
  • 设计一个算法,判断一个图G是否为一棵树,如果是,返回TRUE,否则,返回FALSE。 二、美丽的星座 星座真的好美好美。特别是当人类给它们赋予含义的那一刻,更美,仿佛有了灵魂一般。  是不是很美,是不是?...
  • 算法思想:一个有n个顶点的一棵树条件是有n个顶点的连通&有n-1条边 即除了根结点其他结点都有一条边与他直接相连。 void DFS2(AGraph *G,int v,int &vn,int &en) { ArcNode *p; visit[v]=1; ...
  • 但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,...
  • 【练习】判断无向图是否是

    千次阅读 2018-01-16 23:41:05
    一个无向图G是一棵树条件是G必须是无回路的连通图或是有n-1条边的连通图,这里采用后者实现。   在深度搜索遍历的过程中,同时对遍历过的顶点和边数计数,当全部顶点都遍历过且边数为2∗(n−1)2*(n-1)时,这个...
  • 题目大意:判断一个向图是不是一棵树 判断条件环,一个根节点,(只有一个入度为0的结点,不存在入度大于1的结点) #include<iostream> #include<algorithm> #include<cst
  • 11——判断图中是否为一棵树

    千次阅读 2019-06-29 20:46:30
    一个无向图G是一棵树条件为:G必须是无回路的连通图或n-1条边的连通图,这里我们采用后者作为判断条件。例如下图所示: 上面的无向图就是一棵树,它有6个顶点,5条边。 code: #include<stdlib.h> #...
  • 判断无向图是否是

    千次阅读 2019-09-28 21:46:03
    无向图条件是有n-1条边的连通图 int visit[MAXV]; void DFS2(AdjGraph *G, int v, int &vn, int &en){ visit[v] = 1; vn++; ArcNode *p = G->adjlist[v].firstarc; while(p != NULL){ en++...
  • 判断无向图G是否是

    千次阅读 2020-08-12 10:45:12
    一个无向图是一颗条件是有n-1条边的连通图,n为图中顶点的个。边和顶点的数目是否满足条件可有图的信息直接判断,连通与否可以用遍历能否访问到所有顶点来判断。 结构体定义: #include<stdio.h> #include&...
  • 判断一个向图

    千次阅读 2012-07-14 04:24:07
    1. 有且仅有一个节点,入度为0,即为根 2. 其他节点,入度皆为1 3. 从跟开始广度搜索 所遍历的节点数 应当与有向图中的节点数相等
  • 最小生成 经典算法Kruskal算法 int cmp(const node &amp;c,const node &amp;d) { return c.z&lt;d.z; } int find(int x) //路径压缩(没有按秩合并)的并查集 { if (fa[x]!=x) fa[x]=find(fa...
  • 无向图的连通性的判断

    万次阅读 2018-09-14 23:55:46
    对于一个无向图的连通性的判断,我们可以通过读入的边对得出邻接矩阵,然后可以采用Warshall算法得到可达矩阵,那么就可以很简单的判断图的连通性,只要所有的点之间都是相互可达的,那么图就是连通的,反之则不连通...
  • 解答:我们都知道对于一个无向图而言,如果它能表示成一棵树,那么它一定没有回路,并且有|E|=|V|-1,如果在这个树上添加一条边,那么就构成了回路,如果在这个树中去掉一个边就成了森林(注意:如果只是限定|E||V|-...
  • 另外,没有一个关节点的连通称为双连通(Biconnect Graph) 二、求解算法: 先贴一张数据结构书(《数据结构c语言描述–殷人昆》,额,我好像免费帮他们打广告了)上的介绍 最底下也写了,利用DFS树判断关节点的...
  • 给定一个无向图,图可能是非连通的,如果图中存在环,就输出YES,否则就输出的直径 思路: 判断是否成环可以用并查集搞一下或者记录前驱节点dfs一下 为什么会想到这两个呢?最小生成判断两...
  • 无向图的连通分支

    万次阅读 2014-06-21 23:13:31
    虽然暂时用不到,还是花时间学习了...无向图的连通分支(连通子图): 判断一个无向图是否连通,如果进行dfs或者bfs之后,还有未访问到的顶点,说明不是连通图,否则连通。 求解无向图的所有连通分支: 只需要重复调
  • * 该类对象可以表示中的条边 * @author lhever 2017年2月19日 下午5:10:49 * @version v1.0 */ public class Edge implements Comparable { private int v; private int w; private final do
  • Prim输出无向图中所有的最小生成

    千次阅读 2017-12-21 21:36:25
    一棵最小生成中有n-1条边,所以在m条边中选n-1条边判断能否构成最小生成,如果能则直接输出。 判断是否能构成最小生成条件是 当前的n-1条边的权值的和是否是最小生成树的权值的和(代码里的ans)。 步骤: ...
  • 在无向连通中,删除一个顶点v及其相连的边后,原一个连通分量变成了两个或多个连通分量,则称顶点v为割点,同时也称关节点(Articulation Point)。 双连通的一个没有关节点的连通称为重连通...
  • 无向图最小生成(两种做法)

    千次阅读 2020-09-08 12:58:12
    若(u,v)是一条具有最小权值的边,其中u∈U,v∈V-U,则必存在一棵包含边(u,v)的最小生成。 1.prim算法 基本思想:假设G=(V,E)是连通的,TE是G上最小生成中边的集合。算法从U={u0}(u0∈V)、TE={}开始。...
  • 题目:试设计一个算法,判断一个无向图G是否为一棵树。若是一棵树,则返回true,否则返回false 关键字:图 ; 树的判断 思路: 判断一个图G是否为树的条件有两个: 1.G必须是无回路的连通图 (无回路的判断有:DFS;...
  • 无向图

    千次阅读 2014-07-02 20:44:33
    作者:disappearedgod ... 时间:2014-5-7 4.1 无向图 ...边(edge)仅仅是两顶点(vertex...为了和其他图模型相区别,我们将它称为无向图。 定义 图示由组顶点和组能够将两顶点相连接的边组成的。 就定义而
  • 搜索树:dfs这些点的时候,遍历的边必定是构成一棵树的(一个点只经过一次)。 low:追溯值。一个节点i的追溯值要么是自己的dfn,要么就是另外一个点的dfn(这个点满足:只通过一条不在搜索树上的边,可以到达...
  • 割顶和桥:对于无向图G,如果删除某个节点u后,连通分量数目增加,则称u为图的割顶;如果删除某条边后,连通分量数目增加,则称该边为图的桥。对于连通图删除割顶或桥后都会使得图不再连通以下我,我们利用dfs的性质...
  • 无向图的最大割问题(分支限界)

    千次阅读 2020-06-04 12:37:08
    给定一个无向图G=(V, E),设是G的顶点集。对任意(u, v)∈E,若u∈U,且v∈V-U,就称(u, 1)为关于顶点集U的一条割边。顶点集U的所有割边构成图G的一个割。G的最大割是指G中所含边数最多的割。 对于给定的无向图G,设计...
  • 无向图双连通分量

    千次阅读 2009-08-30 15:11:00
    对今天的学习做个总结:无向图的连通分支(连通子图): 判断一个无向图是否连通,如果进行dfs或者bfs之后,还有未访问到的顶点,说明不是连通图,否则连通。求解无向图的所有连通分支: 只需要重复调用dfs或者bfs

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,096
精华内容 6,038
关键字:

判断一个无向图是一棵树的条件