数据结构(C实现)——- 图的深度优先遍历


[本文是自己学习所做笔记,欢迎转载,但请注明出处:http://blog.csdn.net/jesson20121020]

算法描写:      

       假定给定图G的初始状态是所有顶点均未曾访问过,在G中任选1顶点vi为初始的动身点,则深度优先遍历可定义以下: 首先访问动身点vi,并将其标记为已被访问过;然后,顺次从vi动身遍历vi的每个邻接点vj,若vj未曾访问过,则以vj为新的动身点继续进行深度优先遍历,直至图中所有和vi有路径相通的顶点都被访问到为止。因此,若G是连通图,则从初始动身点开始的遍历进程结束也就意味着完成了对图G的遍历。

算法实现:

       分别以邻接矩阵和邻接表作为图的存储结构,给出连通图的深度优先搜索遍历的递归算法。算法描写以下:

      (1) 访问动身点vi,并将其标记为已被访问已访问过。

      (2) 遍历vi的每个邻接点vj,若vj未曾访问过,则以vj为新的动身点继续进行深度优先遍历。

完全代码:

      用邻接矩阵实现深度优先搜索算法源代码以下:

/**
* 深度遍历图
**/
void DFS_MG(MGraph MG,int i){
visit[i] = 1;
printf("%c ",MG.vexs[i]);
int j;
for (j = 1; j <= MG.vexnum;j++){
if(visit[j] == 0 && MG.arcs[i][j] == 1)
DFS_MG(MG,j);
}
}

    

     用邻接表实现深度优先搜索算法源代码以下:

/**
* 深度遍历图
**/
void DFS_AG(ALGraph AG,int i){
ArcPtr p;
printf("%c ",AG.vertices[i].vexdata);
visit[i] = 1;
p = AG.vertices[i].firstarc;
while( p!= NULL ){
if(visit[p->adjvex] == 0)
DFS_AG(AG,p->adjvex);
p = p->nextarc;
}
}

算法说明:

         对具有n个顶点,e条边的连通图,算法DFS_MG,DFS_AG
均调用n次。除初始调用是来自外部,基于n⑴次调用均是来自DFS_MG和DFS_AG内部的递归调用,用邻接矩阵实现时,遍历1个顶点的所有邻接点需要O(n)时间,则遍历全部图需要O(n^2),即DFS_MG的时间复杂度为O(n^2)。

       用邻接表实现时,遍历n个顶点的所有邻接点是对边表节点的扫描1遍,故算法DFS_AG时间复杂度为O(n+e)。

          采取深度优先遍历算法时,都要用到访问标志,所以该算法的空间复杂度为O(n).

      

          邻接矩阵实现深度优先搜索算法完全代码以下:

/*
============================================================================
Name : Graph.c
Author : jesson20121020
Version : 1.0
Description : create Graph using Adjacency Matrix, Ansi-style
============================================================================
*/

#include <stdio.h>
#include <stdlib.h>
#define MAX_VEX_NUM 50
typedef char VertexType;
typedef enum {
DG, UDG
} GraphType;
typedef struct {
VertexType vexs[MAX_VEX_NUM];
int arcs[MAX_VEX_NUM][MAX_VEX_NUM];
int vexnum, arcnum;
GraphType type;
} MGraph;

//设置图中顶点访问标志
int visit[MAX_VEX_NUM];

/**
* 根据名称得到指定顶点在顶点集合中的下标
* vex 顶点
* return 如果找到,则返回下标,否则,返回0
*/
int getIndexOfVexs(char vex, MGraph *MG) {
int i;
for (i = 1; i <= MG->vexnum; i++) {
if (MG->vexs[i] == vex) {
return i;
}
}
return 0;
}

/**
* 创建邻接矩阵
*/
void create_MG(MGraph *MG) {
int i, j, k;
int v1, v2, type;
char c1, c2;
printf("Please input graph type DG(0) or UDG(1) :");
scanf("%d", &type);
if (type == 0)
MG->type = DG;
else if (type == 1)
MG->type = UDG;
else {
printf("Please input correct graph type DG(0) or UDG(1)!");
return;
}

printf("Please input vexmun : ");
scanf("%d", &MG->vexnum);
printf("Please input arcnum : ");
scanf("%d", &MG->arcnum);
getchar();
for (i = 1; i <= MG->vexnum; i++) {
printf("Please input %dth vex(char):", i);
scanf("%c", &MG->vexs[i]);
getchar();
}

//初始化邻接矩阵
for (i = 1; i <= MG->vexnum; i++) {
for (j = 1; j <= MG->vexnum; j++) {
MG->arcs[i][j] = 0;
}
}

//输入边的信息,建立邻接矩阵
for (k = 1; k <= MG->arcnum; k++) {
printf("Please input %dth arc v1(char) v2(char) : ", k);

scanf("%c %c", &c1, &c2);
v1 = getIndexOfVexs(c1, MG);
v2 = getIndexOfVexs(c2, MG);
if (MG->type == 1)
MG->arcs[v1][v2] = MG->arcs[v2][v1] = 1;
else
MG->arcs[v1][v2] = 1;
getchar();
}
}
/**
* 打印邻接矩阵和顶点信息
*/
void print_MG(MGraph MG) {
int i, j;
if(MG.type == DG){
printf("Graph type: Direct graph
");
}
else{
printf("Graph type: Undirect graph
");
}

printf("Graph vertex number: %d
",MG.vexnum);
printf("Graph arc number: %d
",MG.arcnum);

printf("Vertex set:
");
for (i = 1; i <= MG.vexnum; i++)
printf("%c ", MG.vexs[i]);
printf("
Adjacency Matrix:
");

for (i = 1; i <= MG.vexnum; i++) {
j = 1;
for (; j < MG.vexnum; j++) {
printf("%d ", MG.arcs[i][j]);
}
printf("%d
", MG.arcs[i][j]);
}
}

/**
* 初始化顶点访问标志
**/
void init_Visit(){
int i;
for(i = 0;i < MAX_VEX_NUM;i++)
visit[i] = 0;
}

/**
* 深度遍历图
**/
void DFS_MG(MGraph MG,int i){
visit[i] = 1;
printf("%c ",MG.vexs[i]);
int j;
for (j = 1; j <= MG.vexnum;j++){
if(visit[j] == 0 && MG.arcs[i][j] == 1)
DFS_MG(MG,j);
}
}

/**
* 主函数
*/
int main(void) {
MGraph MG;
create_MG(&MG);
print_MG(MG);
printf("The result of DFS:
");
DFS_MG(MG,1);

return EXIT_SUCCESS;
}

       邻接表实现深度优先搜索算法的完全代码以下:

/*
============================================================================
Name : ALGraph.c
Author : jesson20121020
Version : 1.0
Copyright : Your copyright notice
Description : Graph using linkList, Ansi-style
============================================================================
*/

#include <stdio.h>
#include <stdlib.h>

#include <stdio.h>

#define MAX_VERTEX_NUM 50
typedef enum {
DG, UDG
} GraphType;
typedef char VertexType;
//表节点
typedef struct ArcNode {
int adjvex; //邻接节点
int weight; //边权重
struct ArcNode *nextarc; //下1个节点指针
} ArcNode, *ArcPtr;
//头节点
typedef struct {
VertexType vexdata;
int id;
ArcPtr firstarc;
} VNode;
//头节点数组
typedef struct {
VNode vertices[MAX_VERTEX_NUM];
int vexnum, arcnum;
GraphType type;
} ALGraph;

int visit[MAX_VERTEX_NUM];

/**
* 根据顶点字符得到在顶点数组中的下标
*/
int getIndexOfVexs(char vex, ALGraph *AG) {
int i;
for (i = 1; i <= AG->vexnum; i++) {
if (AG->vertices[i].vexdata == vex) {
return i;
}
}
return 0;
}
/**
* 创建邻接表
*/
void create_AG(ALGraph *AG) {
ArcPtr p,q;
int i, j, k, type;
VertexType v1, v2;
printf("Please input graph type UG(0) or UDG(1) :");
scanf("%d", &type);
if (type == 0)
AG->type = DG;
else if (type == 1)
AG->type = UDG;
else {
printf("Please input correct graph type UG(0) or UDG(1)!");
return;
}

printf("please input vexnum:");
scanf("%d", &AG->vexnum);
printf("please input arcnum:");
scanf("%d", &AG->arcnum);
getchar();
for (i = 1; i <= AG->vexnum; i++) {
printf("please input the %dth vex(char) : ", i);
scanf("%c", &AG->vertices[i].vexdata);
getchar();
AG->vertices[i].firstarc = NULL;
}

for (k = 1; k <= AG->arcnum; k++) {
printf("please input the %dth arc v1(char) v2(char) :", k);
scanf("%c %c", &v1, &v2);
i = getIndexOfVexs(v1, AG);
j = getIndexOfVexs(v2, AG);

//根据图的类型创建邻接表
//方法1,插入到链表头
/*
if (AG->type == DG) { //有向图
p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = AG->vertices[i].firstarc;
AG->vertices[i].firstarc = p;
} else { //无向图
p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = AG->vertices[i].firstarc;
AG->vertices[i].firstarc = p;

p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = AG->vertices[j].firstarc;
AG->vertices[j].firstarc = p;
}
*/
//方法2,插入到链表尾
if (AG->type == DG) { //有向图
p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = j;
//表为空
if(AG->vertices[i].firstarc == NULL){
AG->vertices[i].firstarc = p;
}
else{
//找最后1个表节点
q = AG->vertices[i].firstarc;
while(q->nextarc != NULL){
q = q->nextarc;
}
q->nextarc = p;
}
p->nextarc = NULL;

} else { //无向图

p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = j;
//表为空
if(AG->vertices[i].firstarc == NULL){
AG->vertices[i].firstarc = p;
}
else{
//找最后1个表节点
q = AG->vertices[i].firstarc;
while(q->nextarc != NULL){
q = q->nextarc;
}
q->nextarc = p;
}
p->nextarc = NULL;

p = (ArcPtr) malloc(sizeof(ArcNode));
p->adjvex = i;
//表为空
if(AG->vertices[j].firstarc == NULL){
AG->vertices[j].firstarc = p;
}
else{
//找最后1个表节点
q = AG->vertices[j].firstarc;
while(q->nextarc != NULL){
q = q->nextarc;
}
q->nextarc = p;
}
p->nextarc = NULL;
}

getchar();
}
}

/**
* 输出图的相干信息
*/
void print_AG(ALGraph AG) {
ArcPtr p;
int i;
if (AG.type == DG) {
printf("Graph type: Direct graph
");
} else {
printf("Graph type: Undirect graph
");
}

printf("Graph vertex number: %d
", AG.vexnum);
printf("Graph arc number: %d
", AG.arcnum);

printf("Vertex set :
");
for (i = 1; i <= AG.vexnum; i++)
printf("%c ", AG.vertices[i].vexdata);
printf("
Adjacency List:
");
for (i = 1; i <= AG.vexnum; i++) {
printf("%d", i);
p = AG.vertices[i].firstarc;
while (p != NULL) {
printf("–>%d", p->adjvex);
p = p->nextarc;
}
printf("
");
}
}

/**
* 初始化顶点访问标志
**/
void init_Visit(){
int i;
for(i = 0;i < MAX_VERTEX_NUM;i++)
visit[i] = 0;
}

/**
* 深度遍历图
**/
void DFS_AG(ALGraph AG,int i){
ArcPtr p;
printf("%c ",AG.vertices[i].vexdata);
visit[i] = 1;
p = AG.vertices[i].firstarc;
while( p!= NULL ){
if(visit[p->adjvex] == 0)
DFS_AG(AG,p->adjvex);
p = p->nextarc;
}
}

int main(void) {
ALGraph AG;

create_AG(&AG);

print_AG(AG);
printf("The result of DFS:
");
DFS_AG(AG,1);

return EXIT_SUCCESS;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 数据结构(C实现)——- 图的深度优先遍历

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