C语言实现图的深度优先遍历
/*-----------------------------------------Copyright (c) 2010-2011 Zidane CLiUsage of this program is free for non-commercial use.-----------------------------------------*//* 用邻接矩阵实现图，并用广度优先遍历遍历图。*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <limits.h>#define MAX_NAME 5// 顶点字符串的最大长度+1#define MAX_INFO 20// 相关信息字符串的最大长度+1typedef int VRType;// 顶点关系的数据类型#define INFINITY INT_MAX// 用整型最大值代替∞#define MAX_VERTEX_NUM 20// 最大顶点个数 typedef char InfoType;// 信息的类型typedef char VertexType[MAX_NAME];// 顶点数据类型及长度typedef enum {DG, DN, UDG, UDN}GraphKind;typedef struct ArcCell{VRType adj;InfoType* info;}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct {VertexType vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum, arcnum;GraphKind kind;}MGraph;#define BOOL int#define TRUE 1#define FALSE 0typedef VertexType *QElemType;typedef struct{QElemType* elem; //存储空间基址int queuesize;int front;int rear;}SqQueue;void visit(VertexType a){printf("%s ", a);}int LocateVex(MGraph G, VertexType a){ int i;for (i = 0; i < G.vexnum; i++){if(strcmp(a, G.vexs[i]) == 0){return i;}}return -1;}void CreateDG(MGraph* G){VertexType va, vb; int IncInfo, i, j, k;printf("Number of Vex and Arc, Info: ");scanf("%d%d%d", &G->vexnum, &G->arcnum, &IncInfo);//构造顶点向量for (i = 0; i < G->vexnum; i++){scanf("%s", G->vexs[i]); }//初始化邻接矩阵for (i = 0; i < G->vexnum; i++){for (j = 0; j < G->vexnum; j++){G->arcs[i][j].adj = 0;G->arcs[i][j].info = NULL;}}//构造邻接矩阵for (k = 0; k < G->arcnum; k++){//顶点1，顶点2，权值scanf("%s%s", va, vb);i = LocateVex(*G, va);j = LocateVex(*G, vb);G->arcs[i][j].adj = 1;if (IncInfo){scanf("%s", G->arcs[i][j].info);}G->arcs[j][i].adj = G->arcs[i][j].adj;}G->kind = DG;}void CreateDN(MGraph* G){VertexType va, vb; int IncInfo, i, j, w, k;printf("Number of Vex and Arc, Info: ");scanf("%d%d%d", &G->vexnum, &G->arcnum, &IncInfo);//构造顶点向量for (i = 0; i < G->vexnum; i++){scanf("%s", G->vexs[i]); }//初始化邻接矩阵for (i = 0; i < G->vexnum; i++){for (j = 0; j < G->vexnum; j++){G->arcs[i][j].adj = INFINITY;G->arcs[i][j].info = NULL;}}//构造邻接矩阵for (k = 0; k < G->arcnum; k++){//顶点1，顶点2，权值scanf("%s%s%d", va, vb, &w);i = LocateVex(*G, va);j = LocateVex(*G, vb);G->arcs[i][j].adj = w;if (IncInfo){scanf("%s", G->arcs[i][j].info);}}G->kind = DN;}void CreateUDG(MGraph* G){VertexType va, vb; int IncInfo, i, j, k;printf("Number of Vex and Arc, Info: ");scanf("%d%d%d", &G->vexnum, &G->arcnum, &IncInfo);//构造顶点向量for (i = 0; i < G->vexnum; i++){scanf("%s", G->vexs[i]); }//初始化邻接矩阵for (i = 0; i < G->vexnum; i++){for (j = 0; j < G->vexnum; j++){G->arcs[i][j].adj = 0;G->arcs[i][j].info = NULL;}}//构造邻接矩阵for (k = 0; k < G->arcnum; k++){//顶点1，顶点2，权值scanf("%s%s", va, vb);i = LocateVex(*G, va);j = LocateVex(*G, vb);G->arcs[i][j].adj = 1;if (IncInfo){scanf("%s", G->arcs[i][j].info);}G->arcs[j][i].adj = G->arcs[i][j].adj;}G->kind = UDG;}void CreateUDN(MGraph* G){VertexType va, vb; int IncInfo, i, j, w, k;printf("Number of Vex and Arc, Info: ");scanf("%d%d%d", &G->vexnum, &G->arcnum, &IncInfo);//构造顶点向量for (i = 0; i < G->vexnum; i++){scanf("%s", G->vexs[i]); }//初始化邻接矩阵for (i = 0; i < G->vexnum; i++){for (j = 0; j < G->vexnum; j++){G->arcs[i][j].adj = INFINITY;G->arcs[i][j].info = NULL;}}//构造邻接矩阵for (k = 0; k < G->arcnum; k++){//顶点1，顶点2，权值scanf("%s%s%d", va, vb, &w);i = LocateVex(*G, va);j = LocateVex(*G, vb);G->arcs[i][j].adj = w;if (IncInfo){scanf("%s", G->arcs[i][j].info);}G->arcs[j][i].adj = G->arcs[i][j].adj;}G->kind = UDN;}void CreateGraph(MGraph* G){printf("Kind of the Graph: ");scanf("%d", (int*)&G->kind);switch (G->kind){case DG: return CreateDG(G);break;case DN: return CreateDN(G);break;case UDG: return CreateUDG(G);break;case UDN: return CreateUDN(G);break;}}VertexType* GetVex(MGraph G, int v){ //局部变量保存在stack中，函数执行完会自动释放，所以不要将局部变量的指针作为返回值 VertexType* vex = (VertexType*)malloc(sizeof(VertexType)); vex = &G.vexs[v];return vex;}//对a赋新值valuevoid PutVex(MGraph* G, VertexType a, char* value){int i = LocateVex(*G, a);strcpy(G->vexs[i], value);}//返回a的第一个邻接顶点（从第一个顶点开始与其相连的第一个顶点）int FirstAdjVex(MGraph G, VertexType a){int k = LocateVex(G, a);int w = (G.kind == DN || G.kind == UDN ? INFINITY : 0);int i;for (i = 0; i < G.vexnum; i++){if (G.arcs[k][i].adj != w){return i;}}return -1;}//返回a的（相对于b的）下一个邻接顶点。若b是a的最后一个邻接点，则返回-1。int NextAdjVex(MGraph G, VertexType a, VertexType b){int k1 = LocateVex(G, a);int k2 = LocateVex(G, b);int w = (G.kind == DN || G.kind == UDN ? INFINITY : 0);int i;for (i = k2 + 1; i < G.vexnum; i++){if (G.arcs[k1][i].adj != w){return i;}}return -1;}//在图中只添加一个顶点，且和图中顶点有相同特征void InsertVex(MGraph* G, VertexType a){strcpy(G->vexs[G->vexnum], a);int i;for(i = 0; i <= G->vexnum; i++){switch (G->kind){case DG: case UDG: G->arcs[G->vexnum][i].adj = 0;G->arcs[i][G->vexnum].adj = 0;break;case DN: case UDN: G->arcs[G->vexnum][i].adj = INFINITY;G->arcs[i][G->vexnum].adj = INFINITY;break; }}G->vexnum++;}void DeleteVex(MGraph* G, VertexType v){int i, j, k;VRType m=0;k = LocateVex(*G,v);// k为待删除顶点v的序号 if(k < 0)// v不是图G的顶点if(G->kind == DN || G->kind == UDN) // 网m = INFINITY;for(j = 0; j < G->vexnum; j++)if(G->arcs[j][k].adj != m)// 有入弧或边 {if(G->arcs[j][k].info)// 有相关信息 free(G->arcs[j][k].info);// 释放相关信息 G->arcnum--;// 修改弧数 }if(G->kind == DG || G->kind == DN) // 有向 for(j = 0; j < G->vexnum; j++)if(G->arcs[k][j].adj != m)// 有出弧 {if(G->arcs[k][j].info) // 有相关信息 free(G->arcs[k][j].info); // 释放相关信息 G->arcnum--; // 修改弧数 }for(j = k + 1; j < G->vexnum; j++) // 序号k后面的顶点向量依次前移 strcpy(G->vexs[j-1], G->vexs[j]);for(i = 0; i < G->vexnum; i++)for(j = k + 1; j < G->vexnum; j++)G->arcs[i][j-1] = G->arcs[i][j]; // 移动待删除顶点之后的矩阵元素 for(i = 0; i < G->vexnum; i++)for(j = k + 1; j < G->vexnum; j++)G->arcs[j - 1][i] = G->arcs[j][i]; // 移动待删除顶点之下的矩阵元素 G->vexnum--;}void InsertArc(MGraph* G, VertexType a, VertexType b){int i = LocateVex(*G, a);int j = LocateVex(*G, b);G->arcnum++;switch (G->kind){case DG: G->arcs[i][j].adj = 1;break;case DN: printf("Please input value of arc: ");scanf("%d", &G->arcs[i][j].adj);break;case UDG: G->arcs[i][j].adj = 1;break;case UDN: printf("Please input value of arc: ");scanf("%d", &G->arcs[i][j].adj);break;}}void DeleteArc(MGraph* G, VertexType a, VertexType b){int i = LocateVex(*G, a);int j = LocateVex(*G, b);G->arcnum--;switch (G->kind){case DG: case UDG: G->arcs[i][j].adj = 0;break;case DN: case UDN: G->arcs[i][j].adj = INFINITY;break;}}/**/BOOL visited[MAX_VERTEX_NUM];void DFS(MGraph G, int u){ visited[u] = TRUE; visit(G.vexs[u]); VertexType v; strcpy(v, G.vexs[u]); int i = FirstAdjVex(G, v); for (; i >= 0; i = NextAdjVex(G, v, *GetVex(G, i))) { if (!visited[i]){DFS(G, i);} }}void DFSTraverse(MGraph G){ printf("DFS: "); int i;for (i = 0; i < G.vexnum; i++){visited[i] = FALSE;}for (i = 0; i < G.vexnum; i++){if (!visited[i]){DFS(G, i);}}printf("\n");}int main(){ MGraph a; CreateGraph(&a); DFSTraverse(a); return 0;}?