图的创建以及深度与广度优先遍历C/C++ |
您所在的位置：网站首页 › 图的创建和遍历 › 图的创建以及深度与广度优先遍历C/C++ |
图的创建以及深度与广度优先遍历C/C++
|
一、图的存储结构 图有几种最常见的存储结构：邻接矩阵、邻接表和十字链表。 下面仅以邻接表表示法进行图的操作 邻接表： 邻接表（Adjacency List）是一种顺序存储结构与链式存储相结合的图的存储方法。邻接表类似于树的孩子链表表示法。就是对于图G中的每个Vi，将所有邻接于Vi的顶点Vj链成一个单链表，这个单链表就称为顶点Vi的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。在邻接表中有两种节点结构，如下： 三、建立无向图的算法 /* *建立无向图的邻接表存储 */ void CreateALGraph(ALGraph *G) { int i , j , k ; EdgeNode *s ; printf("请输入顶点数与边数（输入格式为：顶点数，边数）： ") ; scanf("%d,%d" , &G->n , &G->e) ; printf("请输入顶点信息（输入格式为：顶点号）：\n") ; for( i = 0 ; i < G->n ; i++) { scanf("%s" , G->adjList[i].vertex) ; G->adjList[i].firstedge = NULL ; //将顶点的边表头指针设置为空 } printf("请输入边的信息（输入格式为：i,j）：\n") ; for(k = 0 ; k < G->e ; k++) { scanf("%d,%d" , &i , &j) ; s = (VertexNode*)malloc(sizeof(VertexNode)) ; //边上的第一个节点 s->adjvex = j ; s->next = G->adjList[i].firstedge ; G->adjList[i].firstedge = s ; //边上的第二个节点 s = (VertexNode*)malloc(sizeof(VertexNode)) ; s->adjvex = i ; s->next = G->adjList[j].firstedge ; G->adjList[j].firstedge = s ; } }四、进行无向图的深度优先遍历 思路： 假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可以从图中某个顶点v出发，访问此顶点，然后访问v的一个未被访问的邻接节点w1，接着再从w1出发，访问w1的一个未被访问过的邻接节点w2，然后再从w2出发，访问w2的一个未被访问的邻接顶点w3…如此下去深度优先遍历图，直至图中所有和v有路径相同的顶点都被访问到；若此时途中尚有顶点未被访问，则另选图中另外一个未曾被访问的顶点做起始节点，重复上述过程，直至途中所有节点都被访问到为止。 算法： /* *进行图的深度优先搜索遍历 */ void DFSAL(ALGraph *G , int i) { //以Vi为出发点对图进行遍历 EdgeNode *p ; printf("visit vertex : %s \n" , G->adjList[i].vertex) ; visited[i] = 1 ; p = G->adjList[i].firstedge ; while(p) { if(!visited[p->adjvex]) { DFSAL(G , p->adjvex) ; } p = p->next ; } } void DFSTraverseAL(ALGraph *G) { int i ; for(i = 0 ; i < G->n ; i++) { visited[i] = 0 ; } for(i = 0 ; i < G->n ; i++) { if(!visited[i]) { DFSAL(G , i) ; } } }五、进行图的广度优先遍历 1、从图中某个顶点V0出发，并访问此顶点； 2、从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点； 3、重复步骤2，直到全部顶点都被访问为止。 利用队列进行访问节点的记录。 算法： /* *建立队列的数据结构方便进行广度优先遍历 */ typedef struct { int data[MaxVerNum] ; int head , tail ; //队头与队尾 } Quene ; /* *进行广度优先搜索遍历 */ void BFSG(ALGraph *G , int k) { int i , j ; Quene q ; EdgeNode *p ; q.head = 0 ; q.tail = 0 ; //进行队列的初始化 printf("visit vertex : %s \n" , G->adjList[k].vertex) ; visited[k] = 1 ; q.data[q.tail++] = k ; while(q.head % (MaxVerNum - 1) != q.tail % (MaxVerNum - 1)) { i = q.data[q.head++] ; p = G->adjList[i].firstedge ; while(p) { if(!visited[p->adjvex]) { printf("visit vertex : %s \n" , G->adjList[p->adjvex].vertex) ; visited[p->adjvex] = 1 ; q.data[q.tail++] = p->adjvex ; } p = p->next ; } } } void BFSTraverseAL(ALGraph *G) { int i ; for(i = 0 ; i < G->n ; i++) { visited[i] = 0 ; } for(i = 0 ; i < G->n ; i++) { if(!visited[i]) { BFSG(G , i) ; } } }六、全部测试代码 /* *进行图的遍历，进行图的深度遍历与广度遍历 */ #include #include #define MaxVerNum 100 /*定义最大节点数*/ int visited[MaxVerNum] ; typedef char VertexType ; typedef struct node { int adjvex ; struct node *next ; //指向下一个邻接节点域 } EdgeNode ; typedef struct vnode { VertexType vertex[3] ; //顶点域 EdgeNode *firstedge ; //边表头指针 } VertexNode ; typedef VertexNode AdjList[MaxVerNum] ; /* *定义以邻接边为存储类型的图 */ typedef struct { AdjList adjList ; //邻接表 int n , e ; //顶点数与边数 } ALGraph ; /* *建立队列的数据结构方便进行广度优先遍历 */ typedef struct { int data[MaxVerNum] ; int head , tail ; //队头与队尾 } Quene ; /* *建立无向图的邻接表存储 */ void CreateALGraph(ALGraph *G) { int i , j , k ; EdgeNode *s ; printf("请输入顶点数与边数（输入格式为：顶点数，边数）： ") ; scanf("%d,%d" , &G->n , &G->e) ; printf("请输入顶点信息（输入格式为：顶点号）：\n") ; for( i = 0 ; i < G->n ; i++) { scanf("%s" , G->adjList[i].vertex) ; G->adjList[i].firstedge = NULL ; //将顶点的边表头指针设置为空 } printf("请输入边的信息（输入格式为：i,j）：\n") ; for(k = 0 ; k < G->e ; k++) { scanf("%d,%d" , &i , &j) ; s = (VertexNode*)malloc(sizeof(VertexNode)) ; //边上的第一个节点 s->adjvex = j ; s->next = G->adjList[i].firstedge ; G->adjList[i].firstedge = s ; //边上的第二个节点 s = (VertexNode*)malloc(sizeof(VertexNode)) ; s->adjvex = i ; s->next = G->adjList[j].firstedge ; G->adjList[j].firstedge = s ; } } /* *进行图的深度优先搜索遍历 */ void DFSAL(ALGraph *G , int i) { //以Vi为出发点对图进行遍历 EdgeNode *p ; printf("visit vertex : %s \n" , G->adjList[i].vertex) ; visited[i] = 1 ; p = G->adjList[i].firstedge ; while(p) { if(!visited[p->adjvex]) { DFSAL(G , p->adjvex) ; } p = p->next ; } } void DFSTraverseAL(ALGraph *G) { int i ; for(i = 0 ; i < G->n ; i++) { visited[i] = 0 ; } for(i = 0 ; i < G->n ; i++) { if(!visited[i]) { DFSAL(G , i) ; } } } /* *进行广度优先搜索遍历 */ void BFSG(ALGraph *G , int k) { int i , j ; Quene q ; EdgeNode *p ; q.head = 0 ; q.tail = 0 ; //进行队列的初始化 printf("visit vertex : %s \n" , G->adjList[k].vertex) ; visited[k] = 1 ; q.data[q.tail++] = k ; while(q.head % (MaxVerNum - 1) != q.tail % (MaxVerNum - 1)) { i = q.data[q.head++] ; p = G->adjList[i].firstedge ; while(p) { if(!visited[p->adjvex]) { printf("visit vertex : %s \n" , G->adjList[p->adjvex].vertex) ; visited[p->adjvex] = 1 ; q.data[q.tail++] = p->adjvex ; } p = p->next ; } } } void BFSTraverseAL(ALGraph *G) { int i ; for(i = 0 ; i < G->n ; i++) { visited[i] = 0 ; } for(i = 0 ; i < G->n ; i++) { if(!visited[i]) { BFSG(G , i) ; } } } /* *进行图的测试 */ void main() { ALGraph *G ; EdgeNode *p = NULL ; int i ; G = (ALGraph*)malloc(sizeof(ALGraph)) ; CreateALGraph(G) ; printf("进行深度优先遍历\n") ; DFSTraverseAL(G) ; printf("进行广度优先遍历\n") ; BFSTraverseAL(G) ; } |
邻接表的表示形式如下： 
二、邻接表的数据结构【本文地址】
今日新闻 |
推荐新闻 |