--数据结构--图

本站首页 管理页面写新日志退出

« November 2025 »
日一二三四五六
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30

公告

暂无公告...

我的分类（专题）

首页(32)
WINDOWS(3)

日志更新

10年IT老兵跳槽到银行1年后的体会
劳动纠纷2
劳动纠纷1
中国人力资源总监谈如何折腾毕业生（转）
辞职报告(转)
匈牙利命名法
数据库设计三大范式应用实例剖析
C语言指针的奥秘
C++类库介绍
VC 界面库皮肤库

留言板

签写新留言

链接

半生江湖半生梦，两江风月两江情

Blog信息

blog名称:
日志总数:32
评论数量:44
留言数量:0
访问次数:180591
建立时间:2005年1月4日

数据结构--图
文章收藏

eaglebetter 发表于 2006/8/6 0:24:55

　7-1 图的定义和术语7-1-1 图的定义7-1-2 图的相关术语无向图（Undigraph）有向图（Digraph）无向完全图有向完全图稠密图、稀疏图顶点的度权网——边（或弧）上带权的图称为网（Network）路径、路径长度回路、简单路径、简单回路子图连通图、连通分量强连通图、强连通分量生成树7-1-3 图的基本操作7-2 图的存储表示7-2-1 邻接矩阵#define MAXLEN 10typedef struct{char vexs[MAXLEN];int edges[MAXLEN][MAXLEN];int n,e;}MGraph;建立一个图的邻接矩阵存储的算法如下：void CreateMGraph(MGraph *G){ int i,j,k;char ch1,ch2;printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");scanf("%d,%d",&(G->n),&(G->e));printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");for(i=0;i<G->n;i++){getchar();scanf("%c",&(G->vexs[i]));}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0;printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n");for(k=0;k<G->e;k++){getchar();printf("请输入第%d条边的顶点序号：",k+1);scanf("%c,%c",&ch1,&ch2);for(i=0;ch1!=G->vexs[i];i++);for(j=0;ch2!=G->vexs[j];j++);G->edges[i][j]=1;}}7-2-2 邻接表＃define MAXLEN 10 // 最大顶点数为10 typedef struct node{ // 边表结点 int adjvex; // 邻接点域 struct node * next; // 指向下一个邻接点的指针域 //若要表示边上信息，则应增加一个数据域info }EdgeNode; typedef struct vnode{ // 顶点表结点 VertexType vertex; // 顶点域 EdgeNode * firstedge; // 边表头指针 }VertexNode; typedef VertexNode AdjList[MAXLEN]; // AdjList是邻接表类型 typedef struct{ AdjList adjlist; // 接表 int n,e; // 顶点数和边数 }ALGraph; // ALGraph是以邻接表方式存储的图类型建立一个有向图的邻接表存储的算法如下： void CreateGraphAL (ALGraph *G) { int i,j,k; EdgeNode * s; printf("请输入顶点数和边数(输入格式为:顶点数,边数)：\n"); scanf("%d,%d",&(G->n),&(G->e)); // 读入顶点数和边数 printf("请输入顶点信息(输入格式为:顶点号<CR>)每个顶点以回车作为结束:\n"); for (i=0;i<G->n;i++) // 立有n个顶点的顶点表 { scanf("\n%c",&(G->adjlist[i].vertex)); // 读入顶点信息 G->adjlist[i].firstedge=NULL; // 点的边表头指针设为空 } printf("请输入边的信息(输入格式为:i,j)：\n"); for (k=0;k<G->e;k++) // 建立边表 { scanf("\n%d,%d",&i,&j); // 读入边<Vi,Vj>的顶点对应序号 s=new EdgeNode; // 生成新边表结点s s->adjvex=j; // 邻接点序号为j s->next=G->adjlist[i].firstedge; // 将新边表结点s插入到顶点Vi的边表头部 G->adjlist[i].firstedge=s; }}7-3 图的遍历7-3-1 深度优先搜索void DFSTraverseM(MGraph *G){int i;for(i=0;i<G->n;i++)visited[i]=FALSE; // FALSE在c语言中定义为0，以下同for(i=0;i<G->n;i++)if(!visited[i]) DFSM(G,i);} void DFSM(MGraph *G,int i){int j;printf("\t\t深度优先遍历结点: 结点%c\n",G->vexs[i]);visited[i]=TRUE; // TRUE在c语言中定义为0，以下同for(j=0;j<G->n;j++)if(G->edges[i][j]==1&&!visited[j])DFSM(G,j);}7-3-2 广度优先搜索void BFSTraverseM(MGraph *G){int i;for (i=0;i<G->n;i++)visited[i]=FALSE;for (i=0;i<G->n;i++)if (!visited[i]) BFSM(G,i);}void BFSM(MGraph *G,int k){ int i,j;CirQueue Q;InitQueue(&Q);printf("广度优先遍历结点: 结点%c\n",G->vexs[k]);visited[k]=TRUE;EnQueue(&Q,k);while (!QueueEmpty(&Q)){i=DeQueue(&Q);for (j=0;j<G->n;j++)if(G->edges[i][j]==1&&!visited[j]){printf("广度优先遍历结点:%c\n",G->vexs[j]);visited[j]=TRUE;EnQueue(&Q,j);}}}7-4 图的连通性7-4-1 无向图的连通分量和生成树7-4-2 最小生成树1．最小生成树的基本概念2．常用的构造最小生成树的方法构造最小生成树的Prim算法构造最小生成树的Kruskal算法7-5 最短路径小结实验7 图子系统1．实验目的2．实验内容3．操作举例4．参考程序#define MAXLEN 10#include <stdio.h>#define FALSE 0#define TRUE 1#define Error printf#define QueueSize 30typedef struct{char vexs[MAXLEN];int edges[MAXLEN][MAXLEN];int n,e;}MGraph;int visited[10];void CreateMGraph(MGraph *G);void DFSTraverseM(MGraph *G);void BFSTraverseM(MGraph *G);void DFSM(MGraph *G,int i);void BFSM(MGraph *G,int i);typedef struct{ int front;int rear; int count; int data[QueueSize];}CirQueue;void InitQueue(CirQueue *Q){Q->front=Q->rear=0; Q->count=0;}int QueueEmpty(CirQueue *Q){return Q->count=QueueSize;}int QueueFull(CirQueue *Q){return Q->count==QueueSize;}void EnQueue(CirQueue *Q,int x){ if (QueueFull(Q))Error("Queue overflow"); else { Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize; }}int DeQueue(CirQueue *Q){int temp; if(QueueEmpty(Q)){ Error("Queue underflow");return NULL;}else{temp=Q->data[Q->front];Q->count--;Q->front=(Q->front+1)%QueueSize;return temp;}}void main(){MGraph *G,a; char ch1; int i,j,ch2; G=&a; printf("\n\t\t建立一个有向图的邻接矩阵表示\n"); CreateMGraph(G); printf("\n\t\t已建立一个图的邻矩阵存储\n\t\t"); for(i=0;i<G->n;i++){ for(j=0;j<G->n;j++)printf("%5d",G->edges[i][j]);printf("\n\t\t"); }getchar();ch1='y';while(ch1=='y'||ch1=='Y'){printf("\n\n\n\n\n\t\t图子系统\n");printf("\t\t*****************************************\n");printf("\t\t* 1-------更新邻接矩阵 *\n");printf("\t\t* 2-------深度优先遍历 *\n");printf("\t\t* 3-------广度优先遍历 *\n");printf("\t\t* 0-------退出 *\n");printf("\t\t*****************************************\n");printf("\t\t请选择菜单号(0--3):");scanf("%d",&ch2); getchar();switch(ch2){case 1:CreateMGraph(G);printf("\t\t\t图的邻接矩阵存储建立完毕.\n");break;case 2:DFSTraverseM(G);break;case 3:BFSTraverseM(G);break;case 0:ch1='n';break;default:printf("\t\t输入错误！请重新输入！\n");}}}void CreateMGraph(MGraph *G){ int i,j,k;char ch1,ch2;printf("\t\t请输入顶点数和边数(输入格式为:顶点数,边数):\n\t\t");scanf("%d,%d",&(G->n),&(G->e));printf("\t\t请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:\n");for(i=0;i<G->n;i++){ getchar();printf("\t\t");scanf("%c",&(G->vexs[i]));}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0;printf("\t\t请输入每条边对应的两个顶点的序号(输入格式为:i,j):\n");for(k=0;k<G->e;k++){ getchar();printf("\t\t请输入第%d条边的顶点序号：",k+1);scanf("%c,%c",&ch1,&ch2);for(i=0;ch1!=G->vexs[i];i++);for(j=0;ch2!=G->vexs[j];j++);G->edges[i][j]=1;}}void DFSTraverseM(MGraph *G){int i; for(i=0;i<G->n;i++)visited[i]=FALSE; for(i=0;i<G->n;i++)if(!visited[i]) DFSM(G,i);}void BFSTraverseM(MGraph *G){int i;for (i=0;i<G->n;i++)visited[i]=FALSE;for (i=0;i<G->n;i++)if (!visited[i]) BFSM(G,i);}void DFSM(MGraph *G,int i){int j;printf("\t\t深度优先遍历结点: 结点%c\n",G->vexs[i]);visited[i]=TRUE;for(j=0;j<G->n;j++)if(G->edges[i][j]==1&&!visited[j])DFSM(G,j);}void BFSM(MGraph *G,int k){ int i,j;CirQueue Q;InitQueue(&Q);printf("\t\t广度优先遍历结点: 结点%c\n",G->vexs[k]);visited[k]=TRUE;EnQueue(&Q,k);while (!QueueEmpty(&Q)){ i=DeQueue(&Q);for (j=0;j<G->n;j++)if(G->edges[i][j]==1&&!visited[j]){ printf("\t\t广度优先遍历结点:%c\n",G->vexs[j]);visited[j]=TRUE;EnQueue(&Q,j);}}}

阅读全文(7646) | 回复(6) | 编辑 | 精华

回复:数据结构--图
文章收藏

丑小鸭(游客)发表评论于2008/12/9 16:07:42

不错顶

个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:数据结构--图
文章收藏

D (游客)发表评论于2007/1/16 13:34:40

我要的是图的定义，可是在这里我确看不到图的定义啊，谁能不能告诉我图的定义啊，要快啊，望个位能帮帮忙我就在这里先谢过了！

个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:数据结构--图
文章收藏

麻辣烫(游客)发表评论于2007/1/16 11:07:12

程序不错，帮了大忙