图的邻接表表示法及遍历

时间: 2023-11-27 19:07:21 浏览: 90

图的邻接表及遍历

#include<stdio.h> #include<stdlib.h> #include<conio.h> #include<math.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define NULL 0 #define MAX 20 typedef int Status; typedef struct Node {int elem; struct Node *next; }Node,*QNode; typedef struct {QNode front; QNode rear; }Queue; typedef struct ArcNode /*头节点*/ {int adjvex; /*该边所指向的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条边*/ }ArcNode; typedef struct VNode /*表节点*/ {int data; /*顶点信息*/ ArcNode *firstarc; /*指向第一条依附该节点的边的指针*/ }VNode,AdjList[MAX]; typedef struct {AdjList vertices; /*表节点*/ int vexnum; /*节点的个数*/ int arcnum; /*边的条数*/ }Graph; Status InitQueue(Queue *Q) {Q->front=Q->rear=(QNode)malloc(sizeof(Node)); if(!Q->front) exit(OVERFLOW); Q->front->next=NULL; return OK; } Status EnQueue(Queue *Q,int e) {QNode p=(QNode)malloc(sizeof(Node)); if(!p) exit(OVERFLOW); p->elem=e; p->next=NULL; Q->rear->next=p; Q->rear=p; return OK; } Status DeQueue(Queue *Q,int *e) {QNode p; p=Q->front->next; Q->front->next=p->next; if(Q->rear==p) Q->rear=Q->front; *e=p->elem; free(p); return OK; } Status QueueEmpty(Queue Q) {if(Q.rear==Q.front) return TRUE; else return FALSE; } int LocateVex(Graph *G,int v) /*返回节点v在图中的位置*/ {int i; for(i=0;i<G->vexnum;++i) if(G->vertices[i].data==v) break; else continue; if(i<G->vexnum) return i; else return -1; } Status CreateGraph(Graph *G)/*以邻接表形式创建无向连通图G*/ {int m,n,i,j,k,v1,v2,flag=0; ArcNode *p1,*q1,*p,*q; printf("Please input the number of VNode: "); scanf("%d",&m); printf("Please input the number of ArcNode: "); scanf("%d",&n); G->vexnum=m; /*顶点数目*/ G->arcnum=n; /*边的数目*/ for(i=0;i<G->vexnum;++i) {G->vertices[i].data=i+1; /*顶点信息*/ G->vertices[i].firstarc=NULL; } printf("Output the message of VNode:\n"); for(i=0;i<G->vexnum;++i) printf("v%d\n",G->vertices[i].data); for(k=0;k<G->arcnum;++k) {printf("Please input the %d edge beginpoint and endpoint: ",k+1); scanf("%d%d",&v1;,&v2;); i=LocateVex(G,v1); j=LocateVex(G,v2); if(i>=0&&j>=0) {++flag; p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; p->nextarc=NULL; if(!G->vertices[i].firstarc) G->vertices[i].firstarc=p; else{for(p1=G->vertices[i].firstarc;p1->nextarc;p1=p1->nextarc); p1->nextarc=p; } q=(ArcNode *)malloc(sizeof(ArcNode)); q->adjvex=i; q->nextarc=NULL; if(!G->vertices[j].firstarc) G->vertices[j].firstarc=q; else{for(q1=G->vertices[j].firstarc;q1->nextarc;q1=q1->nextarc); q1->nextarc=q; } } else{printf("Not hava this edge!\n"); k=flag; } } printf("The Adjacency List is:\n"); /*输出邻接表*/ for(i=0;i<G->vexnum;++i) {printf("\t%d v%d->",i,G->vertices[i].data); p=G->vertices[i].firstarc; while(p->nextarc) {printf("%d->",p->adjvex); p=p->nextarc; } printf("%d\n",p->adjvex); } return OK; } int FirstAdjVex(Graph G,int v)/*返回v的第一个邻接顶点*/ {if(G.vertices[v].firstarc) return G.vertices[v].firstarc->adjvex; else return -1; }/*FirstAdjVex*/ int NextAdjVex(Graph G,int v,int w)/*返回v中相对于w的下一个邻接顶点*/ {int flag=0; ArcNode *p; p=G.vertices[v].firstarc; while(p) { if(p->adjvex==w) { flag=1; break; } p=p->nextarc; } if(flag && p->nextarc) return p->nextarc->adjvex; else return -1; }/*NextAdjVex*/ int Visited[MAX]; void DFS(Graph G,int v)/*深度优先遍历*/ {int w; Visited[v]=TRUE; printf("v%d ",G.vertices[v].data); for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)) if(!Visited[w]) DFS(G,w); } void DFSTraverse(Graph G) {int v; for(v=0;v<G.vexnum;++v) Visited[v]=FALSE; for(v=0;v<G.vexnum;++v) if(!Visited[v]) DFS(G,v); } void BFSTraverse(Graph G)/*广度优先遍历*/ {int v,v1,w; Queue q; for(v=0;v<G.vexnum;++v) Visited[v]=FALSE; InitQueue(&q); for(v=0;v<G.vexnum;++v) if(!Visited[v]) {Visited[v]=TRUE; printf("v%d ",G.vertices[v].data); EnQueue(&q,v); /*第一个顶点入队*/ while(!QueueEmpty(q)) {DeQueue(&q,&v1;); /*第一个顶点出对*/ for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,w)) if(!Visited[w]){Visited[w]=TRUE; printf("v%d ",G.vertices[w].data); EnQueue(&q,w); }/*if*/ } } } main() {Graph G; char ch; system("cls"); CreateGraph(&G); while(1) {printf("which one choice you want DFS(1) BFS(2) orQuit(0)?\n"); scanf("%d",&ch;); switch(ch) {case 1:printf("Depth First Search:\n"); DFSTraverse(G); break; case 2:printf("\nBreadth First Search:\n"); BFSTraverse(G); break; case 0:exit(0); } } getch(); } 根据提供的代码和描述，我们可以总结出以下几个关键知识点： ### 1. 图的邻接表表示方法在这段代码中，图是以**邻接表**的形式存储的。邻接表是一种常用的图存储结构，适合用于存储稀疏图。它通过一个数组来表示图中的各个顶点，并且每个顶点都有一个链表与其相连，用来表示与该顶点相邻的所有顶点。 #### 结构定义 - **`AdjList`**: 定义了一个数组`AdjList[MAX]`，其中`MAX`是预设的最大顶点数量。数组中的每个元素都是`VNode`类型。 - **`VNode`**: 表示一个顶点，包含以下字段： - `int data`: 顶点的数据或编号。 - `ArcNode *firstarc`: 指向与该顶点相邻的所有顶点链表的头结点。 - **`ArcNode`**: 表示一条边，包含以下字段： - `int adjvex`: 相邻顶点的位置（在数组中的索引）。 - `ArcNode *nextarc`: 指向下一个边的指针。 #### 创建图 - 函数`CreateGraph`用于创建一个无向图。 - 首先读取顶点数`m`和边数`n`。 - 初始化顶点信息。 - 读取每条边的两个端点，并通过调用`LocateVex`函数获取这两个顶点在数组中的位置。 - 使用动态分配的内存创建`ArcNode`，并将它们添加到对应的顶点链表中。 - 最后输出创建完成的邻接表。 ### 2. 图的遍历算法图的遍历有两种基本方式：**深度优先搜索(DFS)** 和 **广度优先搜索(BFS)**。 #### 深度优先搜索 (DFS) - **实现**: 使用递归的方式实现深度优先遍历。 - **过程**: - 标记访问过的顶点，避免重复访问。 - 访问一个顶点。 - 递归地访问该顶点的所有未被访问过的邻接顶点。 - 重复上述步骤直到所有顶点都被访问过。 #### 广度优先搜索 (BFS) - **实现**: 使用队列实现广度优先遍历。 - **过程**: - 将起始顶点标记为已访问并加入队列。 - 当队列不为空时： - 从队列头部取出顶点进行访问。 - 将该顶点的所有未被访问过的邻接顶点标记为已访问并加入队列尾部。 - 重复上述步骤直到队列为空。 ### 3. 辅助数据结构为了实现图的遍历，本程序还定义了**队列**这一辅助数据结构。 #### 队列 - **定义**: 使用链表实现的队列结构。 - **操作**: - `InitQueue`: 初始化队列。 - `EnQueue`: 元素入队。 - `DeQueue`: 元素出队。 - `QueueEmpty`: 判断队列是否为空。 ### 4. 主程序逻辑 - **主函数`main`**: - 调用`CreateGraph`函数创建图。 - 提供一个循环让用户选择进行DFS、BFS还是退出程序。 - 实现DFS和BFS的遍历。通过以上分析可以看出，这段代码不仅实现了图的基本存储结构——邻接表，还提供了两种重要的图遍历算法：深度优先搜索和广度优先搜索，以及一个队列辅助结构。这些基础知识对于理解和实现图的相关算法非常有帮助。

