精华内容
下载资源
问答
  • 思路:判断一个无向图是否是一棵树,只需要判断该图是否是一个包含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 << "不是一棵树";
    
    }

     

    展开全文
  • 判断无向图是否是一棵树

    万次阅读 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);
        }
    }


    展开全文
  • 11——判断图中是否为一棵树

    千次阅读 2019-06-29 20:46:30
    编写算法,判断一个无向图是否是一颗树。 【分析】 一个无向图G是一棵树的条件为:G必须是无回路的连通图或n-1条边的连通图,这里我们采用后者作为判断条件。例如下图所示: 上面的无向图就是一棵树,它有6个...

    编写算法,判断一个无向图是否是一颗树。

    【分析】
    一个无向图G是一棵树的条件为:G必须是无回路的连通图或n-1条边的连通图,这里我们采用后者作为判断条件。例如下图所示:

    上面的无向图就是一棵树,它有6个顶点,5条边。

    code:

    #include<stdlib.h>
    #include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    #include<iostream>
    using namespace std;
    /*图的邻接表类型定义*/
    typedef char VertexType[4];
    typedef char InfoPtr;
    typedef int VRType;
    #define MAXSIZE 100				/*最大顶点个数*/
    typedef enum { DG, DN, UG, UN }GraphKind; 	/*图的类型:有向图、有向网、无向图和无向网*/
    typedef struct ArcNode			/*边结点的类型定义*/
    {
    	int adjvex; 				/*弧指向的顶点的位置*/
    	InfoPtr *info;				/*与弧相关的信息*/
    	struct ArcNode *nextarc; 	/*指示下一个与该顶点相邻接的顶点*/
    }ArcNode;
    typedef struct VNode			/*头结点的类型定义*/
    {
    	VertexType data; 			/*用于存储顶点*/
    	ArcNode *firstarc; 			/*指示第一个与该顶点邻接的顶点*/
    }VNode, AdjList[MAXSIZE];
    typedef struct					/*图的类型定义*/
    {
    	AdjList vertex;
    	int vexnum, arcnum;			/*图的顶点数目与弧的数目*/
    	GraphKind kind; 			/*图的类型*/
    }AdjGraph;
    int LocateVertex(AdjGraph G, VertexType v);
    void CreateGraph(AdjGraph *G);
    void DisplayGraph(AdjGraph G);
    void DestroyGraph(AdjGraph *G);
    void DFS(AdjGraph *G, int v, int *vNum, int *eNum, int visited[]);
    int LocateVertex(AdjGraph G, VertexType v)
    //返回图中顶点对应的位置
    {
    	int i;
    	for (i = 0; i < G.vexnum; i++)
    		if (strcmp(G.vertex[i].data, v) == 0)
    			return i;
    	return -1;
    }
    void CreateGraph(AdjGraph *G)
    //采用邻接表存储结构创建无向图G
    {
    	int i, j, k;
    	VertexType v1, v2;		//定义两个顶点v1和v2
    	ArcNode *p;
    	cout << "请输入图的顶点数和边数: ";
    	cin >> (*G).vexnum >> (*G).arcnum;
    	cout << "请输入" << G->vexnum << "个顶点的值:" << endl;
    	for (i = 0; i < G->vexnum; i++)	//将顶点存储在头结点中
    	{
    		cin >> G->vertex[i].data;
    		G->vertex[i].firstarc = NULL;	//将相关联的顶点置为空
    	}
    	cout << "请输入弧尾 弧头:" << endl;
    	for (k = 0; k < G->arcnum; k++)	//建立边链表
    	{
    		cin >> v1 >> v2;
    		i = LocateVertex(*G, v1);/*确定v1对应的编号*/
    		j = LocateVertex(*G, v2);/*确定v2对应的编号*/
    								 //j为弧头i为弧尾创建邻接表
    		p = (ArcNode*)malloc(sizeof(ArcNode));
    		p->adjvex = j;
    		p->info = NULL;
    		p->nextarc = G->vertex[i].firstarc;
    		G->vertex[i].firstarc = p;
    		//i为弧头j为弧尾创建邻接表
    		p = (ArcNode*)malloc(sizeof(ArcNode));
    		p->adjvex = i;
    		p->info = NULL;
    		p->nextarc = G->vertex[j].firstarc;
    		G->vertex[j].firstarc = p;
    	}
    	(*G).kind = UG;
    }
    void DestroyGraph(AdjGraph *G)
    //销毁无向图G
    {
    	int i;
    	ArcNode *p, *q;
    	for (i = 0; i < (*G).vexnum; i++)	//释放图中的边表结点
    	{
    		p = G->vertex[i].firstarc;//p指向边表的第一个结点
    		if (p != NULL)			//如果边表不为空,则释放边表的结点
    		{
    			q = p->nextarc;
    			free(p);
    			p = q;
    		}
    	}
    	(*G).vexnum = 0;		//将顶点数置为0
    	(*G).arcnum = 0;		//将边的数目置为0
    }
    void DisplayGraph(AdjGraph G)
    //输出图的邻接矩阵G
    {
    	int i;
    	ArcNode *p;
    	cout << G.vexnum << "个顶点:" << endl;
    	for (i = 0; i < G.vexnum; i++)
    		cout << G.vertex[i].data << " ";
    	cout << endl << G.arcnum << "条边:" << endl;
    	for (i = 0; i < G.vexnum; i++)
    	{
    		p = G.vertex[i].firstarc;
    		while (p)
    		{
    			cout << G.vertex[i].data << "→" << G.vertex[p->adjvex].data << " ";
    			p = p->nextarc;
    		}
    		cout << endl;
    	}
    }
    int IsTree(AdjGraph *G)
    {
    	int vNum = 0, eNum = 0, i, visited[MAXSIZE];
    	for (i = 0; i < G->vexnum; i++)
    		visited[i] = 0;
    	DFS(G, 0, &vNum, &eNum, visited);
    	if (vNum == G->vexnum && eNum == 2 * (G->vexnum - 1))
    		return 1;
    	else
    		return 0;
    }
    void DFS(AdjGraph *G, int v, int *vNum, int *eNum, int visited[])
    {
    	ArcNode *p;
    	visited[v] = 1;
    	(*vNum)++;
    	p = G->vertex[v].firstarc;
    	while (p != NULL)
    	{
    		(*eNum)++;
    		if (visited[p->adjvex] == 0)
    			DFS(G, p->adjvex, vNum, eNum, visited);
    		p = p->nextarc;
    	}
    }
    void main()
    {
    	AdjGraph G;
    	cout << "采用邻接表创建无向图G:" << endl;
    	CreateGraph(&G);
    	cout << "输出无向图G的邻接表:" << endl;
    	DisplayGraph(G);
    	if (IsTree(&G))
    		cout << "无向图G是一棵树!" << endl;
    	else
    		cout << "无向图G不是一棵树!" << endl;
    	DestroyGraph(&G);
    
    	system("pause");
    }
    

    结果:

    
    采用邻接表创建无向图G:
    请输入图的顶点数和边数: 6 5
    请输入6个顶点的值:
    A B C D E F
    请输入弧尾 弧头:
    A B
    A C
    B E
    C D
    C F
    输出无向图G的邻接表:
    6个顶点:
    A B C D E F
    5条边:
    A→C A→B
    B→E B→A
    C→F C→D C→A
    D→C
    E→B
    F→C
    无向图G是一棵树!

     

    展开全文
  • 判断无向图是否是树

    2017-09-01 18:32:00
    一个无向图G是一树的条件: G必须是无回路的连通图或者是n-1条边的连通图 思路: 如果能通过一次dfs就能够访问图中所有顶点, 并且访问的边是n-1条则此图是一个棵树 void dfs(ALGraph graph, int v, bool ...

     

    一个无向图G是一颗树的条件:
    G必须是无回路的连通图或者是n-1条边的连通图

     

    思路: 如果能通过一次dfs就能够访问图中所有顶点, 并且访问的边是n-1条则此图是一个棵树

    void dfs(ALGraph graph, int v, bool visit[], int &vnum, int &arcnum)
    {
        visit[v] = true;
        vnum++;
        for(ArcNode* edge = graph.adjList[v].first; edge != NULL; edge = edge->next)
        {
            arcnum++;//所有访问过的边
            if(!visit[edge->adjvex])
            {
                dfs(graph, edge->adjvex, visit, vnum, arcnum);
            }
        }
    }
    
    /*
        一个无向图G是一颗树的条件:
        G必须是无回路的连通图或者是n-1条边的连通图
    */
    bool isTree(ALGraph graph)
    {
        bool visit[MAX_NUM];
        memset(visit, 0, sizeof(visit));
        int vnum = 0, arcnum = 0;//访问过顶点的个数,边的条数
        dfs(graph, 1, visit, vnum, arcnum);
        if(vnum == graph.vexnum && arcnum ==  2 * (graph.vexnum - 1))
            return true;
        return false;
    }

      

    参考: 王道考研数据结构复习指导

    转载于:https://www.cnblogs.com/wt20/p/7464618.html

    展开全文
  • 【练习】判断无向图是否是树

    千次阅读 2018-01-16 23:41:05
    一个无向图G是一棵树的条件是G必须是无回路的连通图或是有n-1条边的连通图,这里采用后者实现。   在深度搜索遍历的过程中,同时对遍历过的顶点和边数计数,当全部顶点都遍历过且边数为2∗(n−1)2*(n-1)时,这个...
  • 算法思想:一个无向图 G是一棵树的条件是, G必须是无回路的连通图或有 n-1条边的连通图。这里采用后者作为判断条件。对连通的判定,可用能否遍历全部顶点来实现。可以采用深度优先搜索算法在遍历图的过程中统计可能...
  • 判断是否能构成最小生成树的条件是 当前的n-1条边的权值的和是否最小生成树的权值的和(代码里的ans)。 步骤: 先进行次prim,只是为了求出MST的权值ans。 再对m条边进行深搜,当选中n-1条边时判断是否能构成...
  • 题目:试设计一个算法,判断一个无向图G是否为一棵树。若是一棵树,则返回true,否则返回false 关键字:图 ; 树的判断 思路: 判断一个图G是否为树的条件有两个: 1.G必须无回路的连通图 (无回路的判断有:DFS;...
  • 题意:判断是不是一棵树 条件:无环,一个跟节点,看别人的代码要只有一个入度为0的...无向图的话判断父节点不是一个点就好了,但是树的一个点只能赋值一次父节点,比如1 2 1 2就错了,至于入度问题~我没理解诶。。
  • ——例题1

    2019-11-20 22:13:39
    1.试设计一个算法,判断一个无向图G是否为一棵树。若是一棵树,则算法返回TRUE,否则则返回FALSE. 一个无向图G是一棵树的条件是:G必须是无回路的连通图或者是有n-1条边的连通图。这里采用后者作为判断条件。对连通...
  • 机器学习中决策一个预测模型,它表示对象属性和对象值之间一种映射,一颗决策树是一棵向无,它由若干个节点、分支、分裂谓词以及类别组成。一个节点表示对象属性的判断条件,其分支表示符合节点...
  • 用给你数据构成一个无向图,要我们判断这个图有没有回路也就是这个图是不是一棵树。或者判断这组数据构成一棵树还是一个森林n个不向交树。这就是这道题考察问题。 条件1、根据数据每两个数据表示一条边,...
  • 扩展:判断一个数值是不是2得整数次方,如果是的话,这个数二进制数中有且只有一个1,那么这个数n会有 n&(n-1) == 0。或者求两个整数m和n需要改变m二进制中多少位才能得到n,可以先做 m^n 异或运算,然后...
  • 自学考试-数据结构

    2019-09-29 10:54:39
    1.带头结点的单循环链表的头指针为head,则判断该链表是否为空的条件是head->next==head 2.不需要判断栈是否为空的 进栈 3.对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;...
  • 弥补了朴素贝叶斯算法中必须要事件独立性的缺点,利用了贝叶斯网络的DAG有向无,允许各个事件保留一定的依赖关系,网络结构中的每节点代表种属性,边代表相应的条件概率值,通过计算从而能得到精准的分类...
  • 定义一棵树的根结点所在的层次为1,其他结点所在的层次等于它的父结点所在的层次加1。树的最大层次称为树的深度。例如,在1-1中,根结点A在第1层,结点B,C在第2层,结点D,E,F在第3层。该树的深度为3。 子树 在...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    4、用邻接矩阵或邻接图实现一个向图的存储,并实现单源最短路径算法实现(这个类的一个成员函数),并能输出该图关键路径。 注:1、要用面向对象方法设计代码; 2、一个图是一个实例; 3、类...
  • 数据结构题

    2012-12-27 16:58:40
    24头指针为f,尾指针为r的循环队列判断的条件是 (r+1)%max==f 。 三、问答题 1.已知一个6行5列的稀疏矩阵中非零元的值分别为:9,41,6,8,-54,5和-8,它们在矩阵中的列号依次为:1,4,5,1,2,4和5,其行值...
  • <p><strong>unshift方法可数组开头添加一个或者多个元素。 </li><li> <p>pop() <p><strong>pop方法用于删除并返回数组最后一个元素。 </li><li> <p>shift() <p><strong>shift方法可以删除数组一个元素。 ...
  • 结构化程序设计由于采用了模块分解与功能抽象,自顶下、分而治之方法,从而有效地将一个较复杂程序系统设计任务分解成许多易于控制和处理子任务,便于开发和维护。 虽然结构化程序设计方法具有很多优点,...
  • 这估计大家第一个会考虑到问题:到底把组件库代码放在一起,还是分散在各个仓库? 调查发现 Antd 将所有组件都写入一个项目中,这样方便组件统一管理,开发时不需要在多个...

空空如也

空空如也

1 2
收藏数 24
精华内容 9
关键字:

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