|
=LocateVex(*G,w); // 弧头或边的序号 if(i < 0 || j < 0) return 0; (*G).arcnum++; // 图G的弧或边的数目加1 if((*G).kind%2) // 网 { printf(请输入弧(边)%s→%s的权值: ,v,w); scanf(%d,&w1); } p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; if((*G).kind%2) // 网 { p->info=(int*)malloc(sizeof(int)); *(p->info)=w1; } 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) = w1; } else p->info=NULL; p->nextarc=(*G).vertices[j].firstarc; // 插在表头 (*G).vertices[j].firstarc=p; } return 1; } // 在G中删除弧
,若G是无向的,则还删除对称弧
。 int DeleteArc(ALGraph *G,VertexType v,VertexType w) { ArcNode *p,*q; int i,j; i = LocateVex(*G,v); // i是顶点v(弧尾)的序号 j = LocateVex(*G,w); // j是顶点w(弧头)的序号 if(i < 0 || j < 0 || i == j) return 0; p=(*G).vertices[i].firstarc; // p指向顶点v的第一条出弧 while(p&&p->adjvex!=j) // p不空且所指之弧不是待删除弧
{ // p指向下一条弧 q=p; p=p->nextarc; } if(p&&p->adjvex==j) // 找到弧
{ if(p==(*G).vertices[i].firstarc) // p所指是第1条弧 (*G).vertices[i].firstarc=p->nextarc; // 指向下一条弧 else q->nextarc=p->nextarc; // 指向下一条弧 if((*G).kind%2) // 网 free(p->info); free(p); // 释放此结点 (*G).arcnum--; // 弧或边数减1 } if((*G).kind>=2) // 无向,删除对称弧
{ p=(*G).vertices[j].firstarc; // p指隙サ?的第一条出弧 while(p&&p->adjvex!=i) // p不空且所指之弧不是待删除弧
{ // p指向下一条弧 q=p; p=p->nextarc; } if(p&&p->adjvex==i) // 找到弧
{ if(p==(*G).vertices[j].firstarc) // p所指是第1条弧 (*G).vertices[j].firstarc=p->nextarc; // 指向下一条弧 else q->nextarc=p->nextarc; // 指向下一条弧 if((*G).kind==3) // 无向网 free(p->info); free(p); // 释放此结点 } } return 1; } // 从第v个顶点出发递归地深度优先遍历图G。 void DFS(ALGraph G,int v) { int w; VertexType v1,w1; strcpy(v1,*GetVex(G,v)); visited[v] = 1; // 设置访问标志为1(已访问) VisitFunc(G.vertices[v].data); // 访问第v个顶点 for(w = FirstAdjVex(G,v1); w >= 0; w = NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w)))) if(!visited[w]) DFS(G,w); // 对v的尚未访问的邻接点w递归调用DFS } // 对图G作深度优先遍历。 void DFSTraverse(ALGraph G,void(*Visit)(char*)) { int v; // 使用全局变量VisitFunc,使DFS不必设函数指针参数 VisitFunc = Visit; for(v = 0; v < G.vexnum; v++) visited[v] = 0; // 访问标志数组初始化 for(v = 0; v < G.vexnum; v++) if(!visited[v]) DFS(G,v); // 对尚未访问的顶点调用DFS printf( ); } // 构造一个空队列Q。 int InitQueue(LinkQueue *Q) { (*Q).front = (*Q).rear = (QueuePtr)malloc(sizeof(QNode)); //动态分配一个空间 if(!(*Q).front) exit(0); (*Q).front->next = NULL; //队头指针指向空，无数据域，这样构成了一个空队列 return 1; } // 插入元素e为Q的新的队尾元素。 int EnQueue(LinkQueue *Q, QElemType e) { QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); if( !p ) // 存储分配失败 exit(0); // 生成一个以为e为数据域的队列元素 p->data = e; p->next = NULL; //将该新队列元素接在队尾的后面 (*Q).rear->next = p; (*Q).rear = p; return 1; } // 若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0。 int DeQueue(LinkQueue *Q,QElemType *e) { QueuePtr p; if((*Q).front==(*Q).rear) return 0; p=(*Q).front->next; //队头元素 *e=p->data; (*Q).front->next=p->next; if((*Q).rear==p) (*Q).rear=(*Q).front; free(p); return 1; } // 若Q为空队列,则返回1,否则返回0。 int QueueEmpty(LinkQueue Q) { if(Q.front == Q.rear) return 1; else return 0; } //按广度优先遍历图G。使用辅助队列Q和访问标志数组visited。 void BFSTraverse(ALGraph G,void(*Visit)(char*)) { int v,u,w; VertexType u1,w1; LinkQueue Q; for(v = 0; v < G.vexnum; ++v) visited[v]=0; // 置初值 InitQueue(&Q); // 置空的辅助队列Q for(v = 0; v < G.vexnum; v++) // 如果是连通图,只v=0就遍历全图 if(!visited[v]) // v尚未访问 { visited[v]=1; Visit(G.vertices[v].data); EnQueue(&Q,v); // v入队列 while(!QueueEmpty(Q)) // 队列不空 { DeQueue(&Q,&u); // 队头元素出队并置为u strcpy(u1,*GetVex(G,u)); for(w = FirstAdjVex(G,u1); w >= 0; w = NextAdjVex(G, u1, strcpy(w1, *GetVex(G,w)))) if(!visited[w]) // w为u的尚未访问的邻接顶点 { visited[w] = 1; Visit(G.vertices[w].data); EnQueue(&Q,w); // w入队 } } } printf( ); } // 输出图的邻接表G。 void Display(ALGraph G) { int i; ArcNode *p; switch(G.kind) { case DG: printf(有向图 ); break; case DN: printf(有向网 ); break; case AG: printf(无向图 ); break; case AN: printf(无向网 ); } printf(%d个顶点： ,G.vexnum); for(i = 0; i < G.vexnum; ++i) printf(%s ,G.vertices[i].data); printf( %d条弧(边): , G.arcnum); for(i = 0; i < G.vexnum; i++) { p = G.vertices[i].firstarc; while(p) { if(G.kind <= 1) // 有向 { printf(%s→%s ,G.vertices[i].data, G.vertices[p->adjvex].data); if(G.kind == DN) // 网 printf(:%d , *(p->info)); } else // 无向(避免输出两次) { if(i < p->adjvex) { printf(%s－%s ,G.vertices[i].data, G.vertices[p->adjvex].data); if(G.kind == AN) // 网 printf(:%d ,*(p->info)); } } p=p->nextarc; } printf( ); } } void print(char *i) { printf(%s ,i); } int main() { int i,j,k,n; ALGraph g; VertexType v1,v2; printf(请选择有向图 ); CreateGraph(&g); Display(g); printf(删除一条边 |