考研数据结构-图的相关应用算法
124 浏览量
2022-11-14
11:04:14
上传
评论 2
收藏 403KB PDF 举报
CSDN 博主：住在阳光的心里
图的相关应用算法
一、图的存储结构
（一）邻接矩阵
#define MaxVertexNum 100 //顶点数目的最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表；
int vexnum, arcnum; //图的当前顶点数和弧数
}MGraph;
（二）邻接表
#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode{ //边表结点
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
InfoType info; //网的边权值
}ArcNode;
typedef struct VNode{ //顶点表结点
VertexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];
typedef struct{
AdjList vertices; //邻接表
int vexnum, arcnum; 图的顶点数和弧数
}AGraph;
二、图的遍历方式
（一）DFS
bool visited[MaxVertexNum]; //标记访问数组
void DFSTraverse(Graph G){ //对图 G 进行深度优先遍历
for(v = 0; v < G.vexnum; ++v){ // v 为起始顶点
visited[v] = FALSE; //初始化已访问标记数据
}
for(v = 0; v < G.vexnum; ++v){
if(!visited[v])
DFS(G, v);
}
}
剩余15页未读，继续阅读
资源评论
