不同的存储结构所采用的实现方法有所区别,这里优先理解思想
后续会更新具体实现图以及实现方法
以下是实现代码
#include<stdio.h> #define NumOfVertex 200 #define VertexType int int visited[NumOfVertex]; typedef enum{Digraph,Undigraph,DirectedNet,UndirectedNet}GraphKind; typedef struct{ int relation; //无权图用01表示是否相连接 网直接表示权重 //Info; }rlt,rltionMatrix[NumOfVertex][NumOfVertex]; typedef struct{ VertexType Vex[NumOfVertex]; //存顶点 int NumOfVex,NumOfArc; //存顶点和边的数量 rltionMatrix Matrix; // 矩阵 GraphKind kind; //图的类型 }MyGraph; //定位顶点在表中位置 int LocateVex(MyGraph*g,VertexType v){ for(int i = 0;i<g->NumOfVex;i++){ if(g->Vex[i]==v) return i; } printf("None"); return -1; } //创建有向图 void CreatDG(MyGraph *g){ int VNum,ANum; scanf("%d %d",&(g->NumOfVex),&(g->NumOfArc)); //存顶点数据 for(int i =0;i<g->NumOfVex;i++) scanf("%d",&(g->Vex[i])); //printf("RUN HERE"); //初始化矩阵全置为0 for(int i =0;i<g->NumOfVex;i++) for(int j = 0;j<g->NumOfVex;j++) { g->Matrix[i][j].relation=0; //info } //构造矩阵 for(int i = 0;i<g->NumOfArc;i++) { int v1,v2; scanf("%d %d", &v1, &v2); int pos1 = LocateVex(g,v1); int pos2 = LocateVex(g,v2); if(pos1==-1||pos2==-1) return; else g->Matrix[pos1][pos2].relation=1; ////无向图的二阶矩阵沿主对角线对称 //网读入权存入矩阵 } } //void CreateGraph(MyGraph* G) { // //选择图的类型 // scanf("%d", &(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; // default: // break; // } //} void printG(MyGraph *g){ for (int i = 0;i<g->NumOfVex;i++){ for(int j = 0;j<g->NumOfVex;j++) { printf(" %d ",g->Matrix[i][j].relation); } printf("\n"); } } //DFS int FindFirstAdjVex(MyGraph *g,int v){ //寻找第一个相邻结点 for(int i = 0;i<g->NumOfVex;i++){ if(g->Matrix[v][i].relation){ return i; } } return -1; //未找到返回-1 } int FineNext(MyGraph *g,int v,int now) //对于数组下标 v 处的顶点,从 now 位置开始继续查找和它相邻的顶点,并返回该顶点的数组下标 { for(int i = now+1;i<g->NumOfVex;i++){ if(g->Matrix[v][i].relation){ return i; } } return -1; } void DFS(MyGraph g,VertexType v){ int i ; printf("%d ",g.Vex[v]); visited[v] = 1; for(i = FindFirstAdjVex(&g,v);i>=0;i = FineNext(&g,v,i)) { if(!visited[i]) DFS(g,i); } //简写 //for(int j = 0;j<g.NumOfVex;j++){ // if(g.Matrix[v][j].relation==1&&!visited[j]) // DFS(g,j); //} } void DFSTraverse(MyGraph g){ for(int i= 0;i<g.NumOfVex;i++) visited[i] = 0; for(int i= 0;i<g.NumOfVex;i++) { if(!visited[i]) DFS(g,i); } } int main(){ MyGraph g; CreatDG(&g); printG(&g); DFSTraverse(g); }
原文地址:http://www.cnblogs.com/konataxzy/p/16897134.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性