本篇内容介绍了“C语言数据结构图如何创建与遍历”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
理解图的基本概念，掌握图的存储结构，实现图的深度优先搜索遍历算法与广度优先搜索遍历算法。
利用邻接矩阵描述示例图，编写程序输出示例图的深度优先搜索和广度优先搜索的遍历序列。
具体步骤如下：
将图的邻接矩阵描述为一个二维数组，并将该数组定义为全局变量，以便数据的传递；
定义一个队列，在广度优先搜索时，该队列存储已被访问的路径长度为1，2，…的顶点；
定义访问函数visit()、深度优先搜索函数DFS()和广度优先搜索函数BFS()；
主函数实现各函数的调用。
Dev-C++
//Authors:xiaobei
#include<stdio.h>
#include<stdlib.h>
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
//定义图结构
typedef struct{
VerTexType vexs[MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;
//定义辅助链队
typedef struct QNode{
char data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//定义全局辅助数组visited[MVNum]
int visited[MVNum];
//函数返回定点下标
int LocateVex(AMGraph G,char v){
int i;
for(i=0;i<G.vexnum;i++)
if(G.vexs[i]==v)
return i;
return -1;
}
//函数访问并输出顶点，返回下标
int visit(AMGraph G,char v){
int i;
for(i=0;i<G.vexnum;i++)
if(v==G.vexs[i])
printf("%c",v);
return LocateVex(G,v);
}
//函数创建无向图，以邻接矩阵形式
int CreateUDN(AMGraph &G){
int i,j,k,v1,v2,w;
printf("[输入总顶点数和边数:]\n>>>");
scanf("%d %d",&G.vexnum,&G.arcnum);
for(i=0;i<G.vexnum;i++)
{
getchar();
printf("[依次输入各顶点的信息:]\n>>>");
scanf("%c",&G.vexs[i]);
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j] = MaxInt;
for(k=0;k<G.arcnum;k++){
getchar();
printf("[输入一条边依附的顶点及权值:]\n>>>");
scanf("%c %c %d",&v1,&v2,&w);
i = LocateVex(G,v1);
j = LocateVex(G,v2);
G.arcs[i][j]=w;
G.arcs[j][i]=G.arcs[i][j];
}
return 1;
}
//函数深度遍历连通图
void DFS_AM(AMGraph G,char v){
int w,u;
u = visit(G,v);
visited[u] = 1;
for(w=0;w<G.vexnum;w++){
if((G.arcs[u][w]<MaxInt) && (!visited[w]))
DFS_AM(G,G.vexs[w]);
}
}
//函数初始化链队
void InitQueue(LinkQueue &Q){
Q.front = Q.rear = (QNode*)malloc(sizeof(QNode));
Q.front->next=NULL;
}
//函数数据进队
void EnQueue(LinkQueue &Q,char e){
QueuePtr p;
p = (QNode*)malloc(sizeof(QNode));
p->data = e;
p->next = NULL;
Q.rear->next=p;
Q.rear = p;
}
//函数数据出队
void DeQueue(LinkQueue &Q,char &e){
QueuePtr p;
if(Q.front==Q.rear);
else
{
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
}
}
//函数判断链队是否为空
int QueueEmpty(LinkQueue Q){
if(Q.front==Q.rear)
return 1;
else
return 0;
}
//函数返回顶点下一个邻接点下标
int FirstAdjVex(AMGraph G,int c){
int j;
for(j=0;j<G.vexnum;j++)
if(G.arcs[c][j]<MaxInt && visited[j]==0)
return j;
return -1;
}
//函数返回顶点下一个相对邻接点下标
int NextAdjVex(AMGraph G,int c,int w){
int j;
for(j=0;j<G.vexnum;j++)
if(G.arcs[c][j]<MaxInt && visited[j]==0)
return j;
return -1;
}
//函数广度遍历连通图
void BFS_AM(AMGraph G,char v){
int c,w,i;
char u;
LinkQueue Q;
c = visit(G,v);
visited[c] = 1;
InitQueue(Q);
EnQueue(Q,v);
while(!QueueEmpty(Q)){
DeQueue(Q,u);
c = LocateVex(G,u);
for(w=FirstAdjVex(G,c);w>=0;w=NextAdjVex(G,c,w))
{
if(!visited[w]){
i = visit(G,G.vexs[w]);
visited[i] = 1;
EnQueue(Q,G.vexs[w]);
}
}
}
}
//菜单打印
void Menu(){
printf("\n————————菜单————————\n");
printf("\n1.创建图结构;\n");
printf("\n2.深度遍历（DFS）;\n");
printf("\n3.广度遍历（BFS）;\n");
printf("\n0.退出;\n");
printf("\n——————————————————\n");
printf("[请输入你的选择:]\n>>>");
}
//主函数
int main(){
int i,user;
char v;
AMGraph G;
while(1){
Menu();
scanf("%d",&user);
switch(user){
case 1:{
CreateUDN(G);
break;
}
case 2:{
//初始化辅助数组
for(i=0;i<G.vexnum;i++)
visited[i] = 0;
printf("[请输入遍历开始的顶点:]\n>>>");
getchar();
scanf("%c",&v);
DFS_AM(G,v);
break;
}
case 3:{
//初始化辅助数组
for(i=0;i<G.vexnum;i++)
visited[i] = 0;
printf("[请输入遍历开始的顶点:]\n>>>");
getchar();
scanf("%c",&v);
BFS_AM(G,v);
break;
}
case 0:{
exit(0);
break;
}
}
}
return 0;
}
无向图的邻接矩阵是对称的，有向图邻接矩阵可能不对称。
深度优先搜索类似于栈结构的出栈于入栈过程，模拟递归，其实递归也是通过堆栈的形式实现的。
广度遍历是非递归过程，借助队列来实现。
辅助数组需要在全局使用，在主函数外定义。
DFS与BFS空间复杂度都是O（n）,邻接矩阵时间复杂度都是O（n2），邻接表时间复杂度为O（n+e）。
邻接矩阵示意图：
“C语言数据结构图如何创建与遍历”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
