圖的基本運(yùn)算及智能交通中的最佳路徑選擇問(wèn)題

完成鄰接矩陣的初始化、撤銷和邊的搜索、插入、刪除等操作

#include <stdio.h> #include <stdlib.h>#define ERROR 0 #define OK 1 #define Overflow 2 //表示上溢 #define Underflow 3 //表示下溢 #define NotPresent 4 //表示元素不存在 #define Duplicate 5 //表示有重復(fù)元素 typedef int Status; typedef int ElemType; //圖的鄰接矩陣結(jié)構(gòu)體 typedef struct mGraph {ElemType **a; //鄰接矩陣int n; //圖的當(dāng)前頂點(diǎn)數(shù)int e; //圖的當(dāng)前邊數(shù)ElemType noEdge; //兩頂點(diǎn)間無(wú)邊時(shí)的值 }mGraph;//鄰接矩陣的初始化 Status Init(mGraph *mg, int nSize, ElemType noEdgeValue) {int i, j;mg->n = nSize; //初始化頂點(diǎn)數(shù)mg->e = 0; //初始化沒(méi)有邊mg->noEdge = noEdgeValue; //初始化時(shí)沒(méi)有邊時(shí)的取值mg->a = (ElemType **)malloc(nSize * sizeof(ElemType *)); //動(dòng)態(tài)生成長(zhǎng)度為n的一維指針數(shù)組if(!mg->a)return ERROR;for (i = 0; i < mg->n; i++) //動(dòng)態(tài)生成二位數(shù)組{mg->a[i] = (ElemType *)malloc(nSize * sizeof(ElemType));for ( j = 0; j < mg->n; j++)mg->a[i][j] = mg->noEdge;mg->a[i][i] = 0;}return OK; }//鄰接矩陣的撤銷 void Destroy(mGraph *mg) {int i;mg->n = 0;mg->e = 0;for(i = 0; i < mg->n; i++)free(mg->a[i]);free(mg->a); }//邊的搜索 Status Exit(mGraph *mg, int u, int v) {if(u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v || mg->a[u][v] == mg->noEdge)return ERROR;return OK; }//邊的插入 Status Insert (mGraph * mg, int u, int v, ElemType w) {if(u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v)return ERROR;if(mg->a[u][v] != mg->noEdge)return Duplicate; //若待插入邊已存在， 則返回錯(cuò)誤信息mg->a[u][v] = w;mg->e++;return OK; }//邊的刪除 Status Remove(mGraph *mg, int u, int v) {if(u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v)return ERROR;if(mg->a[u][v] == mg->noEdge)return NotPresent; //待刪除邊不存在mg->a[u][v] = mg->noEdge;mg->e--;return OK; }int main() {mGraph mg;mg.n = 0;mg.e = 0;int m, n, u, v, w, a, b; //n頂點(diǎn)個(gè)數(shù)， m邊的個(gè)數(shù)int choice;printf("請(qǐng)輸入你想要的功能：\n0. 退出。\n1.創(chuàng)建鄰接矩陣。\n2.查詢邊的權(quán)重。\n3.撤銷鄰接矩陣。\n4.刪除邊\n");while (1){printf("\n請(qǐng)輸入你的選擇:");scanf("%d", &choice);if(choice == 0){if (mg.n)printf("所創(chuàng)建鄰接矩陣未撤銷，請(qǐng)撤銷后退出!!!\n");elsebreak;}switch (choice){case 1:if(mg.n){printf("已經(jīng)創(chuàng)建鄰接矩陣，請(qǐng)撤銷后，重新創(chuàng)建。\n");break;}printf("請(qǐng)輸入頂點(diǎn)個(gè)數(shù):");scanf("%d", &n);Init(&mg, n, 0);printf("請(qǐng)輸入插入邊的個(gè)數(shù):");scanf("%d", &m);for (int i = 0; i < m; i++){printf("請(qǐng)輸入第%d條邊插入邊的起點(diǎn)、終點(diǎn)以及邊權(quán):", i + 1);scanf("%d%d%d", &u, &v, &w);Insert(&mg, u, v, w);}break;case 2:if(!mg.n){printf("未創(chuàng)建鄰接矩陣，請(qǐng)創(chuàng)建后查詢。\n");break;}printf("請(qǐng)輸入查詢邊的起點(diǎn)及終點(diǎn)：");scanf("%d%d", &a, &b);if (Exit(&mg, a, b))printf("該邊的邊權(quán)為：%d\n", mg.a[a][b]);elseprintf("該邊不存在\n");break;case 3:if(!mg.n){printf("未創(chuàng)建鄰接矩陣，請(qǐng)創(chuàng)建后撤銷。\n");break;}Destroy(&mg);printf("已撤銷");break;case 4:if(!mg.n){printf("未創(chuàng)建鄰接矩陣，請(qǐng)創(chuàng)建。\n");break;}printf("請(qǐng)輸入刪除邊的起點(diǎn)及終點(diǎn)：");scanf("%d%d", &a, &b);if(Remove(&mg, a, b))printf("刪除成功。\n");elseprintf("該邊不存在。\n");break;default:printf("請(qǐng)正確輸入選項(xiàng)。\n");break;}}system("pause");return 0;}

