精华内容
下载资源
问答
  • 数据结构

    2017-08-22 18:36:52
    1 一个具有n个顶点的无向连通图,它所包含的连通分量数为( ) 由于该图本身就是连通图,所以只可能包含一个连通分量。若不连通才可能有多个连通分量 答案 1

    1 一个具有n个顶点的无向连通图,它所包含的连通分量数为(  )

    由于该图本身就是连通图,所以只可能包含一个连通分量。若不连通才可能有多个连通分量

    答案 1

    展开全文
  • 具有 n 个顶点的无向连通图至少有 n-1 条边,如果只有 n-1 条边,则不会形成环,这样的图称为“生成树”。连通图可通过遍历构造生成树,非连通图的每个连通分量可构造一棵生成树,整个非连通图构造为生成森林。 ...

    具有 n 个顶点的无向连通图至少有 n-1 条边,如果只有 n-1 条边,则不会形成环,这样的图称为“生成树”。连通图可通过遍历构造生成树,非连通图的每个连通分量可构造一棵生成树,整个非连通图构造为生成森林。

    下面程序调用算法 7.77.8,将无向图构造为生成森林,并以孩子—兄弟二叉链表存储之。

     

    typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
    typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
    
    #include<malloc.h> /* malloc()等 */
    #include<stdio.h> /* EOF(=^Z或F6),NULL */
    #include<process.h> /* exit() */
    #include<limits.h> //常量INT_MAX和INT_MIN分别表示最大、最小整数
    
    /* 函数结果状态代码 */
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW -2 
    
    
    #define MAX_NAME 2 /* 顶点字符串的最大长度+1 */
    typedef char ElemType[MAX_NAME];
    typedef ElemType TElemType;
    
    
    /* ------------------------------- 树的二叉链表(孩子-兄弟)存储表示 ----------------------------*/
    
    typedef struct CSNode
    {
    	TElemType data;
    	struct CSNode *firstchild, *nextsibling;
    }CSNode, *CSTree;
    
    /* ---------------------------------------------------------------------------------------------*/
    
    typedef int InfoType;
    typedef char VertexType[MAX_NAME];
    
    
    /* ---------------------------------    图的邻接表存储表示     --------------------------------*/
    
    #define MAX_VERTEX_NUM 20
    typedef enum { DG, DN, AG, AN }GraphKind; /* {有向图,有向网,无向图,无向网} */
    typedef struct ArcNode
    {
    	int adjvex; /* 该弧所指向的顶点的位置 */
    	struct ArcNode *nextarc; /* 指向下一条弧的指针 */
    	InfoType *info; /* 网的权值指针) */
    }ArcNode; /* 表结点 */
    typedef struct
    {
    	VertexType data; /* 顶点信息 */
    	ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */
    }VNode, AdjList[MAX_VERTEX_NUM]; /* 头结点 */
    typedef struct
    {
    	AdjList vertices;
    	int vexnum, arcnum; /* 图的当前顶点数和弧数 */
    	int kind; /* 图的种类标志 */
    }ALGraph;
    
    /* ---------------------------------------------------------------------------------------------*/
    
    
    
    
    /* -----------------------------  需要用的图的邻接表存储的基本操作 ----------------------------*/
    
    
    int LocateVex(ALGraph G, VertexType u)
    { /* 初始条件: 图G存在,u和G中顶点有相同特征 */
      /* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
    	int i;
    	for (i = 0; i < G.vexnum; ++i)
    		if (strcmp(u, G.vertices[i].data) == 0)
    			return i;
    	return -1;
    }
    
    Status CreateGraph(ALGraph *G)
    { /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */
    	int i, j, k;
    	int w; /* 权值 */
    	VertexType va, vb;
    	ArcNode *p;
    	printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
    	scanf("%d", &(*G).kind);
    	printf("请输入图的顶点数,边数: ");
    	scanf("%d,%d", &(*G).vexnum, &(*G).arcnum);
    	printf("请输入%d个顶点的值(<%d个字符):\n", (*G).vexnum, MAX_NAME);
    	for (i = 0; i < (*G).vexnum; ++i) /* 构造顶点向量 */
    	{
    		scanf("%s", (*G).vertices[i].data);
    		(*G).vertices[i].firstarc = NULL;
    	}
    	if ((*G).kind == 1 || (*G).kind == 3) /* 网 */
    		printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
    	else /* 图 */
    		printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
    	for (k = 0; k < (*G).arcnum; ++k) /* 构造表结点链表 */
    	{
    		if ((*G).kind == 1 || (*G).kind == 3) /* 网 */
    			scanf("%d%s%s", &w, va, vb);
    		else /* 图 */
    			scanf("%s%s", va, vb);
    		i = LocateVex(*G, va); /* 弧尾 */
    		j = LocateVex(*G, vb); /* 弧头 */
    		p = (ArcNode*)malloc(sizeof(ArcNode));
    		p->adjvex = j;
    		if ((*G).kind == 1 || (*G).kind == 3) /* 网 */
    		{
    			p->info = (int *)malloc(sizeof(int));
    			*(p->info) = w;
    		}
    		else
    			p->info = NULL; /* 图 */
    		p->nextarc = (*G).vertices[i].firstarc; /* 插在表头 */
    		(*G).vertices[i].firstarc = p;
    		if ((*G).kind >= 2) /* 无向图或网,产生第二个表结点 */
    		{
    			p = (ArcNode*)malloc(sizeof(ArcNode));
    			p->adjvex = i;
    			if ((*G).kind == 3) /* 无向网 */
    			{
    				p->info = (int*)malloc(sizeof(int));
    				*(p->info) = w;
    			}
    			else
    				p->info = NULL; /* 无向图 */
    			p->nextarc = (*G).vertices[j].firstarc; /* 插在表头 */
    			(*G).vertices[j].firstarc = p;
    		}
    	}
    	return OK;
    }
    
    VertexType* GetVex(ALGraph G, int v)
    { /* 初始条件: 图G存在,v是G中某个顶点的序号。操作结果: 返回v的值 */
    	if (v >= G.vexnum || v < 0)
    		exit(ERROR);
    	return &G.vertices[v].data;
    }
    
    int FirstAdjVex(ALGraph G, VertexType v)
    { /* 初始条件: 图G存在,v是G中某个顶点 */
      /* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
    	ArcNode *p;
    	int v1;
    	v1 = LocateVex(G, v); /* v1为顶点v在图G中的序号 */
    	p = G.vertices[v1].firstarc;
    	if (p)
    		return p->adjvex;
    	else
    		return -1;
    }
    
    int NextAdjVex(ALGraph G, VertexType v, VertexType w)
    { /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
      /* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号。 */
      /*           若w是v的最后一个邻接点,则返回-1 */
    	ArcNode *p;
    	int v1, w1;
    	v1 = LocateVex(G, v); /* v1为顶点v在图G中的序号 */
    	w1 = LocateVex(G, w); /* w1为顶点w在图G中的序号 */
    	p = G.vertices[v1].firstarc;
    	while (p&&p->adjvex != w1) /* 指针p不空且所指表结点不是w */
    		p = p->nextarc;
    	if (!p || !p->nextarc) /* 没找到w或w是最后一个邻接点 */
    		return -1;
    	else /* p->adjvex==w */
    		return p->nextarc->adjvex; /* 返回v的(相对于w的)下一个邻接顶点的序号 */
    }
    
    
    
    Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
    void(*VisitFunc)(char* v); /* 函数变量(全局量) */
    
    
    typedef int QElemType; /* 队列类型 */
    
    
    /* ------------------------------- 单链队列--队列的链式存储结构 -------------------------------*/
    
    typedef struct QNode
    {
    	QElemType data;
    	struct QNode *next;
    }QNode, *QueuePtr;
    
    typedef struct
    {
    	QueuePtr front, rear; /* 队头、队尾指针 */
    }LinkQueue;
    
    /* ---------------------------------------------------------------------------------------------*/
    
    
    /* ---------------------------------  需要用到的链队列的基本操作   --------------------------------*/
    
    
    Status InitQueue(LinkQueue *Q)
    { /* 构造一个空队列Q */
    	(*Q).front = (*Q).rear = (QueuePtr)malloc(sizeof(QNode));
    	if (!(*Q).front)
    		exit(OVERFLOW);
    	(*Q).front->next = NULL;
    	return OK;
    }
    
    Status QueueEmpty(LinkQueue Q)
    { /* 若Q为空队列,则返回TRUE,否则返回FALSE */
    	if (Q.front == Q.rear)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    Status EnQueue(LinkQueue *Q, QElemType e)
    { /* 插入元素e为Q的新的队尾元素 */
    	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    	if (!p) /* 存储分配失败 */
    		exit(OVERFLOW);
    	p->data = e;
    	p->next = NULL;
    	(*Q).rear->next = p;
    	(*Q).rear = p;
    	return OK;
    }
    
    Status DeQueue(LinkQueue *Q, QElemType *e)
    { /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
    	QueuePtr p;
    	if ((*Q).front == (*Q).rear)
    		return ERROR;
    	p = (*Q).front->next;
    	*e = p->data;
    	(*Q).front->next = p->next;
    	if ((*Q).rear == p)
    		(*Q).rear = (*Q).front;
    	free(p);
    	return OK;
    }
    
    
    /* ---------------------------------------------------------------------------------------------*/
    
    
    void Display(ALGraph G)
    { /* 输出图的邻接矩阵G */
    	int i;
    	ArcNode *p;
    	switch (G.kind)
    	{
    	case DG: printf("有向图\n");
    		break;
    	case DN: printf("有向网\n");
    		break;
    	case AG: printf("无向图\n");
    		break;
    	case AN: printf("无向网\n");
    	}
    	printf("%d个顶点:\n", G.vexnum);
    	for (i = 0; i < G.vexnum; ++i)
    		printf("%s ", G.vertices[i].data);
    	printf("\n%d条弧(边):\n", G.arcnum);
    	for (i = 0; i < G.vexnum; i++)
    	{
    		p = G.vertices[i].firstarc;
    		while (p)
    		{
    			if (G.kind <= 1) /* 有向 */
    			{
    				printf("%s→%s ", G.vertices[i].data, G.vertices[p->adjvex].data);
    				if (G.kind == DN) /* 网 */
    					printf(":%d ", *(p->info));
    			}
    			else /* 无向(避免输出两次) */
    			{
    				if (i < p->adjvex)
    				{
    					printf("%s-%s ", G.vertices[i].data, G.vertices[p->adjvex].data);
    					if (G.kind == AN) /* 网 */
    						printf(":%d ", *(p->info));
    				}
    			}
    			p = p->nextarc;
    		}
    		printf("\n");
    	}
    }
    
    
    
    /* --------------------------------------------------------------------------------------------------*/
    
    
    
    /* 调用算法7.7、7.8 */
    
    
    void DFSTree(ALGraph G, int v, CSTree *T)
    { /* 从第v个顶点出发深度优先遍历图G,建立以T为根的生成树。算法7.8 */
    	Boolean first = TRUE;
    	int w;
    	CSTree p, q = NULL;
    	VertexType v1, w1;
    	visited[v] = TRUE;
    	strcpy(v1, *GetVex(G, v));
    	for (w = FirstAdjVex(G, v1); w >= 0; w = NextAdjVex(G, v1, strcpy(w1, *GetVex(G, w)))) /* w依次为v的邻接顶点 */
    		if (!visited[w]) /* w顶点不曾被访问 */
    		{
    			p = (CSTree)malloc(sizeof(CSNode)); /* 分配孩子结点 */
    			strcpy(p->data, *GetVex(G, w));
    			p->firstchild = NULL;
    			p->nextsibling = NULL;
    			if (first)
    			{ /* w是v的第一个未被访问的邻接顶点 */
    				(*T)->firstchild = p;
    				first = FALSE; /* 是根的第一个孩子结点 */
    			}
    			else /* w是v的其它未被访问的邻接顶点 */
    				q->nextsibling = p; /* 是上一邻接顶点的兄弟姐妹结点 */
    			q = p;
    			DFSTree(G, w, &q); /* 从第w个顶点出发深度优先遍历图G,建立子生成树q */
    		}
    }
    
    void DFSForest(ALGraph G, CSTree *T)
    { /* 建立无向图G的深度优先生成森林的(最左)孩子(右)兄弟链表T。算法7.7 */
    	CSTree p, q = NULL;
    	int v;
    	*T = NULL;
    	for (v = 0; v < G.vexnum; ++v)
    		visited[v] = FALSE; /* 赋初值 */
    	for (v = 0; v < G.vexnum; ++v) /* 从第0个顶点找起 */
    		if (!visited[v])
    		{ /* 第v顶点为新的生成树的根结点 */
    			p = (CSTree)malloc(sizeof(CSNode)); /* 分配根结点 */
    			strcpy(p->data, *GetVex(G, v));
    			p->firstchild = NULL;
    			p->nextsibling = NULL;
    			if (!*T) /* 是第一棵生成树的根(T的根) */
    				*T = p;
    			else /* 是其它生成树的根(前一棵的根的"兄弟") */
    				q->nextsibling = p;
    			q = p; /* q指示当前生成树的根 */
    			DFSTree(G, v, &p); /* 建立以p为根的生成树 */
    		}
    }
    
    void PreOrderTraverse(CSTree T, void(*Visit)(TElemType))
    { /* 先根遍历孩子-兄弟二叉链表结构的树T */
    	if (T)
    	{
    		Visit(T->data); /* 先访问根结点 */
    		PreOrderTraverse(T->firstchild, Visit); /* 再先根遍历长子子树 */
    		PreOrderTraverse(T->nextsibling, Visit); /* 最后先根遍历下一个兄弟子树 */
    	}
    }
    
    void print(char *i)
    {
    	printf("%s ", i);
    }
    
    void main()
    {
    	ALGraph g;
    	CSTree t;
    	printf("请选择无向图\n");
    	CreateGraph(&g);
    	Display(g);
    	DFSForest(g, &t);
    	printf("先根遍历生成森林:\n");
    	PreOrderTraverse(t, print);
    	printf("\n");
    }

    运行结果:

    非连通无向图:
     
     
    根据输入产生的邻接表:
     
     
     
    生成森林:
     
     
     
    生成森林以孩子—兄弟二叉链表存储的结构:
     
    展开全文
  • 具有n 个顶点的无向连通图至少有n-1 条边,如果只有n-1 条边,则不会形成环,这 样的图称为“生成树”。连通图可通过遍历构造生成树,非连通图的每个连通分量可构造 一棵生成树,整个非连通图构造为生成森林。algo...
    具有n 个顶点的无向连通图至少有n-1 条边,如果只有n-1 条边,则不会形成环,这
    样的图称为“生成树”。连通图可通过遍历构造生成树,非连通图的每个连通分量可构造
    一棵生成树,整个非连通图构造为生成森林。algo7-1.cpp 调用算法7.7、7.8,将无向图

    构造为生成森林,并以孩子—兄弟二叉链表存储之。

    // algo7-1.cpp 调用算法7.7、7.8
    #include"c1.h"
    #define MAX_NAME 2 // 顶点字符串的最大长度+1
    typedef char VertexType[MAX_NAME];
    typedef VertexType TElemType; // 定义树的元素类型为图的顶点类型
    #include"c6-5.h" // 孩子—兄弟二叉链表存储结构
    #include"func6-2.cpp" // 孩子—兄弟二叉链表存储结构的先根遍历操作
    typedef int InfoType; // 权值类型
    #include"c7-21.h" // bo7-2.cpp采用的存储类型
    #include"bo7-2.cpp" // 邻接表的基本操作
    void DFSTree(ALGraph G,int v,CSTree &T)
    { // 从第v个顶点出发深度优先遍历图G,建立以T为根的生成树。算法7.8
    	Boolean first=TRUE;
    	int w;
    	CSTree p,q;
    	visited[v]=TRUE;
    	for(w=FirstAdjVex(G,G.vertices[v].data);w>=0;w=NextAdjVex(G,G.vertices[v].data,
    		G.vertices[w].data)) // w依次为v的邻接顶点
    		if(!visited[w]) // w顶点不曾被访问
    		{
    			p=(CSTree)malloc(sizeof(CSNode)); // 分配孩子结点
    			strcpy(p->data,G.vertices[w].data);
    			p->firstchild=NULL;
    			p->nextsibling=NULL;
    			if(first)
    			{ // w是v的第一个未被访问的邻接顶点
    				T->firstchild=p;
    				first=FALSE; // 是根的第一个孩子结点
    			}
    			else // w是v的其它未被访问的邻接顶点
    				q->nextsibling=p; // 是上一邻接顶点的兄弟姐妹结点(第1次不通过此处,以后q已赋值)
    			q=p;
    			DFSTree(G,w,q); // 从第w个顶点出发深度优先遍历图G,建立子生成树q
    		}
    }
    void DFSForest(ALGraph G,CSTree &T)
    { // 建立无向图G的深度优先生成森林的(最左)孩子(右)兄弟链表T。算法7.7
    	CSTree p,q;
    	int v;
    	T=NULL;
    	for(v=0;v<G.vexnum;++v)
    		visited[v]=FALSE; // 赋初值,visited[]在bo7-2.cpp中定义
    	for(v=0;v<G.vexnum;++v) // 从第0个顶点找起
    		if(!visited[v]) // 第v个顶点不曾被访问
    		{ // 第v顶点为新的生成树的根结点
    			p=(CSTree)malloc(sizeof(CSNode)); // 分配根结点
    			strcpy(p->data,G.vertices[v].data);
    			p->firstchild=NULL;
    			p->nextsibling=NULL;
    			if(!T) // 是第一棵生成树的根(T的根)
    				T=p;
    			else // 是其它生成树的根(前一棵的根的“兄弟”)
    				q->nextsibling=p; // 第1次不通过此处,以后q已赋值
    			q=p; // q指示当前生成树的根
    			DFSTree(G,v,p); // 建立以p为根的生成树
    		}
    }
    void print(char *i)
    {
    	printf("%s ",i);
    }
    void main()
    {
    	ALGraph g;
    	CSTree t;
    	printf("请选择无向图\n");
    	CreateGraph(g); // 构造无向图g
    	Display(g); // 输出无向图g
    	DFSForest(g,t); // 建立无向图g的深度优先生成森林的孩子—兄弟链表t
    	printf("先序遍历生成森林:\n");
    	PreOrderTraverse(t,print); // 先序遍历生成森林的孩子—兄弟链表t
    	printf("\n");
    }
    

    代码的运行结果:

    请选择无向图
    请输入G的类型(有向图:0,有向网:1,无向图:2,无向网:3): 2
    请输入G的顶点数,边数: 13,13(见图751)
    请输入13个顶点的值(<2个字符):
    A B C D E F G H I J K L M
    请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):
    A B
    A C
    A F
    A L
    B M
    D E

    G H
    G I
    G K
    H K
    J L
    J M
    L M
    无向图(见图752)
    13个顶点:
    A B C D E F G H I J K L M
    13条弧(边):
    A-L A-F A-C A-B
    B-M
    D-E
    G-K G-I G-H
    H-K
    J-M J-L
    L-M
    先序遍历生成森林:(见图753)
    A L M J B F C D E G K H I


    以上对图的输入产生的邻接表如图752 所示,仍略去网的权值指针域,并用顶点名
    称代替顶点位置。调用算法7.7 产生的生成森林如图753 所示,此生成森林以孩子—兄
    弟二叉链表存储的结构如图754 所示。


    展开全文
  • 具有n 个顶点的无向连通图至少有n-1 条边,如果只有n-1 条边,则不会形成环,这 样的图称为“生成树”。连通图可通过遍历构造生成树,非连通图的每个连通分量可构造 一棵生成树,整个非连通图构造为生成森林。algo...
    具有n 个顶点的无向连通图至少有n-1 条边,如果只有n-1 条边,则不会形成环,这
    样的图称为“生成树”。连通图可通过遍历构造生成树,非连通图的每个连通分量可构造
    一棵生成树,整个非连通图构造为生成森林。algo7-1.cpp 调用算法7.7、7.8,将无向图

    构造为生成森林,并以孩子—兄弟二叉链表存储之。

    // algo7-1.cpp 调用算法7.7、7.8
    #include"c1.h"
    #define MAX_NAME 2 // 顶点字符串的最大长度+1
    typedef char VertexType[MAX_NAME];
    typedef VertexType TElemType; // 定义树的元素类型为图的顶点类型
    #include"c6-5.h" // 孩子—兄弟二叉链表存储结构
    #include"func6-2.cpp" // 孩子—兄弟二叉链表存储结构的先根遍历操作
    typedef int InfoType; // 权值类型
    #include"c7-21.h" // bo7-2.cpp采用的存储类型
    #include"bo7-2.cpp" // 邻接表的基本操作
    void DFSTree(ALGraph G,int v,CSTree &T)
    { // 从第v个顶点出发深度优先遍历图G,建立以T为根的生成树。算法7.8
    	Boolean first=TRUE;
    	int w;
    	CSTree p,q;
    	visited[v]=TRUE;
    	for(w=FirstAdjVex(G,G.vertices[v].data);w>=0;w=NextAdjVex(G,G.vertices[v].data,
    		G.vertices[w].data)) // w依次为v的邻接顶点
    		if(!visited[w]) // w顶点不曾被访问
    		{
    			p=(CSTree)malloc(sizeof(CSNode)); // 分配孩子结点
    			strcpy(p->data,G.vertices[w].data);
    			p->firstchild=NULL;
    			p->nextsibling=NULL;
    			if(first)
    			{ // w是v的第一个未被访问的邻接顶点
    				T->firstchild=p;
    				first=FALSE; // 是根的第一个孩子结点
    			}
    			else // w是v的其它未被访问的邻接顶点
    				q->nextsibling=p; // 是上一邻接顶点的兄弟姐妹结点(第1次不通过此处,以后q已赋值)
    			q=p;
    			DFSTree(G,w,q); // 从第w个顶点出发深度优先遍历图G,建立子生成树q
    		}
    }
    void DFSForest(ALGraph G,CSTree &T)
    { // 建立无向图G的深度优先生成森林的(最左)孩子(右)兄弟链表T。算法7.7
    	CSTree p,q;
    	int v;
    	T=NULL;
    	for(v=0;v<G.vexnum;++v)
    		visited[v]=FALSE; // 赋初值,visited[]在bo7-2.cpp中定义
    	for(v=0;v<G.vexnum;++v) // 从第0个顶点找起
    		if(!visited[v]) // 第v个顶点不曾被访问
    		{ // 第v顶点为新的生成树的根结点
    			p=(CSTree)malloc(sizeof(CSNode)); // 分配根结点
    			strcpy(p->data,G.vertices[v].data);
    			p->firstchild=NULL;
    			p->nextsibling=NULL;
    			if(!T) // 是第一棵生成树的根(T的根)
    				T=p;
    			else // 是其它生成树的根(前一棵的根的“兄弟”)
    				q->nextsibling=p; // 第1次不通过此处,以后q已赋值
    			q=p; // q指示当前生成树的根
    			DFSTree(G,v,p); // 建立以p为根的生成树
    		}
    }
    void print(char *i)
    {
    	printf("%s ",i);
    }
    void main()
    {
    	ALGraph g;
    	CSTree t;
    	printf("请选择无向图\n");
    	CreateGraph(g); // 构造无向图g
    	Display(g); // 输出无向图g
    	DFSForest(g,t); // 建立无向图g的深度优先生成森林的孩子—兄弟链表t
    	printf("先序遍历生成森林:\n");
    	PreOrderTraverse(t,print); // 先序遍历生成森林的孩子—兄弟链表t
    	printf("\n");
    }
    

    代码的运行结果:

    请选择无向图
    请输入G的类型(有向图:0,有向网:1,无向图:2,无向网:3): 2
    请输入G的顶点数,边数: 13,13(见图751)
    请输入13个顶点的值(<2个字符):
    A B C D E F G H I J K L M
    请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):
    A B
    A C
    A F
    A L
    B M
    D E

    G H
    G I
    G K
    H K
    J L
    J M
    L M
    无向图(见图752)
    13个顶点:
    A B C D E F G H I J K L M
    13条弧(边):
    A-L A-F A-C A-B
    B-M
    D-E
    G-K G-I G-H
    H-K
    J-M J-L
    L-M
    先序遍历生成森林:(见图753)
    A L M J B F C D E G K H I


    以上对图的输入产生的邻接表如图752 所示,仍略去网的权值指针域,并用顶点名
    称代替顶点位置。调用算法7.7 产生的生成森林如图753 所示,此生成森林以孩子—兄
    弟二叉链表存储的结构如图754 所示。


    转载于:https://www.cnblogs.com/KongkOngL/p/4074455.html

    展开全文
  • 定理1:在一个具有n个顶点的无向连通图G中,如果任意两个顶点的度数之和大于n,则G具有Hamilton回路。此条件为充分条件 定理2:设图G = <V,E>,是Hamilton图,则对于v的任意一个非空子集S,若以|S|表示S中...
  • 2.对于一个具有n个顶点的无向连通图,它包含的连通分量的个数为( 1 )。 在无向图G中,若从顶点Vi到顶点Vj有路径(当然从Vj到Vi也一定有路径),则称 Vi和Vj 是联通的。若V(G)中任意两个不同的顶点Vi 和Vj都联通...
  • 图的连通度边连通度总结

    千次阅读 2015-08-12 21:57:51
    点连通度定义:一个具有N个图G中,在去掉任意k-1个顶点后(1),所得子图仍然连通,去掉K个顶点后不连通,则称G是K连通图,K称作图G连通度,记作K(G)。 独立轨:A,B是图G(有向无向均可)个顶点,...
  • 点连通度:一个具有N个点的图G中,在去掉任意k-1个顶点后(1 独立轨:A,B是图G(有向无向均可)的两个顶点,我们称为从A到B的两两无公共内顶点的轨为独立轨,其最大条数记作P(A,B)。 设A和B是无向连通图G两个不...
  • 算法与数据结构之

    2020-10-21 23:33:04
    5. 在n个顶点的无向连通图的连通分量个数为?个。 6. 在n个顶点的非空无向图中,最多有?个连通分量。 7. n个顶点的连通无向图,其边的条数至少为?。 8. 如果具有n个顶点的图是一个环,则它有?棵生成树。 9. N...
  • 问题引入:给定无向连通图G=(V,E)和正整数m,寻找最小整数m,用m种颜色对G中的顶点着色,使得任意两相邻顶点着色不同。由于用m种颜色为无向图G=(V,E)着色,其中,V 的顶点个数为n,可以用一个n元组C=(c​1​​,c...
  • 图的连通度和边连通

    千次阅读 2014-10-19 22:12:18
    连通定义:一个具有N个的图G中,在去掉任意k-1个顶点后(1 独立轨:A,B是G(有向无向均可)个顶点,我们称为从A到B两两无公共内顶轨为独立轨,其最大条数记作p(A,B)。 在上中有一个...
  • 数据结构习题 第七章 图 选择题 1一个有n个顶点的无向图最多有 C 条边 An Bn(n-1) Cn(n-1)/2 D2n 2具有4个顶点的无向完全图有 A 条边 A6 B12 C16 D20 3具有6个顶点的无向图至少有 A 条边才能保证是一个连通图 ...
  • 有向完全:若有向n个顶点,且具有n(n-1)个边 无向完全:若无向n个顶点,且具有(n(n-1)/2) 简单路径:序列中顶点不重复出现路径成为简单路径  回路:若一条路径中第一个顶点和最后一个顶点相同,则这...
  • 1

    2019-12-01 13:27:29
    的组成部分:点和线。故的定义是点的集合与边的集合。 需要注意的是:的顶点不能为0 !...(2)要连通具有n个顶点的有向,至少需要( )条边。 n (3)若无向G=(V,E)中含7个顶点,则保证G在...
  • 问题引入:给定无向连通图G=(V,E)和正整数m,寻找最小整数m,用m种颜色对G中的顶点着色,使得任意两相邻顶点着色不同。由于用m种颜色为无向图G=(V,E)着色,其中,V 的顶点个数为n,可以用一个n元组C=(c​1​​,c...
  • 1.什么是图的搜索?  指从一个指定顶点可以到达哪些顶点 2.无向完全图和有向完全图 ... 具有6个顶点的无向图,当有多少条边的时候,能确保是一个连通图?  6个顶点组成的完全图,需要6(6-1)/2=10条,则需要...
  • 对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为(n),邻接表中的全部结点总数是(2e)。 用邻接表表示有向图: 顶点的出度 = 邻接表中对应链表的长度 任何一个无向连通图有一棵或多棵...
  • 1、具有n个顶点的无向完全图的弧数为( )。 A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、n/2 正确答案: A 2、下列有关图遍历的说法中不正确的是( )。 A、连通图的深度优先搜索是一个递归过程 B、图的广度优先搜索...
  • 第七章 练习题(一)

    千次阅读 2013-04-25 17:35:22
    原文地址:第七章 练习题(一)作者:tanzj1、有n个顶点的无向完全具有(  )条边. A、n(n+1)/2   B、n-1  C、n  D、n(n-1) 2、有向中一个顶点i的出度等于其邻接...4、一个具有n个顶点的连通有向至多
  •  一个具有n个顶点的连通图的生成树是原图的极小连通子图,它包含原图中所有的n个顶点,并且保持连通图的最小的边,简单的说就是有n个顶点,并且任何一对顶点都是可以到达的。并且边数是最少的。对于无向图来说,...
  • 给定无向连通图G和m种不同颜色,用这些颜色为图G各顶点着色,每个顶点着一种颜色,如果有一种着色方案使中种每条边个顶点着不同颜色,则称图是m可着色,求出所有不同着色方案。 数据结构设计: 1.用二...
  • 点连通度定义:一个具有N个图G中,在去掉任意k-1个顶点后(1<=k<=N),所得子图仍然连通,去掉K个顶点后不连通,则称G是K连通图,K称作图G连通度,记作K(G)。 独立轨:A,B是图G(有向无向均可)...
  • 2019-11-26 18:47:00
    最小生成树: 生成树的代价:设G=(V,E)是一个无向...设G=(V, E)是具有n个顶点的连通网, T=(U, TE)是G的最小生成树, T的初始状态为U={u0}(u0∈V),TE={ }, 重复执行下述操作: 在所有u∈U,v∈V-U的边中找...
  • :最小生成树

    2019-11-24 17:15:43
    设G=(V, E)是具有n个顶点的连通网, T=(U, TE)是G的最小生成树, T的初始状态为U={u0}(u0∈V),TE={ }, 重复执行下述操作: 在所有u∈U,v∈V-U的边中找一条代价最小的边(u, v)并入集合T...
  • 第六章(2)

    2019-11-19 21:29:42
    应用举例——最小生成树 生成树的代价:设G=(V,E)是一个...设G=(V, E)是具有n个顶点的连通网, T=(U, TE)是G的最小生成树, T的初始状态为U={u0}(u0∈V),TE={ }, 重复执行下述操作: 在所有u∈U,v∈V-U...

空空如也

空空如也

1 2 3 4
收藏数 74
精华内容 29
关键字:

具有n个顶点的无向连通图