邻接表是一种图的表示方法，由一个由顶点列表和每个顶点对应的邻接点列表组成。具体地，每个顶点对应一个链表，链表中存储该顶点所连接的所有顶点。例如，下面是一个无向图的邻接表表示。 ``` 0: 1->2 1: 0->2->3 2: 0->1->3 3: 1->2 ``` 表示图中有4个顶点，编号分别为0、1、2、3。顶点0连接顶点1和2，顶点1连接顶点0、2和3，以此类推。遍历图的方式有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。 DFS从某个顶点开始，一直沿着一条路径访问下去，直到走到不能再走为止，然后回溯到前一个节点，再沿着另一条路径继续访问，直到所有节点都被访问为止。具体实现可以使用递归或栈来实现。 BFS从某个顶点开始，先访问该顶点的所有邻接顶点，然后访问这些邻接顶点的邻接顶点，依次类推，直到所有节点都被访问为止。具体实现可以使用队列来实现。

阅读全文

图的邻接表表示法及遍历

相关推荐

邻接表和遍历

图的邻接表存储下的遍历算法

图的邻接表表示法及遍历代码实现

图的邻接表表示法及遍历C语言实现

图的邻接表表示法及遍历c语言代码实现

数据结构无向图邻接表表示和DFS遍历

图的数组表示法和邻接表表示法及运用