圖的寬度遍歷和深度遍歷

//隊(duì)列結(jié)構(gòu)體 typedef struct queue {int front;int rear;int maxSize;int *element; }queue; //初始化隊(duì)列 void initqueue(queue *q, int msize) {q->maxSize = msize;q->element = (int *)malloc(msize * sizeof(int));q->front = q->rear = 0; } //入隊(duì)列 int enqueue(queue * q, int m) {if ((q->rear + 1) % q->maxSize == q->front){printf("隊(duì)列已滿");return ERROR;}q->rear = (q->rear + 1) % q->maxSize;q->element[q->rear] = m;return OK; } //判斷是否為空 int isEmpty(queue * q) {return q->front == q->rear; } //出隊(duì)列，返回隊(duì)首 int dequeue(queue * q) {if (isEmpty(q)){printf("隊(duì)列為空");return ERROR;}q->front = (q->front + 1) % q->maxSize;return q->element[q->front]; }//圖的深度優(yōu)先遍歷 void DFS(int v, int visited[], mGraph *mg) {visited[v] = 1;printf("%d ", v);for (int i = 0; i < mg->n; i++){if (mg->a[v][i] != mg->noEdge && visited[i] != 1)DFS(i, visited, mg);} }void DFSGraph(mGraph * mg) {int * visited = (int *)malloc(mg->n);for (int i = 0; i < mg->n; i++)visited[i] = 0;for (int i = 0; i < mg->n; i++)if (!visited[i])DFS(i, visited, mg);free(mg); }//寬度優(yōu)先遍歷 void BFS(int v, int visited[], mGraph *mg) {queue q;initqueue(&q, mg->n);visited[v] = 1;printf("%d ", v);enqueue(&q, v);while (isEmpty(&q)){v = dequeue(&q);for (int i = 0; i < mg->n; i++){if (mg->a[v][i] != mg->noEdge && visited[i] != 1){visited[i] = 1;printf("%d ", i);enqueue(&q, i);}}}} void BFSGraph(mGraph *mg) {int * visited = (int *)malloc(mg->n);for (int i = 0; i < mg->n; i++)visited[i] = 0;for (int i = 0; i < mg->n; i++)if (!visited[i]) BFS(i, visited, mg);free(visited); }

鄰接表實(shí)現(xiàn)上訴的功能

