| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
 买学问 - 大牛一对一辅导，有问必答 买学问 - 专业的付费知识问答平台

已结贴   问题点数：20  回复次数：1

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define INFINITY 65535

typedef struct MGragh
{
char Vexs[MAXSIZE];//定义顶点表
int Edge[MAXSIZE][MAXSIZE];//定义边数组
int VexsNum;
int EdgeNum;
}MGraph;
typedef struct QNode//结点结构
{
int data;
struct QNode *next;
}QNode, *QueuePtr;//定义了链队列中的结点类型
{
QueuePtr front, rear;

void CreatMGragh(MGragh *);//创建无向网图
void  DispMGraph(MGraph *);//在屏幕显示邻接矩阵
int visited[MAXSIZE];
void DFS(MGragh, int);//邻接矩阵的是深度优先递归算法
void DFSTraverse(MGragh);//邻接矩阵的深度遍历
void BFSTraverse(MGragh);//邻接矩阵的广度遍历

int main(void)
{
MGragh G;
CreatMGragh(&G);
DispMGraph(&G);
printf("\n深度遍历：");
DFSTraverse(G);
printf("\n广度遍历：");
BFSTraverse(G);
return 0;
}
void CreatMGragh(MGragh *G)
{
int i = 0, j = 0, k = 0, wet = 0;
char ch;
printf("请输入顶点数和边数：\n");
scanf_s("%d %d", &G->VexsNum, &G->EdgeNum);
ch = getchar();//吸收Enter键
for (i = 0; i < G->VexsNum; i++)
{
for (j = 0; j< G->VexsNum; j++)
G->Edge[i][j] = INFINITY;//对边数组初始化
}
printf("请输入顶点信息(char类型)\n");
for (i = 0; i < G->VexsNum; i++)
{
scanf_s("%c", &G->Vexs[i]);//输入顶点信息
ch = getchar();
}
for (k = 0; k < G->EdgeNum; k++)
{
printf("请输入(Vi,Vj)边的下标i,j和权值wet:");
scanf_s("%d %d %d", &i, &j, &wet);
ch = getchar();
G->Edge[i][j] = wet;
G->Edge[j][i] = G->Edge[i][j];
}
}
void DispMGraph(MGraph *G)
{
int i, j;
printf("G含有%d个顶点%d个边\n", G->VexsNum, G->EdgeNum);
printf("打印顶点信息：\n");
for (i = 0; i < G->VexsNum; i++)
printf("%c", G->Vexs[i]);
printf("各顶点相连情况:\n");
for (i = 0; i <G->VexsNum; i++)
{
printf("[%d]\t", i);
for (j = 0; j < G->VexsNum; j++)
{
if (G->Edge[i][j] == INFINITY)
printf("0\t");
else
printf("%d\t", G->Edge[i][j]);
}
printf("\n");
}
}
{
q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));//产生一个头结点并将地址填入头指针域，尾指针也指向头结点
if (!q->front) return FALSE;
q->front->next = NULL;//填头结点的指针域为空
return TRUE;
}
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
if (!s)
return FALSE;
s->data = e;
s->next = NULL;
q->rear->next = s;
q->rear = s;
return TRUE;
}
{
QueuePtr p;
if (q->front == q->rear) return FALSE;//空队列，返回空
p = q->front->next;
*e = p->data;
q->front->next = p->next;
if (q->rear == p) q->rear = q->front;//若队头是队尾，则删除后将队尾指针指向头结点
free(p);
return TRUE;
}
{
if (q->front == q->rear)
return 1;
return 0;
}
void DFS(MGragh G, int i)
{
int j;
visited[i] = TRUE;
printf("%c", G.Vexs[i]);
for (j = 0; j < G.VexsNum; j++)
if (G.Edge[i][j] != 0 && !visited[j])
DFS(G, j);//对未被访问过的邻接顶点递归调用
}
void DFSTraverse(MGragh G)
{
int i;
for (i = 0; i < G.VexsNum; i++)
visited[i] = FALSE;//初始所有顶点都是未被访问过
for (i = 0; i < G.VexsNum; i++)
if (!visited[i])
DFS(G, i);
}
void BFSTraverse(MGragh G)
{
int i, j;
for (i = 0; i < G.VexsNum; i++)
{
visited[i] = FALSE;
}
InitQueue(&Q);
for (i = 0; i < G.VexsNum; i++)
{
if (!visited[i])
{
visited[i] = TRUE;
printf("%c", G.Vexs[i]);
EnQueue(&Q, i);
while (!EmptyQueue(&Q))
{
DeQueue(&Q, &i);
for (j = 0; j < G.VexsNum; j++)
{
if (G.Edge[i][j] != 0 && !visited[j])
{
visited[j] = TRUE;
printf("%c", G.Vexs[j]);
EnQueue(&Q, j);
}
}
}
}
}

}

得分:20
void DFS(MGragh G, int i)
{
int j;
visited[i] = TRUE;
printf("%c", G.Vexs[i]);
for (j = 0; j < G.VexsNum; j++)
if (G.Edge[i][j] != 0 && !visited[j])
DFS(G, j);//对未被访问过的邻接顶点递归调用
}

G.Edge[i][j]!=INFINITY

• 2
• 1/1页
• 1