咸鱼网站交易付款怎么做,成都文化墙设计公司,天蒙旅游区网络营销推广方法,html用什么软件打开首先数据结构(C语言版第二版)的关于深度优先搜索遍历连通图的图G4如下: 使用邻接表去创建上面这个无向图#xff0c;然后再使用书本DFS函数以及DFSTraverse函数实现深度优先搜索遍历
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#…首先数据结构(C语言版第二版)的关于深度优先搜索遍历连通图的图G4如下: 使用邻接表去创建上面这个无向图然后再使用书本DFS函数以及DFSTraverse函数实现深度优先搜索遍历
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#define MAXVEX 20
//下面三个结构体就是邻接表的结构体完全一样的方式
typedef struct EdgeNode
{int adjvex;struct EdgeNode* next;
}EdgeNode;
typedef struct VertexNode
{char data;EdgeNode* firstedge;
}VertexNode;
typedef struct
{VertexNode adjlist[MAXVEX];int numVertexs;int numEdges;
}GraphAdjlist;
int visited[10];//一个标记数组记录遍历过的不会重复遍历
//创建邻接表
void CreateALGraph(GraphAdjlist* G)
{int i, j, k;EdgeNode* p;printf(请输入顶点数边数\n);scanf(%d%d, G-numVertexs, G-numEdges);getchar();//接收scanf残留的换行符\nprintf(请输入顶点的信息\n);for (i 0; i G-numVertexs; i){scanf(%c, G-adjlist[i].data);G-adjlist[i].firstedge NULL;//初始化指向边表的指针为null}for (k 0; k G-numEdges; k){printf(请输入(vi,vj)的头尾,一共有%d条\n, G-numEdges);scanf(%d%d, i, j);//我们这里是实现深度遍历连通图的无向图p (EdgeNode*)malloc(sizeof(EdgeNode));p-adjvex j;p-next G-adjlist[i].firstedge;G-adjlist[i].firstedge p;p (EdgeNode*)malloc(sizeof(EdgeNode));p-adjvex i;p-next G-adjlist[j].firstedge;G-adjlist[j].firstedge p;}printf(邻接表创建成功\n);
}
void DFS(GraphAdjlist* G,int i)
{EdgeNode* p;visited[i] 1;printf(%c , G-adjlist[i].data);//先把这个顶点值输出,有点类似树的先序遍历根左右p G-adjlist[i].firstedge;while (p!NULL){if (visited[p-adjvex] 0){DFS(G, p-adjvex);}p p-next;}
}
void DFSTraverse(GraphAdjlist* G)
{int i;for (i 0; i G-numVertexs; i){visited[i] 0;//全部初始为0然后遍历过的(vi,vj)就置为1 由未访问 - 已访问}for (i 0; i G-numVertexs; i){if (visited[i] 0){DFS(G, i);}}
}
int main()
{GraphAdjlist G;CreateALGraph(G);printf(深度遍历如下\n);DFSTraverse(G);return 0;
}
关于深度遍历很相似树的前序遍历(根左右),如果出现(根右左)其实这个问题也就是邻接表边表插入结点的时候我们使用的是头插法所以才有时候出现深度优先遍历会出现根右左这个没关系的不重复遍历就好
下面是终端输入内容: 请输入顶点数边数 8 9 请输入顶点的信息 01234567 请输入(vi,vj)的头尾,一共有9条 0 1 请输入(vi,vj)的头尾,一共有9条 0 2 请输入(vi,vj)的头尾,一共有9条 1 3 请输入(vi,vj)的头尾,一共有9条 1 4 请输入(vi,vj)的头尾,一共有9条 3 7 请输入(vi,vj)的头尾,一共有9条 4 7 请输入(vi,vj)的头尾,一共有9条 2 5 请输入(vi,vj)的头尾,一共有9条 2 6 请输入(vi,vj)的头尾,一共有9条 5 6 邻接表创建成功 深度遍历如下 0 2 6 5 1 4 7 3 下标全部1就可以查看12345678的遍历情况 关于非连通图代码通用的;
数据结构书本关于深度优先搜索遍历的非连通图如下: 终端输入内容如下: 请输入顶点数边数 8 8 请输入顶点的信息 01234567 请输入(vi,vj)的头尾,一共有8条 0 1 请输入(vi,vj)的头尾,一共有8条 1 3 请输入(vi,vj)的头尾,一共有8条 1 4 请输入(vi,vj)的头尾,一共有8条 3 7 请输入(vi,vj)的头尾,一共有8条 4 7 请输入(vi,vj)的头尾,一共有8条 2 5 请输入(vi,vj)的头尾,一共有8条 2 6 请输入(vi,vj)的头尾,一共有8条 5 6 邻接表创建成功 深度遍历如下 0 1 4 7 3 2 6 5 非连续图中的边数由9 - 8