#include<stdio.h> #include<stdlib.h>typedef int ElemType;//循環(huán)隊(duì)列的結(jié)構(gòu)體定義 typedef struct{int front;int rear;int maxSize; //最大容量ElemType *element; }Queue;//創(chuàng)建一個(gè)能容納mSize個(gè)單元的空隊(duì)列 void Create(Queue *Q,int mSize){Q->maxSize=mSize;Q->element=(ElemType*)malloc(sizeof(ElemType)*mSize);Q->front=Q->rear=0; }//判斷隊(duì)列是否為空,若是,則返回TRUE;否則返回FALSE int IsEmpty(Queue *Q){return Q->front==Q->rear; }//判斷隊(duì)列是否已滿,若是,則返回TRUE,否則返回FALSE int IsFULL(Queue *Q){return (Q->rear+1)%Q->maxSize==Q->front; }//獲取隊(duì)頭元素,并通過(guò)x返回.若操作成功,則返回TRUE,否則返回FALSE int Front(Queue *Q,ElemType *x){if(IsEmpty(Q)) //空隊(duì)列處理return 0;*x=Q->element[(Q->front+1)%Q->maxSize]; }//入隊(duì).在隊(duì)列Q的隊(duì)尾插入元素x(入隊(duì)操作)。操作成功,則返回TRUE,否則返回FALSE int EnQueue(Queue *Q,ElemType x){if(IsFULL(Q)) //溢出處理return 0;Q->rear=(Q->rear+1)%Q->maxSize;Q->element[Q->rear]=x;return 1; }//出隊(duì).從隊(duì)列Q中刪除隊(duì)頭元素(出隊(duì)操作)。操作成功,則返回TRUE,否則返回FALSE int DeQueue(Queue *Q){if(IsEmpty(Q)){ //空隊(duì)列處理return 0;}Q->front=(Q->front+1)%Q->maxSize;return 1; }//鄰接表定義 typedef struct eNode{int adjVex;ElemType w;struct eNode* nextArc; }ENode; typedef struct lGraph{int n;int e;ENode **a; }LGraph;//初始化 typedef int Status; Status Init(LGraph *lg,int nSize) {int i;lg->n=nSize;lg->e=0;lg->a=(ENode**)malloc(nSize*sizeof(ENode*));if(!lg->a)return 0;else{for(i=0;i<lg->n;i++) lg->a[i]=NULL;return 1;} }//鄰接表的撤銷 void Destory(LGraph *lg) {int i;ENode *p,*q;for(i=0;i<lg->n;i++){p=lg->a[i];q=p;while(p) {p=p->nextArc;free(q);q=p;}}free(lg->a); }//邊的搜索 Status Exist(LGraph *lg,int u,int v) {ENode* p;if(u<0||v<0||u>lg->n-1||v>lg->n-1||u==v)return 0;p=lg->a[u];while(p&&p->adjVex!=v) p=p->nextArc;if(!p) return 0;else return 1; }//邊的插入 Status Insert(LGraph *lg,int u,int v,ElemType w) {ENode *p;if(u<0||v<0||u>lg->n-1||v>lg->n-1||u==v) return 0;if(Exist(lg,u,v)) return 5;p=(ENode *)malloc(sizeof(ENode));p->adjVex=v;p->w=w;p->nextArc=lg->a[u];lg->a[u]=p;lg->e++;return 1; }//邊的刪除 Status Remove(LGraph *lg,int u,int v) {ENode *p,*q;if(u<0||v<0||u>lg->n-1||v>lg->n-1||u==v)return 0;p=lg->a[u];q=NULL;while(p&&p->adjVex!=v){q=p;p=p->nextArc;}if(!p) return 4;if(q) q->nextArc=p->nextArc ;free(p);lg->e--;return 1; }//深度優(yōu)先遍歷 void DFS(int v,int visited[],LGraph g) {ENode *w;printf("%d",v);visited[v]=1;for(w=g.a[v];w;w=w->nextArc)if(!visited[w->adjVex ])DFS(w->adjVex,visited,g); } void DFEGraph(LGraph g) {int i;int *visited=(int*)malloc(g.n*sizeof(int));for(i=0;i<g.n;i++)visited[i]=0;for(i=0;i<g.n;i++)if(!visited[i]) DFS(i,visited,g);free(visited); }//寬度優(yōu)先遍歷 void BFS(int v,int visited[],LGraph g) {ENode *w;Queue q;Create(&q,g.n);visited[v]=1;printf("%d",v);EnQueue(&q,v);while(!IsEmpty(&q)){Front(&q,&v);DeQueue(&q);for(w=g.a[v];w;w=w->nextArc)if(!visited[w->adjVex]){visited[w->adjVex]=1;printf("%d",w->adjVex);EnQueue(&q,w->adjVex);}} } void BFSGraph(LGraph g) {int i;int *visited=(int *)malloc(g.n*sizeof(int));for(int i=0;i<g.n;i++)visited[i]=0;for(i=0;i<g.n;i++)if(!visited[i]) BFS(i,visited,g);free(visited); }//主函數(shù) void main() {int n;LGraph lg;printf("Please input the num of the node:");scanf("%d",&n);Init(&lg,n);printf("please input the num of the edge:");scanf("%d",&n);int u,v,w;for(int i=0;i<n;i++){printf("Please input the edge:");scanf("%d%d%d",&u,&v,&w);Insert(&lg,u,v,w);}printf("DFS:");DFEGraph(lg);printf("\nBFS:");BFSGraph(lg);printf("\n");}

實(shí)現(xiàn)智能交通的最佳選擇

