assession 2022-11-16 11:07 采纳率: 100%

数据结构图的基本操作（DFS,BFS算法实现）

``````#include<stdio.h>
#include<malloc.h>
#define INF 32767
typedef int InfoType;
#define MAXV 100
//领接矩阵类型的定义
typedef struct
{
int no;
InfoType info;
}VertexType;

//图的定义
typedef struct
{
int edges[MAXV][MAXV];
int n, e;
VertexType vex[MAXV];
}MGraph;

//领接表类型的定义
typedef struct ANode
{
struct ANode* nextarc;
InfoType info;
}ArcNode;
typedef struct Vnode
{
int data;
int count;
ArcNode* firstarc;
}VNode;
typedef struct
{
int n, e;
}ALGraph;

int visited[MAXV];
//将领接矩阵g转换成邻接表G
void MatToList(MGraph g, ALGraph*& G)
{
int i, j, n = g.n;
ArcNode* p;
G = (ALGraph*)malloc(sizeof(ALGraph));
for (i = 0; i < n; i++)
for (i=0;i<n;i++)
for (j = n - 1; j >= 0; j--)
{
if (g.edges[i][j] > 0 && g.edges[i][j] < INF)
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p->info = g.edges[i][j];
}
}
G->n = n;
G->e = g.e;
}
//输出邻接矩阵
void DisMat(MGraph g)
{
int i, j;
for (i = 0; i < g.n; i++)
{
for (j = 0; j < g.n; j++)
if (g.edges[i][j] >= 0 && g.edges[i][j] < INF)
printf("%5d", g.edges[i][j]);
else printf("%s", "INF");
printf("\n");
}
}
//输出邻接表
{
int i;
ArcNode* p;
for (i = 0; i < G->n; i++)
{
printf("%3d:", i);
while (p != NULL)
{
p = p->nextarc;
}
printf("\n");
}
}
//深度优先遍历算法DFS
void ShenduDFS(ALGraph* G, int v)
{
ArcNode* p;
visited[v] = 1;
printf("%2d", v);
while (p != NULL)
{
{
}
p = p->nextarc;
}
}
//广度优先遍历算法BFS
void GuangduBFS(ALGraph* G, int v)
{
ArcNode* p;
int queue[MAXV], front = 0, rear = 0;
int visited[MAXV];
int w, i;
for (i = 0; i < G->n; i++)visited[i] = 0;
printf("%2d", v);
visited[v] = 1;
rear = (rear + 1) % MAXV;
queue[rear] = v;
while (front != rear)
{
front = (front + 1) % MAXV;
w = queue[front];
while (p != NULL)
{
{
rear = (rear + 1) % MAXV;
}
p = p->nextarc;
}
}
printf("\n");
}

int main()
{
int i, j, u = 0, v = 0, d = -4;
bool flag = false;
MGraph g;
ALGraph* G;
int A[MAXV][6] = {
{0,5,INF,7,INF,INF },
{INF,0,4,INF,INF,INF},
{8,INF,0,INF,INF,9},
{INF,INF,5,0,INF,6},
{INF,INF,INF,5,0,INF},
{3,INF,INF,INF,1,0} };
g.n = 6; g.e = 10;
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
g.edges[i][j] = A[i][j];
printf("\n");
printf("有向带权图G的邻接矩阵：\n");
DisMat(g);
G = (ALGraph*)malloc(sizeof(ALGraph));
printf("转换成邻接表：\n");
MatToList(g, G);
printf("\n");
printf("深度优先序列（DFS）：");
ShenduDFS(G, 0);
printf("\n");
printf("广度优先序列（BFS）:");
GuangduBFS(G, 0);
}

``````

• 写回答

8条回答默认 最新

• 语言-逆行者 2022-11-16 13:38
关注

非递归前序遍历：

``````void preorder(bitree *t)//前序遍历的非递归算法
{
bitree *temp = t;//定义一个树节点，用它来遍历
while(temp != NULL || s.top != 0)
{
while(temp != NULL)//先遍历左孩子，并输出。
{
printf("%4d",temp->data);
push(temp);
temp = temp->lchild;
}
if(s.top != 0)//当左孩子遍历完后，取栈顶，找右孩子。此时循环还没有结束，再遍历它的左孩子，直至孩子全部遍历结束。
{
temp = pop();
temp = temp->rchild;
}
}
printf("\n");
}

``````

非递归中序遍历：

``````void inorder(bitree *t)//中序遍历的非递归算法
{
bitree *temp = t;
while(temp != NULL||s.top != 0)
{
while(temp != NULL)//先把左孩子入栈，所有左孩子入栈结束
{
push(temp);
temp = temp->lchild;
}
if(s.top != 0)//左孩子入栈结束，取栈顶，输出栈顶元素，遍历右孩子
{
temp = pop();
printf("%4d",temp->data);
temp = temp->rchild;
}
}
printf("\n");
}

``````

非递归后序遍历：

``````void laorder(bitree *root)//后序遍历的非递归算法
{
bitree *temp = root;
while(temp!=NULL||s.top!=0)
{
while(temp!= NULL)
{
temp->cishu=1;       // 当前节点首次被访问
push(temp);
temp=temp->lchild;
}
if(s.top!=0)
{
temp=pop( );
if(temp->cishu == 1)   // 第一次出现在栈顶
{

temp->cishu++;
push(temp);
temp=temp->rchild;
}
else
if(temp->cishu==2)//第二次输出并制空，防止陷入死循环
{
printf("%4d",temp->data);
temp=NULL;
}
}
}
printf("\n");
}

``````

参考连接1：
参考链接2：

本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论 编辑记录

• 系统已结题 11月24日
• 已采纳回答 11月16日
• 修改了问题 11月16日
• 修改了问题 11月16日
• 展开全部

悬赏问题

• ¥15 有偿求做台风过境全过程模拟仿真
• ¥50 求！AutomationDesk 如何自动导入Variant数据
• ¥20 Next.JS 静态导出路由
• ¥15 我做一个对中文文本情感分析的项目 我用了CNN，和keras框架 报的错误我一直处理不好
• ¥15 unity使用bakery打光烘焙所遇到的问题。
• ¥99 二维有限元方法求解，泊松方程
• ¥15 我需要在PC端 开两个抖店工作台客户端.(语言-java)
• ¥15 有没有哪位厉害的人可以用C#可视化呀
• ¥15 可以帮我看看代码哪里错了吗
• ¥15 设计一个成绩管理系统