#include <stdio.h> #include <stdlib.h> 访问标志向量是全局量 void DFSTraverse(ALGraph *G) { //深度优先遍历以邻接表表示的图 G,而以邻接矩阵表示 G 时,算法完全与 int i; for(i=0;i<G->n;i++) visited[i]=FALSE; //标志向量初始化 for(i=0;i<G->n;i++) if(!visited[i]) //vi 未访问过 DFS(G,i); //以 vi 为源点开始 DFS 此相同 搜索 }//DFSTraverse //(2)邻接表表示的深度优先搜索算法 void DFS(ALGraph *G,int i){ //以 vi 为出发点对邻接表表示的图 G 进行深度优先搜索 EdgeNode *p; printf("visit vertex:%c",G->adjlist[i].vertex);//访问顶点 vi visited[i]=TRUE; //标记 vi 已访问 p=G->adjlist[i].firstedge; //取 vi 边表的头指针 while(p){//依次搜索 vi 的邻接点 vj,这里 j=p->adjvex if (!visited[p->adjvex])//若 vi 尚未被访问 DFS(G,p->adjvex);//则以 Vj 为出发点向纵深搜索 p=p->next; //找 vi 的下一邻接点 } }//DFS #define MaxVertexNum 5 #define m 5 #define NULL 0 typedef struct node { int adjvex; struct node *next; }JD; typedef struct tnode { int vexdata; JD *firstarc; }TD; typedef struct { TD ag[m]; int n; }ALGRAPH; void DFS(ALGRAPH *G,int i); void creat(ALGRAPH *G) {int i,m1,j; JD *p,*p1; printf("please input the number of graph\n"); scanf("%d",&G->n); for(i=0;i<G->n;i++) {printf("please input the info of node %d",i); scanf("%d",&G->ag[i].vexdata); printf("please input the number of arcs which adj to %d",i); scanf("%d",&m1); printf("please input the adjvex position of the first arc\n"); p=(JD *)malloc(sizeof(JD)); scanf("%d",&p->adjvex); p->next=NULL; G->ag[i].firstarc=p; p1=p; for(j=2 ;j<=m1;j++) {printf("please input the position of the next arc vexdata\n"); p=(JD *)malloc(sizeof(JD)); scanf("%d",&p->adjvex); p->next=NULL; p1->next=p; p1=p;} } } int visited[MaxVertexNum]; void DFSTraverse(ALGRAPH *G) { int i; for(i=0;i<G->n;i++) visited[i]=0; for(i=0;i<G->n;i++) if(!visited[i]) DFS(G,i); }/*DFSTraverse */ void DFS(ALGRAPH *G,int i){ JD *p; printf("visit vertex:%d->",G->ag[i].vexdata); visited[i]=1; /*标记 vi 已访问 */ p=G->ag[i].firstarc; /*取 vi 边表的头指针*/ while(p){/*依次搜索 vi 的邻接点 vj,这里 j=p->adjvex*/ if (!visited[p->adjvex])/*若 vi 尚未被访问 */ DFS(G,p->adjvex);/*则以 Vj 为出发点向纵深搜索 */ p=p->next; } }/*DFS */ main() { ALGRAPH *G; printf("下面以临接表存储一个图;\n"); creat(G); printf("下面以深度优先遍历该图 \n"); DFSTraverse(G); getch(); }
时间: 2024-04-03 09:32:37 浏览: 24
这段代码实现了一个以邻接表表示的图的深度优先遍历算法。在该算法中,使用了一个全局的标志向量 visited,用来记录每个顶点是否被访问过。在 DFSTraverse 函数中,遍历整个图,对于每个未被访问的顶点,以该顶点为起点进行 DFS,即深度优先搜索。在 DFS 函数中,首先访问当前顶点,然后遍历该顶点的所有邻接点,对于每个未被访问过的邻接点,以该邻接点为起点进行递归搜索,直到搜索完所有与该顶点相连的顶点。算法的时间复杂度为 O(V+E),其中 V 和 E 分别为图的顶点数和边数。
相关问题
#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 **********/ }
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;
}
}
```
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![image/gif](https://img-home.csdnimg.cn/images/20210720083352.png)
![application/pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)