[图]图的遍历-DFS|BFS-递归与非递归-邻接表示例-C语言

xiaoxiao2021-08-27  374

邻接表

// DFS int visit[MAX_VERTEX_NUM]; void DFSUtil_AL(ALGraph G, int v) { ArcNode *p; visit[v]=1; Visit(G.vers[v].data); for (p=G.vers[v].firstarc; p; p=p->next) if (!visit[p->adjV]) DFSUtil_AL(G, p->adjV); } void DFS_AL(ALGraph G) { int i; for (i=0; i<MAX_VERTEX_NUM; i++) { visit[MAX_VERTEX_NUM] = 0; } for (i=0; i<G.vernum; ++i) { if (!visit[i]) DFSUtil_AL(G, i); } } // DFS非递归 void DFSTraverse_Nonrecurisve(ALGraph G) { int visit[maxSize]; int i,j; ArcNode *p; int stack[maxSize],top=-1; for (i=0; i<maxSize; i++) visit[i]=0; for (i=0; i<G.vernum; i++) { if (visit[i]==0) { //没有访问过 //从它开始 top=-1; //清空栈 stack[++top]=i; //入栈 visit[i]=1; Visit(G.vers[i].data); //访问 while (top!=-1) { //栈不空 j = stack[top]; //得出栈顶 //从j开始走 for (p=G.vers[j].firstarc; p; p=p->next) { if (!visit[p->adjV]) { //这条边没有访问过 visit[p->adjV]=1;Visit(G.vers[p->adjV].data); //访问 stack[++top]=p->adjV; //从这个点继续 break; } else //这条边走过了,找下条边 continue; } if (p==NULL) { //j的邻边走完了,返回上个结点,继续往下走 --top; } } } } } // BFS void BFSUntil_AL(ALGraph G,int v) { ArcNode *p; int i; int queue[maxSize],front,rear; front=rear=0; queue[rear]=v; rear=(rear+1)%maxSize; //入队列 while (front!=rear) { //队列未满 i=queue[front]; front=(front+1)%maxSize; //出队列 //访问i visit[i]=1; Visit(G.vers[i].data); //访问i的邻边 for (p=G.vers[i].firstarc; p; p=p->next) { if (visit[p->adjV]==0) { queue[rear]=p->adjV; rear=(front+1)%maxSize; } } } } void BFS_AL(ALGraph G) { //BFS遍历 int i; for (i=0; i<MAX_VERTEX_NUM; ++i) visit[i]=0; //初始化 for (i=0; i<G.vernum; i++) { if (visit[i]==0) {//没有访问过 BFSUntil_AL(G, i); } } }

完整代码

【邻接表】

