手机建站平台,可做影视网站的服务器,柘城网站建设,网站首页被k 不恢复数据结构—邻接表的DFS 原理#xff1a;参考趣学数据结构
代码#xff1a;
#includestdio.h
#includestdlib.h
#define typeNode int //每个头结点的标识数据类型
#define N 100 //最大结点数
int degree[N];
int result[N];
bool visited[N];
typedef str…
数据结构—邻接表的DFS 原理参考趣学数据结构
代码
#includestdio.h
#includestdlib.h
#define typeNode int //每个头结点的标识数据类型
#define N 100 //最大结点数
int degree[N];
int result[N];
bool visited[N];
typedef struct dNode {//每个头结点后紧跟的单位结点int data;struct dNode * next;
}dNode;
typedef struct mNode {//邻接表中每一行的头结点typeNode data;dNode * first;//指向第一个有效的后继结点
}mNode;
typedef struct {mNode vNode[N];//所有头结点int vNum, eNum;//图中顶点的数量和边数量
}zNode;
void init(zNode ZNode) {printf(规定顶点从0开始取\n);scanf_s(%d%d, ZNode.vNum, ZNode.eNum);//输入有向图的顶点数和边数for (int i 0; i ZNode.vNum; i) {//规定顶点从0开始取scanf_s(%d, ZNode.vNode[i].data);ZNode.vNode[i].first NULL;}for (int i 0; i ZNode.eNum; i) {//头插法int u, v;scanf_s(%d%d, u, v);//u顶点到v顶点有边dNode* p new dNode();p-data v;p-next ZNode.vNode[u].first;//只有指针域指向地址ZNode.vNode[u].first p;}
}
void print12(zNode ZNode) {printf(遍历链表:\n);for (int i 0; i ZNode.vNum; i) {dNode* temp ZNode.vNode[i].first;printf(%d -, ZNode.vNode[i].data);while(temp){printf(%d -,temp-data);temp temp-next;}printf(NULL\n);}
}
void DFSLinkGraph(zNode ZNode, int u) {//邻接表的DFSvisited[u] true;printf(%d , u);dNode* p ZNode.vNode[u].first;while (p) {int v p-data;if (!visited[v]) {DFSLinkGraph(ZNode, v);}p p-next;}
}
int main() {zNode ZNode;printf(邻接表的构造:\n);init(ZNode);print12(ZNode);for (int i 0; i ZNode.vNum; i) {visited[i] false;}printf(DFS遍历邻接表\n);DFSLinkGraph(ZNode, 0);printf(\n);system(pause);return 0;
}测试截图 时间复杂度O(n e)空间复杂度O(n)
如果存在什么问题欢迎批评指正谢谢
