深度优先搜索邻接表存储结构下的无向图

雨点打透心脏的1/2处 2022-01-14 16:07 238阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

# **问题描述** #

使用邻接表存储下图所示无向图，使用**深度优先搜索**遍历无向图上的各节点

\*\*    ![d91273ff377e75ed1521303d0a8d51f46d8.jpg][]\*\*

# **解题思路** #

1、创建一个邻接表接受无向图信息

# **程序实现** #

#include <stdlib.h>
    #include <stdio.h>
    
    #define MAXVEX 10
    #define TRUE 1
    #define FALSE 0
    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
    typedef int Status;
    /* 顶点类型应由用户定义  */
    typedef char VertexType;
    /* 边上的权值类型应由用户定义 */
    typedef int EdgeType;
    
    /* 邻接表的数据结构 */
    typedef struct EdgeNode {
    	// 邻接点域,存储该顶点对应的下标
    	int adjvex;
    	// 链域,指向下一个邻接点
    	struct EdgeNode *next;
    } EdgeNode;
    
    // 顶点表结点
    typedef struct VertexNode {
    	// 顶点域,存储顶点信息
    	VertexType data;
    	// 边表头指针
    	EdgeNode *firstedge;
    } VertexNode, AdjList[MAXVEX];
    
    typedef struct {
    	AdjList adjList;
    	// 图中顶点数
    	int numNodes;
    	// 图中边数
    	int numEdges;
    } GraphAdjList, *GraphList;
    
    
    void createMyGraph(GraphList *plus);
    void DFS(GraphList plus, int i);
    void DFSTraverse(GraphList plus);
    int main(void) {
    	int i, j;
    	GraphList plus;
    	createMyGraph(&plus);
    	for (i = 0; i < plus->numNodes; i++) {
    		printf("%c:\t", plus->adjList[i].data);
    		EdgeNode *e;
    		e = plus->adjList[i].firstedge;
    		while (e != NULL) {
    			printf("%c\t", plus->adjList[e->adjvex].data);
    			e = e->next;
    		}
    		free(e); 
    		printf("\n");
    	}
    	printf("\n深度优先搜素：\n");
    	DFSTraverse(plus); 
    }
    
    /**
     * 创建无向图
     */
    void createMyGraph(GraphList *plus) {
    	int i, j, k, w;
    	EdgeNode *e;
    	printf("请输入顶点数和边数:\n");
    	scanf("%d,%d", &i, &j);
    	*plus = (GraphList)malloc(sizeof(GraphAdjList));
    	getchar();
    	(*plus)->numNodes = i;
    	(*plus)->numEdges = j;
    	// 读入顶点数
    	for (i = 0; i < (*plus)->numNodes; i++) {
    		// 输入顶点信息
    		scanf("%c", &(*plus)->adjList[i].data);
    		// 将边表置为空表
    		(*plus)->adjList[i].firstedge=NULL;
    	}
    
    	// 读入numEdges条边，建立邻接矩阵
    	for(k = 0; k < (*plus)->numEdges; k++) {
    		printf("输入边(vi,vj)上的下标i,下标j:\n");
    		scanf("%d,%d", &i, &j);
    		// 向内存申请空间,生成边表结点
    		e = (EdgeNode *)malloc(sizeof(EdgeNode));
    		// 邻接序号为j
    		e->adjvex = j;
    		// 将e的指针指向当前顶点上指向的结点
    		e->next = (*plus)->adjList[i].firstedge;
    		// 将当前顶点的指针指向e
    		(*plus)->adjList[i].firstedge = e;
    
    		// 因为是无向图，所以需对称存储
    		// 向内存申请空间,生成边表结点
    		e=(EdgeNode *)malloc(sizeof(EdgeNode));
    		// 邻接序号为i
    		e->adjvex=i;
    		// 将e的指针指向当前顶点上指向的结点
    		e->next= (*plus)->adjList[j].firstedge;
    		// 将当前顶点的指针指向e
    		(*plus)->adjList[j].firstedge=e;
    	}
    }
    
    // 访问标志的数组
    int visited[MAXVEX];
    /**
     * 邻接表的深度优先搜索操作 
     */ 
    void DFS(GraphList plus, int i) {
    	EdgeNode *p;
    	visited[i] = TRUE;
    	printf("%c ",plus->adjList[i].data);
    	p = plus->adjList[i].firstedge;
    	while(p) {
    		if(!visited[p->adjvex]) {
    			// 对为访问的邻接顶点递归调用 
    			DFS(plus, p->adjvex);
    		}
    		p = p->next;
    	}
    }
    
    void DFSTraverse(GraphList plus) {
    	int i;
    	// 初始所有顶点状态都是未访问过状态
    	for(i = 0; i < plus->numNodes; i++) {
    		visited[i] = FALSE;
    	}
    	for(i = 0; i < plus->numNodes; i++) {
    		// 对未访问过的顶点调用DFS,若是连通图,只会执行一次
    		if(!visited[i])  {
    			DFS(plus, i);
    		}
    	}
    }

# **运行结果** #

**![00f1a20419b353a199ef2b116cbb6f860ad.jpg][]**

转载于:https://my.oschina.net/niithub/blog/3048554

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/0320c9cba9f1417096b70590031b87bd.png
[d91273ff377e75ed1521303d0a8d51f46d8.jpg]: /images/20220114/6a5fd26cb0a74d0baff6067066cb1975.png
[00f1a20419b353a199ef2b116cbb6f860ad.jpg]: /images/20220114/bfe58c20dc0b4517ba998539dde148aa.png