// 图的数组（邻接矩阵)存储表示
#include
#include
#include
#define MAX_NAME 3 // 顶点字符串的最大长度+1 #define MAX_VERTEX_NUM 20 typedef int InfoType; // 存放网的权值 typedef char VertexType[MAX_NAME]; // 字符串类型 typedef enum{DG, DN, AG, AN}GraphKind; // {有向图,有向网,无向图,无向网} int visited[MAX_VERTEX_NUM]; // 访问标志数组 void(*VisitFunc)(char* v); // 函数变量 typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info; // 网的权值指针 }ArcNode; // 表结点 typedef struct VNode { VertexType data; // 顶点信息 ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针 }VNode, AdjList[MAX_VERTEX_NUM];// 头结点 typedef struct { AdjList vertices; int vexnum, arcnum; // 图的当前顶点数和弧数 int kind; // 图的种类标志 }ALGraph; typedef int QElemType; // 队列类型 //单链队列－－队列的链式存储结构 typedef struct QNode { QElemType data; //数据域 struct QNode *next; //指针域 }QNode, *QueuePtr; typedef struct { QueuePtr front, rear; //队头指针，指针域指向队头元素 队尾指针，指向队尾元素 }LinkQueue; //定位功能 // 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 int LocateVex(ALGraph G,VertexType u) { int i; for(i=0;i
adjvex = j; if((*G).kind == 1 || (*G).kind == 3) // 网 { p->info = (int *)malloc(sizeof(int)); *(p->info) = w; } else p->info = NULL; // 图 p->nextarc = (*G).vertices[i].firstarc; // 插在表头 (*G).vertices[i].firstarc = p; if((*G).kind >= 2) // 无向图或网,产生第二个表结点 { p = (ArcNode*)malloc(sizeof(ArcNode)); p->adjvex = i; if((*G).kind == 3) // 无向网 { p->info = (int*)malloc(sizeof(int)); *(p->info) = w; } else p->info = NULL; // 无向图 p->nextarc = (*G).vertices[j].firstarc; // 插在表头 (*G).vertices[j].firstarc = p; } } return 1; } // 销毁图G void DestroyGraph(ALGraph *G) { int i; ArcNode *p,*q; for(i = 0;i < (*G).vexnum; ++i) { p = (*G).vertices[i].firstarc; while(p) { q = p->nextarc; if((*G).kind%2) // 网 free(p->info); free(p); p=q; } } (*G).vexnum=0; (*G).arcnum=0; } // 返回v的值。 VertexType* GetVex(ALGraph G, int v) { if(v>=G.vexnum||v<0) exit(0); return &G.vertices[v].data; } // 对v赋新值value。 int PutVex(ALGraph *G,VertexType v,VertexType value) { int i; i=LocateVex(*G,v); if(i > -1) // v是G的顶点 { strcpy((*G).vertices[i].data,value); return 1; } return 0; } // 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1。 int FirstAdjVex(ALGraph G,VertexType v) { ArcNode *p; int v1; v1 = LocateVex(G,v); // v1为顶点v在图G中的序号 p = G.vertices[v1].firstarc; if(p) return p->adjvex; else return -1; } // 返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个 // 邻接点, 则返回-1。 int NextAdjVex(ALGraph G,VertexType v,VertexType w) { ArcNode *p; int v1,w1; v1 = LocateVex(G,v); // v1为顶点v在图G中的序号 w1 = LocateVex(G,w); // w1为顶点w在图G中的序号 p = G.vertices[v1].firstarc; while(p&&p->adjvex != w1) // 指针p不空且所指表结点不是w p = p->nextarc; if(!p||!p->nextarc) // 没找到w或w是最后一个邻接点 return -1; else // p->adjvex==w // 返回v的(相对于w的)下一个邻接顶点的序号 return p->nextarc->adjvex; } // 在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)。 void InsertVex(ALGraph *G,VertexType v) { strcpy((*G).vertices[(*G).vexnum].data,v); // 构造新顶点向量 (*G).vertices[(*G).vexnum].firstarc=NULL; (*G).vexnum++; // 图G的顶点数加1 } // 删除G中顶点v及其相关的弧。 int DeleteVex(ALGraph *G,VertexType v) { int i,j; ArcNode *p,*q; j=LocateVex(*G,v); // j是顶点v的序号 if(j < 0 ) // v不是图G的顶点 return 0; p = (*G).vertices[j].firstarc; // 删除以v为出度的弧或边 while( p ) { q = p; p = p->nextarc; if((*G).kind % 2) // 网 free(q->info); free(q); (*G).arcnum--; // 弧或边数减1 } (*G).vexnum--; // 顶点数减1 for(i = j; i < (*G).vexnum; i++) // 顶点v后面的顶点前移 (*G).vertices[i] = (*G).vertices[i+1]; // 删除以v为入度的弧或边且必要时修改表结点的顶点位置值 for(i = 0; i < (*G).vexnum; i++) { p = (*G).vertices[i].firstarc; // 指向第1条弧或边 while(p) // 有弧 { if(p->adjvex == j) // 是以v为入度的边。 { if(p == (*G).vertices[i].firstarc) // 待删结点是第1个结点 { (*G).vertices[i].firstarc = p->nextarc; if((*G).kind % 2) // 网 free(p->info); free(p); p = (*G).vertices[i].firstarc; if((*G).kind < 2) // 有向 (*G).arcnum--; // 弧或边数减1 } else { q->nextarc = p->nextarc; if((*G).kind%2) // 网 free(p->info); free(p); p = q->nextarc; if((*G).kind < 2) // 有向 (*G).arcnum--; // 弧或边数减1 } } else { if(p->adjvex > j) p->adjvex--; // 修改表结点的顶点位置值(序号) q = p; p = p->nextarc; } } } return 1; } // 在G中增添弧
,若G是无向的,则还增添对称弧
。 int InsertArc(ALGraph *G,VertexType v, VertexType w) { ArcNode *p; int w1,i,j; i=LocateVex(*G,v); // 弧尾或边的序号 j