#include<stdio.h> #include<stdlib.h> #ifndef BASE #define BASE #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int bool; #endif #define VertexType char //点类型 #define VRType int //边类型 #define maxSize 20 void Visit(VertexType e) { printf("%c", e); } #define MAX_VERTEX_NUM 20 typedef enum{DG, UDG} GraphKind; typedef struct ArcNode{ int adjV; //边指向的顶点 VRType weight; //权重 struct ArcNode *next; }ArcNode; //边 typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode, AdjList[MAX_VERTEX_NUM]; //顶点 typedef struct{ GraphKind kind; int vernum,arcnum; AdjList vers; }ALGraph; /*------------------------ |7.14 创建有向图的邻接表| ------------------------*/ Status InitGraph_AL(ALGraph *pG) { //初始化 int i; pG->arcnum = 0; pG->vernum = 0; for (i=0; i<MAX_VERTEX_NUM; ++i) pG->vers[i].firstarc = NULL; //VC++6.0中指针初始化为0xcccccccc return OK; } int LocateVex_AL(ALGraph G, VertexType e) { //定位值为e的元素下标 int i; for (i=0; i<G.vernum; ++i) { if (G.vers[i].data == e) { return i; } } return -1; } Status CreateDG_AL(ALGraph *pG) { //创建有向图的邻接表 //输入规则:顶点数目->弧的数目->各顶点的信息->各条弧的信息 int i,a,b; char tmp[MAX_VERTEX_NUM]; char h,t; ArcNode *p, *q; InitGraph_AL(pG); //VC++6.0中指针初始化为0xcccccccc,如果不将指针初始化为NULL,会出错 //图的类型 pG->kind = DG; //顶点数目 scanf("%d", &i); if (i<0) return ERROR; pG->vernum = i; //弧的数目 scanf("%d", &i); if (i<0) return ERROR; pG->arcnum = i; //各顶点信息 scanf("%s", tmp); for (i=0; i<pG->vernum; ++i) pG->vers[i].data=tmp[i]; //弧的信息 for (i=0; i<pG->arcnum; ++i) { scanf("%s", tmp); h = tmp[0]; t = tmp[2]; a = LocateVex_AL(*pG, h); b = LocateVex_AL(*pG, t); if (a<0 || b<0) return ERROR; p = (ArcNode *)malloc(sizeof(ArcNode)); if (!p) exit(OVERFLOW); p->adjV=b;p->next=NULL; if (pG->vers[a].firstarc) { //已经有边了 for (q = pG->vers[a].firstarc; q->next; q=q->next) ; //找到最后一条 q->next = p; } else { //第一条边 pG->vers[a].firstarc = p; } } return OK; } // DFS int visit[MAX_VERTEX_NUM]; void DFSUtil_AL(ALGraph G, int v) { ArcNode *p; visit[v]=1; Visit(G.vers[v].data); for (p=G.vers[v].firstarc; p; p=p->next) if (!visit[p->adjV]) DFSUtil_AL(G, p->adjV); } void DFS_AL(ALGraph G) { int i; for (i=0; i<MAX_VERTEX_NUM; i++) { visit[MAX_VERTEX_NUM] = 0; } for (i=0; i<G.vernum; ++i) { if (!visit[i]) DFSUtil_AL(G, i); } } // DFS非递归 void DFSTraverse_Nonrecurisve(ALGraph G) { int visit[maxSize]; int i,j; ArcNode *p; int stack[maxSize],top=-1; for (i=0; i<maxSize; i++) visit[i]=0; for (i=0; i<G.vernum; i++) { if (visit[i]==0) { //没有访问过 //从它开始 top=-1; //清空栈 stack[++top]=i; //入栈 visit[i]=1; Visit(G.vers[i].data); //访问 while (top!=-1) { //栈不空 j = stack[top]; //得出栈顶 //从j开始走 for (p=G.vers[j].firstarc; p; p=p->next) { if (!visit[p->adjV]) { //这条边没有访问过 visit[p->adjV]=1;Visit(G.vers[p->adjV].data); //访问 stack[++top]=p->adjV; //从这个点继续 break; } else //这条边走过了,找下条边 continue; } if (p==NULL) { //j的邻边走完了,返回上个结点,继续往下走 --top; } } } } } // BFS void BFSUntil_AL(ALGraph G,int v) { ArcNode *p; int i; int queue[maxSize],front,rear; front=rear=0; queue[rear]=v; rear=(rear+1)%maxSize; //入队列 while (front!=rear) { //队列未满 i=queue[front]; front=(front+1)%maxSize; //出队列 //访问i visit[i]=1; Visit(G.vers[i].data); //访问i的邻边 for (p=G.vers[i].firstarc; p; p=p->next) { if (visit[p->adjV]==0) { queue[rear]=p->adjV; rear=(front+1)%maxSize; } } } } void BFS_AL(ALGraph G) { //BFS遍历 int i; for (i=0; i<MAX_VERTEX_NUM; ++i) visit[i]=0; //初始化 for (i=0; i<G.vernum; i++) { if (visit[i]==0) {//没有访问过 BFSUntil_AL(G, i); } } } int main() { /* 6 11 ABCDEF B,A B,D C,B C,F D,C D,E D,F E,A F,A F,B F,E */ ALGraph G; CreateDG_AL(&G); DFS_AL(G);printf("\n"); DFSTraverse_Nonrecurisve(G);printf("\n"); BFS_AL(G);printf("\n"); return 0; }
转载请注明原文地址: https://www.6miu.com/read-4823565.html

最新回复(0)