求一个无向图G的连通分量的个数.doc

精品文档数据结构实验报告实验内容： （一）判断一个图有无回路 （二）求一个无向图G的连通分量的个数 一、 目的和要求（需求分析）：1、 了解图的定义和图的存储结构。 2、 熟悉掌握图的邻接矩阵和邻接表。3、 理解图的遍历算法-深度优先搜索和广度优先搜索。4、 学会编程处理图的连通性问题。二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）判断一个图有无回路：在程序设计中，先必须确定所要创建的图是有向还是无向，是图还是网，其次再根据各自的特点，用连接表来实现创建。在有向图中，先找出入度为0的顶点，删除与这个顶点相关联的边（出边），将与这些边相关的其它顶点的入度减1，循环直到没有入度为0的顶点。如果此时还有未被删除的顶点，则必然存在环路，否则不存在回路。无向图则可以转化为：如果存在回路，则必然存在一个子图，是一个回路。因此回路中所有定点的度=2。第一步：删除所有度=1的顶点及相关边，并将另外与这些边相关的其它顶点的度减1。第二步：将度数变为1的顶点排入队列，并从该队列中（使用栈）取出一个顶点，并重复步骤一。如果最后还有未删除的顶点，则存在回路，否则没有。求一个无向图G的连通分量的个数：用连接表创建图，对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。所以在设计中，为了统计出无向图中的连通分量个数，则因在其深度优先所搜无向图时对函数DFSTraverse(ALGraph G)调用DFS次数进行统计，其结果便为无向图中连通分量个数。三、调试和运行程序过程中产生的问题及采取的措施：在调试和运行求一个无向图G的连通分量的个数程序时，由于执行语句块void DFSTraverse(ALGraph G)先于void DFS(ALGraph G,int v)，而void DFSTraverse(ALGraph G)内调用了DFS( )，因此计算机无法正确运行，将两者顺序进行了交换，程序便实现了其功能，且运行正常。四、源程序及注释：判断一个图有无回路：#include #include #include / 输出有向图的一个拓扑序列。 / 图的邻接表存储表示 #define MAX_NAME 3/ 顶点字符串的最大长度+1 #define MAX_VERTEX_NUM 20#define STACK_INIT_SIZE 10/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 typedef int InfoType;/ 存放网的权值 typedef char VertexTypeMAX_NAME;/ 字符串类型 typedef enumDG,DN,AG,ANGraphKind; / 有向图,有向网,无向图,无向网 typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针 InfoType *info;/ 网的权值指针） ArcNode;/ 表结点 typedef struct VNodeVertexType data;/ 顶点信息 ArcNode *firstarc;/ 第一个表结点的地址,指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM;/ 头结点 typedef structAdjList vertices;int vexnum,arcnum;/ 图的当前顶点数和弧数 int kind;/ 图的种类标志 ALGraph;/ 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 int LocateVex(ALGraph G,VertexType u)int i;for(i=0;iG.vexnum;+i)if(strcmp(u,G.verticesi.data)=0)return i;return -1;/ 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。int CreateGraph(ALGraph *G)int i,j,k;int w;/ 权值 VertexType va,vb;ArcNode *p;printf(请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): );scanf(%d,&(*G).kind);printf(请输入图的顶点数和边数:（空格）n);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).verticesi.data);(*G).verticesi.firstarc = NULL;if(*G).kind = 1 | (*G).kind = 3) / 网 printf(请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):n);else / 图 printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n);for(k = 0;k adjvex = j;if(*G).kind = 1 | (*G).kind = 3) / 网 p-info = (int *)malloc(sizeof(int);*(p-info) = w;elsep-info = NULL; / 图 p-nextarc = (*G).verticesi.firstarc; / 插在表头 (*G).verticesi.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;elsep-info = NULL; / 无向图 p-nextarc = (*G).verticesj.firstarc; / 插在表头 (*G).verticesj.firstarc = p;return 1;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.verticesi.data);printf(n%d条弧(边):n, G.arcnum);for(i = 0; i G.vexnum; i+)p = G.verticesi.firstarc;while(p)if(G.kind adjvex.data);if(G.kind = DN) / 网 printf(:%d , *(p-info);else/ 无向(避免输出两次) if(i adjvex)printf(%s%s ,G.verticesi.data,G.verticesp-adjvex.data);if(G.kind = AN)/ 网 printf(:%d ,*(p-info);p=p-nextarc;printf(n); void FindInDegree(ALGraph G,int indegree) / 求顶点的入度。 int i;ArcNode *p;for(i=0;iG.vexnum;i+)indegreei=0; / 赋初值 for(i=0;iadjvex+;p=p-nextarc;typedef int SElemType; / 栈类型 typedef struct SqStack / 栈的顺序存储表示SElemType *base;/ 在栈构造之前和销毁之后，base的值为NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 SqStack;/ 顺序栈int InitStack(SqStack *S) /构造一个空栈S/ 为栈底分配一个指定大小的存储空间(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base )exit(0);/ 存储分配失败 (*S).top = (*S).base;/ 栈底与栈顶相同表示一个空栈(*S).stacksize = STACK_INIT_SIZE;return 1;/ 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。int StackEmpty(SqStack S)if(S.top = S.base)return 1;elsereturn 0;int Push(SqStack *S, SElemType e) /插入元素e为新的栈顶元素。if(*S).top - (*S).base = (*S).stacksize)/ 栈满，追加存储空间 (*S).base = (SElemType *)realloc(*S).base, (*S).stacksize + STACKINCREMENT) * sizeof(SElemType);if( !(*S).base )exit(0); / 存储分配失败 (*S).top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base)return 0;*e = *-(*S).top;/ 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/ 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序/ 列并返回1, 否则返回0。int TopologicalSort(ALGraph G)int i,k,count,indegreeMAX_VERTEX_NUM;SqStack S;ArcNode *p;FindInDegree(G,indegree); / 对各顶点求入度indegree0.vernum-1 InitStack(&S); / 初始化栈 for(i=0;inextarc)/ 对i号顶点的每个邻接点的入度减1 k=p-adjvex;if(!(-indegreek) / 若入度减为0,则入栈 Push(&S,k);if(countG.vexnum)printf(此有向图有回路n);return 0;elseprintf(无回路，此图的拓扑序n);return 1;int main()ALGraph f;printf(请选择有向图n);CreateGraph(&f);Display(f);TopologicalSort(f);system(pause);return 0; 求一个无向图G的连通分量的个数#include #include #include /无向图的邻接表存储表示 #define MAX_NAME 3/ 顶点字符串的最大长度+1 #define MAX_VERTEX_NUM 20#define TRUE 1#define FALSE 0int visitedMAX_VERTEX_NUM;/访问标志数组 typedef char VertexTypeMAX_NAME;/ 字符串类型 typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针 ArcNode;/ 表结点 typedef struct VNodeVertexType data;/ 顶点信息 ArcNode *firstarc;/ 第一个表结点的地址,指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM;/ 头结点 typedef structAdjList vertices;int vexnum,arcnum;/ 图的当前顶点数和弧数 ALGraph;/ 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 int LocateVex(ALGraph G,VertexType u)int i;for(i=0;iG.vexnum;+i)if(strcmp(u,G.verticesi.data)=0)return i;return -1;/ 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)。int CreateGraph(ALGraph *G)int i,j,k;VertexType va,vb;ArcNode *p;printf(请输入无向图的顶点数和边数:（空格）n);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).verticesi.data);(*G).verticesi.firstarc = NULL;printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n);for(k = 0;k adjvex = j;p-nextarc = (*G).verticesi.firstarc; / 插在表头 (*G).verticesi.firstarc = p; / 无向图产生第二个表结点 p = (ArcNode*)malloc(sizeof(ArcNode);p-adjvex = i;p-nextarc = (*G).verticesj.firstarc; / 插在表头 (*G).verticesj.firstarc = p;return 1;/输出图的邻接表G。void Display(ALGraph G)int i;ArcNode *p; printf(无向图n);printf(%d个顶点：n,G.vexnum);for(i = 0; i G.vexnum; +i)printf(%s ,G.verticesi.data);printf(n%d条弧(边):n, G.arcnum);for(i = 0; i G.vexnum; i+)p = G.verticesi.firstarc;while(p)if(i adjvex)/ 无向(避免输出两次)printf(%s%s ,G.verticesi.data,G.verticesp-adjvex.data);p=p-nextarc;printf(n);void DFS(ALGraph G,int v)/从第v个顶点出发递归地深度优先遍历图G。 ArcNode *p; visitedv = TRUE;/访问第v个顶点 for(p=G.verticesv.firstarc;p;p=p-nextarc) if(!visitedp-adjvex) DFS(G,p-adjvex);/对v尚未访问的邻接点递归调用DFS void DFSTraverse(ALGraph G)/对图G作深度优先遍历。 int v,count=0; for (v=0;vG.vexnum;+v) visitedv=FALSE; for (v=0;vG.vexn