邻接矩阵存图
存储结构定义
#define MaxSize 10 // 图中最多顶点个数
typedef char DataType;
typedef strcut{
DataType vertex[MaxSize];
int edge[MaxSize][MaxSize];
int vertexNum, edgeNum;
} Mgraph;
建图
void CreateGraph(Mgraph *G, DataType a[], int n, int m){
G->vertex=n, G->edgeNum=m;
for(int i=0; i<n; i++) G->vertex[i]=a[i];
for(int i=0; i<m; i++) for(int j=0; j<m; j++) G->edge[i][j]=0; // 初始化
for(int i=0; i<m; i++){
int x, y;
scanf("%d%d", &x, &y);
G->edge[x][y]=G->edge[y][x]=1; // 存边
}
}
遍历
dfs
void dfs(Mgraph *G, int u){ // 全局变量数组 st[n] 初始化为 0
printf("%c ", G->vertex[u]);
st[u]=true;
for(int v=0; v<G->vertexNum; v++){
if(G->vertex[u][v]==1 && st[v]==0)
dfs(G, v);
}
}
bfs
void bfs(Mgraph *G, int root){ // 全局变量数组 st[n] 初始化为 0
int Q[MaxSize];
int front=-1, rear=-1;
printf("%c ", G->vertex[root]);
Q[++rear]=root, st[root]=1;
while(front != rear){
int u=Q[front++];
for(int v=0; v<G->vertexNum; v++)
if(G->edge[i][j]==1 && st[v]==0){
printf("%c ", G->vertex[v]);
Q[++rear]=v, st[v]=1;
}
}
}
文章来源地址https://www.toymoban.com/news/detail-803865.html
文章来源:https://www.toymoban.com/news/detail-803865.html
到了这里,关于第五章 图论 邻接矩阵存图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!