设计算法求无向图的深度优先生成树
借鉴代码：
/** *作者：某某 *2020年11月22日,下午15:31 */ #include <stdio.h> #include <malloc.h> #define MAXV 100//最大顶点个数 int visited[MAXV];//全局数组 typedef int InfoType; typedef struct { int edges[MAXV][MAXV];//邻接矩阵 int vexnum, arcnum; //顶点数，弧数 } MGraph;//图的邻接矩阵类型 typedef struct ANode { int adjvex; //该弧的终点位置 struct ANode* nextarc; //指向下一条弧的指针 InfoType info; //该弧的相关信息,这里用于存放权值 n } ArcNode;//弧的结点结构类型 typedef struct Vnode { //int data; //顶点信息 ArcNode* firstarc;//指向第一条弧 } VNode;//邻接表头结点的类型 typedef struct { VNode adjlist[MAXV];//邻接表 int n, e;//图中顶点数n和边数e } ALGraph;//图的邻接表类型 void init(MGraph& g);//初始化邻接矩阵 void MatToList(MGraph, ALGraph*&);//将邻接矩阵g转换成邻接表G void DispAdj(ALGraph*);//输出邻接表G void DFS(ALGraph* G, int v);//深搜 void BFS(ALGraph* G, int v);//广搜 void main() { MGraph g; g.vexnum = 11; g.arcnum = 13; init(g);//初始化邻接矩阵 ALGraph* G = (ALGraph*)malloc(sizeof(ALGraph)); MatToList(g, G);//将邻接矩阵g转换成邻接表G DispAdj(G);//输出邻接表G for (int i = 0; i < g.vexnum; i++) visited[i] = 0; printf("深度优先生成树:"); DFS(G, 3);//从顶点3开始深度搜索 printf("\n"); } void DFS(ALGraph* G, int v)//从顶点v开始深度搜索 { visited[v] = 1;//置已访问标记 ArcNode* p = G->adjlist[v].firstarc;//p指向顶点v的第一条弧的弧头结点 while (p != NULL) { if (visited[p->adjvex] == 0)//若p->adjvex顶点未访问,递归访问它 { printf("<%d,%d> ", v, p->adjvex);//输出生成树的一条边 DFS(G, p->adjvex);//递归函数 } p = p->nextarc;//p指向顶点v的下一条弧的弧头结点 } } void init(MGraph& g) { int i, j; int A[MAXV][11]; for (i = 0; i < g.vexnum; i++) for (j = 0; j < g.vexnum; j++) A[i][j] = 0; A[0][3] = 1; A[0][2] = 1; A[0][1] = 1; A[1][5] = 1; A[1][4] = 1; A[2][6] = 1; A[2][5] = 1; A[2][3] = 1; A[3][7] = 1; A[6][9] = 1; A[6][8] = 1; A[6][7] = 1; A[7][10] = 1; for (i = 0; i < g.vexnum; i++) for (j = 0; j < g.vexnum; j++) A[j][i] = A[i][j];//无向图双向路径对称 for (i = 0; i < g.vexnum; i++) for (j = 0; j < g.vexnum; j++) g.edges[i][j] = A[i][j]; } void MatToList(MGraph g, ALGraph*& G)//将邻接矩阵g转换成邻接表G { int i, j; G = (ALGraph*)malloc(sizeof(ALGraph)); for (i = 0; i < g.vexnum; i++)//表头节点的指针域置初值 G->adjlist[i].firstarc = NULL; for (i = 0; i < g.vexnum; i++)//对于邻接矩阵中每个元素 for (j = g.vexnum - 1; j >= 0; j--) if (g.edges[i][j] != 0)//邻接矩阵的当前元素不为0---顶点i到j可以走通 { ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));//创建一个新的弧节点 p->adjvex = j;//弧节点的指向的终点位置 p->info = g.edges[i][j];//弧节点的长度 p->nextarc = G->adjlist[i].firstarc;//将*p链到表头后 G->adjlist[i].firstarc = p;//更新表头指针//G->adjlist[i]---表头:顶点i连通到可连通的点 } G->n = g.vexnum;//邻接表G的节点数 G->e = g.arcnum;//弧数 } void DispAdj(ALGraph* G)//输出邻接表G { printf("图G的邻接表:\n"); for (int i = 0; i < G->n; i++)// { ArcNode* p = G->adjlist[i].firstarc; if (p != NULL) printf("%3d: ", i);//输出表头元素 while (p != NULL) { printf("%3d", p->adjvex);//输出表头后链接的元素 p = p->nextarc; } printf("\n"); } }