#include<stdio.h> #include<stdlib.h>typedef int ElemType;//鄰接表定義 typedef struct eNode{int adjVex;ElemType w;struct eNode* nextArc; }ENode; typedef struct lGraph{int n;int e;ENode **a; }LGraph;//初始化 typedef int Status; Status Init(LGraph *lg,int nSize) {int i;lg->n=nSize;lg->e=0;lg->a=(ENode**)malloc(nSize*sizeof(ENode*));if(!lg->a)return 0;else{for(i=0;i<lg->n;i++) lg->a[i]=NULL;return 1;} }//鄰接表的撤銷 void Destory(LGraph *lg) {int i;ENode *p,*q;for(i=0;i<lg->n;i++){p=lg->a[i];q=p;while(p) {p=p->nextArc;free(q);q=p;}}free(lg->a); }//邊的搜索 Status Exist(LGraph *lg,int u,int v) {ENode* p;if(u<0||v<0||u>lg->n-1||v>lg->n-1||u==v)return 0;p=lg->a[u];while(p&&p->adjVex!=v) p=p->nextArc;if(!p) return 0;else return 1; }//邊的插入 Status Insert(LGraph *lg,int u,int v,ElemType w) {ENode *p;if(u<0||v<0||u>lg->n-1||v>lg->n-1||u==v) return 0;if(Exist(lg,u,v)) return 5;p=(ENode *)malloc(sizeof(ENode));p->adjVex=v;p->w=w;p->nextArc=lg->a[u];lg->a[u]=p;lg->e++;return 1; }//邊的刪除 Status Remove(LGraph *lg,int u,int v) {ENode *p,*q;if(u<0||v<0||u>lg->n-1||v>lg->n-1||u==v)return 0;p=lg->a[u];q=NULL;while(p&&p->adjVex!=v){q=p;p=p->nextArc;}if(!p) return 4;if(q) q->nextArc=p->nextArc ;free(p);lg->e--;return 1; }//智能交通 void ITS(int o,int d,int j,int *B,int r[],int b[],int W[],int (*R)[50],LGraph g) {ENode *w;r[j]=o;j++;for(w=g.a[o];w;w=w->nextArc){if(w->adjVex==d){W[j-1]=w->w;r[j]=w->adjVex;int sum=0;int i=0;for(i=0;i<j;i++){sum+=W[i];R[*B][i]=r[i];}R[*B][i]=r[i];b[*B]=sum;*B+=1;continue;}int i=0;int judge=1;while(r[i]!=0){if(r[i]==w->adjVex)judge=0;i++;}if(judge){W[j-1]=w->w;ITS(w->adjVex,d,j,B,r,b,W,R,g);}} } void ITSGraph(LGraph g) {int i;int *route=(int*)malloc(g.n*g.n*sizeof(int));//記錄路徑for(i=0;i<g.n;i++)route[i]=-1;int *best=(int*)malloc(g.n*sizeof(int));for(i=0;i<g.n;i++)best[i]=0;int *W=(int*)malloc(g.n*sizeof(int));for(i=0;i<g.n;i++)W[i]=0;int R[50][50];for(int i=0;i<50;i++)for(int j=0;j<50;j++)R[i][j]=-1;int o,d;printf("please input the origin and destination:");scanf("%d%d",&o,&d);int B=0;ITS(o,d,0,&B,route,best,W,R,g);int temp=best[0];for(int i=1;i<B;i++){if(temp>best[i])temp=best[i];}printf("the best way is:\n");for(int i=0;i<B;i++){if(temp==best[i]){int p=0;while(R[i][p]!=-1){printf("%d",R[i][p]);p++;if(R[i][p]!=-1)printf("->");}printf("\n");}}printf("cost:%d\n",temp);free(W);free(best);free(route); }//主函數(shù) void main() {int n;LGraph lg;//printf("Please input the num of the node:"); // scanf("%d",&n);Init(&lg,6);/*printf("please input the num of the edge:");scanf("%d",&n);int u,v,w;for(int i=0;i<n;i++){printf("Please input the edge:");scanf("%d%d%d",&u,&v,&w);Insert(&lg,u,v,w);}*/int w=1;Insert(&lg,1,3,w);Insert(&lg,1,2,w);Insert(&lg,0,1,w);Insert(&lg,3,2,w);Insert(&lg,3,0,w);Insert(&lg,2,0,w);Insert(&lg,5,1,w);Insert(&lg,5,3,w);Insert(&lg,4,0,w);Insert(&lg,4,2,w);ITSGraph(lg); }\

總結(jié)

以上是生活随笔為你收集整理的图的基本运算及智能交通中的最佳路径选择问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。