图论算法详解：从邻接表到图的遍历

邻接表表示法的深度优先遍历（C语言）

用C语言完成基于邻接表表示法实现图的广度优先遍历

c语言基于邻接表的DFS遍历算法,用户输入总顶点数和总边数，再输入每个顶点，再输入每条边依附的顶点对序列 ,得到邻接表表示法创建的无向图，再输入遍历连通图的起始点，得到深度优先搜索遍历图结果 完整代码 算法思想

图的邻接表表示法 pdf

有向图的邻接矩阵与图的遍历

1.采用邻接表表示法创建无向图 void CreateUDG(AL Graph &G) 2.深度优先搜索遍历 void DFS(ALGraph G. int v) 3.编写一个主函数，调用上述算法，实现采用邻接表表示图的深度优先搜索遍历。

采用邻接表表示法，构造无向网G；并从任意一个顶点出发，递归地深度优先遍历该图G

c语言实现采用邻接表表示法，构造无向网G；并从任意一个顶点出发，递归地深度优先遍历该图G

图邻接表图的遍历等有关操作

邻接表的两种遍历

最新推荐

假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作： （1）构造图（包括有向图、有向网、无向图、无向网）； （2）根据深度优先遍历图。

数据结构课程设计-图的存储与遍历

【java毕业设计】应急救援物资管理系统源码（springboot+vue+mysql+说明文档）.zip

基于java的音乐网站答辩PPT.pptx

基于Flexsim的公路交通仿真系统.zip

Android圆角进度条控件的设计与应用

管理建模和仿真的文件

【R语言lattice包实战】：从案例到技巧，图形制作不再难

输入正整数n.打出长度为n的菱形

mui框架实现带侧边栏的响应式布局

c语言基于邻接表的DFS遍历算法,用户输入总顶点数和总边数，再输入每个顶点，再输入每条边依附的顶点对序列 ,得到邻接表表示法创建的无向图，再输入遍历连通图的起始点，得到深度优先搜索遍历图结果完整代码算法思想

假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作：（1）构造图（包括有向图、有向网、无向图、无向网）；（2）根据深度优先遍历图。