开发工具:
文件大小: 6kb
下载次数: 0
上传时间: 2015-01-09
详细说明： 数据结构中图的相关操作 C语言 #include #include #include #define MAXVEX 100 typedef char VertexType[3]; 定义VertexType为char数组类型 typedef struct vertex { int adjvex; 顶点编号 VertexType data; 顶点的信息 } VType; 顶点类型 typedef struct graph { int n e; n为实际顶点数 e为实际边数 VType vexs[MAXVEX]; 顶点集合 int edges[MAXVEX][MAXVEX]; 边的集合 } AdjMatix; 图的邻接矩阵类型 typedef struct edgenode { int adjvex; 邻接点序号 int value; 边的权值 struct edgenode next; 下一条边的顶点 } ArcNode; 每个顶点建立的单链表中结点的类型 typedef struct vexnode { VertexType data; 结点信息 ArcNode firstarc; 指向第一条边结点 } VHeadNode; 单链表的头结点类型 typedef struct { int n e; n为实际顶点数 e为实际边数 VHeadNode adjlist[MAXVEX]; 单链表头结点数组 } AdjList; 图的邻接表类型 int visited[MAXVEX]; void DispAdjList AdjList G { int i; int in[G >n] out[G >n]; for i 0;in;i++ {in[i] 0 out[i] 0; } ArcNode p; printf "图的邻接表表示如下: n" ; for i 0;in;i++ { printf " 结点 [%d %3s] >" i G >adjlist[i] data ; p G >adjlist[i] firstarc; while p NULL { out[i]++; 对于结点的出度加1 in[p >adjvex] ++; 邻接表中的结点的序号所在的结点的入度 加1 printf " %d >" p >adjvex ; p p >next; } printf "∧ n" ; } for i 0;in;i++ { printf " 结点 [%d %3s]的度 ：%d n" i G >adjlist[i] data in[i]+out[i] ; } } void MatToList AdjMatix g AdjList &G 算法:将邻接矩阵g转换成邻接表G { int i j; ArcNode p; G AdjList malloc sizeof AdjList ; for i 0;iadjlist[i] firstarc NULL; strcpy G >adjlist[i] data g vexs[i] data ; } for i 0;i 0;j if g edges[i][j] 0 邻接矩阵的当前元素不为0 { p ArcNode malloc sizeof ArcNode ; 创建一个结点 p p >value g edges[i][j];p >adjvex j; p >next G >adjlist[i] firstarc; 将 p链到链表后 G >adjlist[i] firstarc p; } G >n g n;G >e g e; } void DFS AdjList g int vi 对邻接表G从顶点vi开始进行深度优先遍历 { ArcNode p; printf "下标%d结点%3s >" vi g >adjlist[vi] data ; 访问vi顶点 visited[vi] 1; 置已访问标识 p g >adjlist[vi] firstarc; 找vi的第一个邻接点 while p NULL 找vi的所有邻接点 { if visited[p >adjvex] 0 DFS g p >adjvex ; 从vi未访问过的邻接点出发深度优先搜索 p p >next; 找vi的下一个邻接点 } } void DFS1 AdjList G int vi 非递归深度优先遍历算法 { ArcNode p; ArcNode St[MAXVEX]; int top 1 v; printf "%d > " vi ; 访问vi顶点 visited[vi] 1; 置已访问标识 top++; 将初始顶点vi的firstarc指针进栈 St[top] G >adjlist[vi] firstarc; while top> 1 栈不空循环 { p St[top];top ; 出栈一个顶点为当前顶点 while p NULL 循环搜索其相邻顶点 { v p >adjvex; 取相邻顶点的编号 if visited[v] 0 若该顶点未访问过 { printf "%d > " v ; 访问v顶点 visited[v] 1; 置访问标识 top++; 将该顶点的第1个相邻顶点进栈 St[top] G >adjlist[v] firstarc; break; 退出当前顶点的搜索 } p p >next; 找下一个相邻顶点 } } } void BFS AdjList G int vi 对邻接表g从顶点vi开始进行广宽优先遍历 { int i v; int Qu[MAXVEX] front 0 rear 0; 循环队列 ArcNode p; printf "%d > " vi ; 访问初始顶点 visited[vi] 1; 置已访问标识 rear rear 1 %MAXVEX; 循环移动队尾指针 Qu[rear] vi; 初始顶点进队 while front rear 队列不为空时循环 { front front+1 % MAXVEX; v Qu[front]; 顶点v出队 p G >adjlist[v] firstarc; 找v的第一个邻接点 while p NULL 找v的所有邻接点 { if visited[p >adjvex] 0 未访问过则访问之 { visited[p >adjvex] 1; 置已访问标识 printf "%d > " p >adjvex ; 访问该点并使之入队列 rear rear+1 % MAXVEX; 循环移动队尾指针 Qu[rear] p >adjvex; 顶点p >adjvex进队 } p p >next; 找v的下一个邻接点 } } } int main { int i j; AdjMatix g; AdjList G; int a[5][5] {{0 1 0 1 0} {1 0 1 0 0} {0 1 0 1 1} {1 0 1 0 1} {0 0 1 1 0}}; char vname[MAXVEX] {"a" "b" "c" "d" "e"}; g n 5;g e 6; 连通图 int a[5][5] {{0 1 0 1 0} {1 0 1 0 0} {0 1 0 1 0} {1 0 1 0 0} {0 0 0 0 0}}; char vname[MAXVEX] {"a" "b" "c" "d" "e"}; g n 5;g e 4; 非连通图 int a[4][4] {{0 1 1 1} {1 0 1 1} {1 1 0 1} {1 1 1 0}}; char vname[MAXVEX] {"a" "b" "c" "d"}; g n 5;g e 12; int a[5][5] {{0 1 1 1 0} {1 0 1 1 1} {1 1 0 1 0} {1 1 1 0 1} {0 1 0 1 0}}; char vname[MAXVEX] {"a" "b" "c" "d" "e"}; g n 5;g e 16; 建立图的无向图 每1条无向边算为2条有向边 int a[6][6] { p151 图7 22的代价矩阵改成的邻接矩阵 {0 1 1 0 1 0} {0 0 1 0 1 0} {1 0 0 1 0 0} {0 1 0 0 1 0} {0 0 0 1 0 0} {0 0 0 1 0 0}}; char vname[MAXVEX] {"v0" "v1" "v2" "v3" "v4" "v5"}; g n 6;g e 11; for i 0;i数据结构中图的相关操作 C语言 #include #include #include #define MAXVEX 100 typedef char VertexType[3]; 定义VertexType为char数组类型 typedef struct vertex { int adjvex; 顶点编号 VertexType data; 顶 [更多] ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
