#include <stdio.h> #include <stdlib.h> #include <string.h> #include "ALGraph.h" int visited[MAXVEX]; /*设访问标志数组为全局变量*/ void DFSTraverse(ALGraph g)/*深度优先遍历以邻接表存储的图g*/ { int i; for(i=0;i<g.vexnum;i++) /*访问标志数组初始化*/ visited[i]=0; for(i=0;i<g.vexnum;i++) if(!visited[i]) DFS(g,i); /*对尚未访问的顶点调用DFS函数*/ } void DFS(ALGraph g, int i)/*从未被访问的顶点Vi出发深度优先遍历图g*/ { // 请在这里补充代码,完成本关任务 /********** Begin *********/ /********** End **********/ }
时间: 2023-07-23 07:00:46 浏览: 77
void DFS(ALGraph g, int i)/*从未被访问的顶点Vi出发深度优先遍历图g*/
{
visited[i] = 1; /*将顶点i标记为已访问*/
printf("%c ", g.vertices[i].data); /*输出顶点i的值*/
EdgeNode *p = g.vertices[i].firstedge; /*获取顶点i的第一个邻接边*/
while (p) {
if (!visited[p->adjvex]) { /*如果该邻接顶点未被访问*/
DFS(g, p->adjvex); /*递归调用DFS函数*/
}
p = p->next; /*继续遍历下一个邻接边*/
}
}
相关问题
实现基于邻接表表示的深度优先遍历。 函数接口定义: void DFS(ALGraph G, int v); 其中 G 是基于邻接表存储表示的无向图,v表示遍历起点。 裁判测试程序样例: #include <stdio.h> #include <stdlib.h> #define MVNum 10 int visited[MVNum]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; int info; }ArcNode; typedef struct VNode{ char data; ArcNode *firstarc; }VNode, AdjList[MVNum]; typedef struct{ AdjList vertices; int vexnum, arcnum; }ALGraph; int CreateUDG(ALGraph &G);//实现细节隐藏 void DFS(ALGraph G, int v); void DFSTraverse(ALGraph G){ int v; for(v = 0; v < G.vexnum; ++v) visited[v] = 0; for(v = 0; v < G.vexnum; ++v) if(!visited[v]) DFS(G, v); } int main(){ ALGraph G; CreateUDG(G); DFSTraverse(G); return 0; } /* 请在这里填写答案 */ 输入样例: 输入第1行为结点数vexnum和边数arcnum。第2行为结点的值,依次输入arcnum行,每行输入两个结点的值表示该两个结点互为邻接点。 8 8 ABCDEFGH A B A C B D B E C F C G D H E H 输出样例: 遍历序列。 A C G F B E H D QQ截图20191125133700.png 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
```
#include <stdio.h>
#include <stdlib.h>
#define MVNum 10
int visited[MVNum];
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
int info;
}ArcNode;
typedef struct VNode{
char data;
ArcNode *firstarc;
}VNode, AdjList[MVNum];
typedef struct{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
int CreateUDG(ALGraph &G);//实现细节隐藏
void DFS(ALGraph G, int v);
void DFSTraverse(ALGraph G){
int v;
for(v = 0; v < G.vexnum; ++v)
visited[v] = 0;
for(v = 0; v < G.vexnum; ++v)
if(!visited[v])
DFS(G, v);
}
int main(){
ALGraph G;
CreateUDG(G);
DFSTraverse(G);
return 0;
}
void DFS(ALGraph G, int v){
visited[v] = 1;
printf("%c ", G.vertices[v].data);
ArcNode *p = G.vertices[v].firstarc;
while(p){
if(!visited[p->adjvex])
DFS(G, p->adjvex);
p = p->nextarc;
}
}
```
#include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 100 // 最大顶点数 #define FALSE 0 #define TRUE 1 // 邻接表结构体 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ int data; ArcNode *firstarc; }VNode, AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum, arcnum; // 顶点数和边数 }ALGraph; // 初始化邻接表 void InitALGraph(ALGraph *G) { int i; G->vexnum = G->arcnum = 0; for(i = 0; i < MAX_VERTEX_NUM; i++){ G->vertices[i].firstarc = NULL; } } // 添加顶点 void AddVertex(ALGraph *G, int v) { if(G->vexnum == MAX_VERTEX_NUM){ printf("Error: Vertex number exceeds maximum.\n"); return; } G->vertices[G->vexnum].data = v; G->vexnum++; } // 添加边 void AddArc(ALGraph *G, int v1, int v2) { if(G->arcnum >= MAX_VERTEX_NUM * (MAX_VERTEX_NUM - 1) / 2){ printf("Error: Arc number exceeds maximum.\n"); return; } ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = v2; p->nextarc = G->vertices[v1].firstarc; G->vertices[v1].firstarc = p; G->arcnum++; } // DFS遍历 void DFS(ALGraph *G, int v, int *visited) { printf("%d ", G->vertices[v].data); visited[v] = TRUE; ArcNode *p = G->vertices[v].firstarc; while(p != NULL){ int w = p->adjvex; if(!visited[w]){ DFS(G, w, visited); } p = p->nextarc; } } // BFS遍历 void BFS(ALGraph *G, int v, int *visited) { int queue[MAX_VERTEX_NUM]; int front = -1, rear = -1; printf("%d ", G->vertices[v].data); visited[v] = TRUE; queue[++rear] = v; while(front != rear){ int w = queue[++front]; ArcNode *p = G->vertices[w].firstarc; while(p != NULL){ int u = p->adjvex; if(!visited[u]){ printf("%d ", G->vertices[u].data); visited[u] = TRUE; queue[++rear] = u; } p = p->nextarc; } } } int main() { ALGraph G; InitALGraph(&G); // 添加顶点 AddVertex(&G, 1); AddVertex(&G, 2); AddVertex(&G, 3); AddVertex(&G, 4); AddVertex(&G, 5); // 添加边 AddArc(&G, 0, 1); AddArc(&G, 0, 2); AddArc(&G, 1, 3); AddArc(&G, 1, 4); AddArc(&G, 2, 4); // 输出深度优先序列 int visited[MAX_VERTEX_NUM] = {FALSE}; printf("DFS: "); DFS(&G, 0, visited); printf("\n"); // 输出广度优先序列 int visited2[MAX_VERTEX_NUM] = {FALSE}; printf("BFS: "); BFS(&G, 0, visited2); printf("\n"); return 0; } 修改代码,使其能输出图的可视化输出图
要输出图的可视化输出图,需要使用图形库或工具,例如Graphviz。以下是修改后的代码,可以输出Graphviz所需的DOT格式的图形描述语言,通过复制到Graphviz的在线编辑器或使用本地Graphviz软件处理后,即可生成图形化的图像。
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
#define FALSE 0
#define TRUE 1
// 邻接表结构体
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
int data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum, arcnum; // 顶点数和边数
}ALGraph;
// 初始化邻接表
void InitALGraph(ALGraph *G) {
int i;
G->vexnum = G->arcnum = 0;
for(i = 0; i < MAX_VERTEX_NUM; i++){
G->vertices[i].firstarc = NULL;
}
}
// 添加顶点
void AddVertex(ALGraph *G, int v) {
if(G->vexnum == MAX_VERTEX_NUM){
printf("Error: Vertex number exceeds maximum.\n");
return;
}
G->vertices[G->vexnum].data = v;
G->vexnum++;
}
// 添加边
void AddArc(ALGraph *G, int v1, int v2) {
if(G->arcnum >= MAX_VERTEX_NUM * (MAX_VERTEX_NUM - 1) / 2){
printf("Error: Arc number exceeds maximum.\n");
return;
}
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = v2;
p->nextarc = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = p;
G->arcnum++;
}
// DFS遍历
void DFS(ALGraph *G, int v, int *visited) {
printf("%d ", G->vertices[v].data);
visited[v] = TRUE;
ArcNode *p = G->vertices[v].firstarc;
while(p != NULL){
int w = p->adjvex;
if(!visited[w]){
DFS(G, w, visited);
}
p = p->nextarc;
}
}
// BFS遍历
void BFS(ALGraph *G, int v, int *visited) {
int queue[MAX_VERTEX_NUM];
int front = -1, rear = -1;
printf("%d ", G->vertices[v].data);
visited[v] = TRUE;
queue[++rear] = v;
while(front != rear){
int w = queue[++front];
ArcNode *p = G->vertices[w].firstarc;
while(p != NULL){
int u = p->adjvex;
if(!visited[u]){
printf("%d ", G->vertices[u].data);
visited[u] = TRUE;
queue[++rear] = u;
}
p = p->nextarc;
}
}
}
// 输出Graphviz所需的DOT格式的图形描述语言
void OutputGraphviz(ALGraph *G) {
printf("digraph G {\n");
int i;
for(i = 0; i < G->vexnum; i++){
printf(" %d;\n", G->vertices[i].data);
ArcNode *p = G->vertices[i].firstarc;
while(p != NULL){
printf(" %d -> %d;\n", G->vertices[i].data, G->vertices[p->adjvex].data);
p = p->nextarc;
}
}
printf("}\n");
}
int main() {
ALGraph G;
InitALGraph(&G);
// 添加顶点
AddVertex(&G, 1);
AddVertex(&G, 2);
AddVertex(&G, 3);
AddVertex(&G, 4);
AddVertex(&G, 5);
// 添加边
AddArc(&G, 0, 1);
AddArc(&G, 0, 2);
AddArc(&G, 1, 3);
AddArc(&G, 1, 4);
AddArc(&G, 2, 4);
// 输出深度优先序列
int visited[MAX_VERTEX_NUM] = {FALSE};
printf("DFS: ");
DFS(&G, 0, visited);
printf("\n");
// 输出广度优先序列
int visited2[MAX_VERTEX_NUM] = {FALSE};
printf("BFS: ");
BFS(&G, 0, visited2);
printf("\n");
// 输出Graphviz所需的DOT格式的图形描述语言
OutputGraphviz(&G);
return 0;
}
```