C语言实现图的遍历,AI禁区（悬赏）,技术交流,鱼C论坛

王小二° 发表于 2024-6-5 23:31:07

C语言实现图的遍历

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct Node
{
int elem;
struct Node *next;
}Node,*QNode;
typedef struct
{
QNode front;
QNode rear;
}Queue;
#define MAX 20

typedef struct ArcNode    //表结点
{
int adjvex;          //该边所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条边
}ArcNode;

typedef struct VNode       //头结点
{
int data;             //顶点信息
ArcNode *firstarc;    //指向第一条依附该结点的边的指针
}VNode,AdjList;

typedef struct
{
AdjList vertices; //一维数组（头结点）
int vexnum;       //结点的个数
int arcnum;       //边的条数
}Graph;
Queue* InitQueue(Queue *Q)
{
Q->front=(QNode)malloc(sizeof(Node));
if(Q->front!=NULL)
{
Q->rear=Q->front;
Q->front->next=NULL;
return Q;
}

else return NULL;
}
Status EnQueue(Queue *Q,int e)
{

QNode newnode;
newnode=(QNode)malloc(sizeof(Node));
if(newnode!=NULL)
{
newnode->elem=e;
newnode->next=NULL;
Q->rear->next=newnode;
Q->rear=newnode;
return OK;
}
else return FALSE;
}
Status DeQueue(Queue *Q,int *e)
{
QNode p;
if(Q->front==Q->rear)
{
return 0;
}
p=Q->front->next;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
*e=p->elem;
free(p);
return 1;
}

int LocateVex(Graph *G,int index)
{
int i;
for(i=0;i<G->vexnum;i++)
{
if(G->vertices.data==index)
return i;
}
}

Status CreateGraph(Graph *G)//Status CreateGraph(Graph &G)(引用参数）
{//以邻接表形式创建无向图G
int m,n,i,j,k,v1,v2,flag=0;
ArcNode *p1,*q1,*p,*q;
printf("请输入VNode的编号: ");
scanf("%d",&m);
printf("请输入ArcNode的编号");
scanf("%d",&n);
G->vexnum=m;          //顶点数目
G->arcnum=n;          //边的数目
for(i=0;i<G->vexnum;++i)
{
G->vertices.data=i+1;    //顶点信息
G->vertices.firstarc=NULL;
}
//顶点信息
printf("输出VNode的消息:\n");
for(i=0;i<G->vexnum;++i)
printf("v%d\n",G->vertices.data);

for(k=0;k<G->arcnum;++k)
{
printf("请输入%d边起始点和端点: ",k+1);
scanf("%d%d",&v1,&v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);

if(i>=0&&j>=0)
{
++flag;
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=NULL;
if(!G->vertices.firstarc)
G->vertices.firstarc=p;
else
{
for(p1=G->vertices.firstarc;p1->nextarc;p1=p1->nextarc);
p1->nextarc=p;
}

q=(ArcNode *)malloc(sizeof(ArcNode));
q->adjvex=i;
q->nextarc=NULL;
if(!G->vertices.firstarc)
G->vertices.firstarc=q;
else
{
for(q1=G->vertices.firstarc;q1->nextarc;q1=q1->nextarc);
q1->nextarc=q;
}
}
else
{
printf("没有这个优势!\n");
k=flag-1;
}

}

printf("邻接表为:\n"); //输出邻接表
for(i=0;i<G->vexnum;++i)
{
printf("\t%d v%d->",i,G->vertices.data);
p=G->vertices.firstarc;
while(p->nextarc)
{
printf("%d->",p->adjvex);
p=p->nextarc;
}
printf("%d\n",p->adjvex);
}
return OK;
}

int FirstAdjVex(Graph G,int v)
{//返回v的第一个邻接顶点
ArcNode *p;
p=G.vertices.firstarc;
if(p)
return (p->adjvex);
else
return -1;
}

int NextAdjVex(Graph G,int v,int w)
{//返回v中相对于w的下一个邻接顶点
int flag=0;
ArcNode *p;
p=G.vertices.firstarc;
while(p)
{
if(p->adjvex==w)
{
flag=1;
break;
}
p=p->nextarc;
}
if(flag && p->nextarc)
return p->nextarc->adjvex;
else
return -1;
}

int Visited;

void DFS(Graph G,int v)
{//深度优先遍历

ArcNode *p;
p=G.vertices.firstarc;
printf("%d ",G.vertices.data);
Visited=TRUE;
while(p)
{
if(!Visited)
{

DFS(G,p->adjvex);
}
p=p->nextarc;

}
}

void DFSTraverse(Graph G)
{
int i;//递归
for(i=0;i<G.vexnum;i++)
{
Visited=FALSE;
}
for(i=0;i<G.vexnum;i++)
{
if(!Visited)
DFS(G,i);
}
}

void BFSTraverse(Graph G)
{//广度优先遍历
int i,index;
ArcNode *temp;
Queue* que=InitQueue(que);

for(i=0;i<G.vexnum;i++)
{
Visited=0;
}
index=G.vertices.data;
if(!Visited)
{
EnQueue(que,index);
Visited=1;
while(que->rear!=que->front)
{
DeQueue(que,&index);

printf("%d ",G.vertices.data);
temp=G.vertices.firstarc;
while(temp)
{
index=LocateVex(&G,G.vertices.data);
if(!Visited)
{
EnQueue(que,index);
Visited=1;
}
temp=temp->nextarc;

}
}
}

}

void main()
{
Graph G;
CreateGraph(&G);
printf("深度优先搜索:\n");
DFSTraverse(G);
printf("\n广度优先搜索:\n");
BFSTraverse(G);
printf("\n");
system("pause");
}

能不能帮忙看看为什么广度遍历不成功啊，急

小甲鱼的二师兄 发表于 2024-6-5 23:31:08

本帖最后由小甲鱼的二师兄于 2024-6-5 23:45 编辑

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;

typedef struct Node {
int elem;
struct Node *next;
} Node, *QNode;

typedef struct {
QNode front;
QNode rear;
} Queue;

#define MAX 20

typedef struct ArcNode {    // 表结点
int adjvex;             // 该边所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条边
} ArcNode;

typedef struct VNode {       // 头结点
int data;                // 顶点信息
ArcNode *firstarc;       // 指向第一条依附该结点的边的指针
} VNode, AdjList;

typedef struct {
AdjList vertices;       // 一维数组（头结点）
int vexnum;             // 结点的个数
int arcnum;             // 边的条数
} Graph;

// 初始化队列
Queue* InitQueue(Queue *Q) {
Q->front = (QNode)malloc(sizeof(Node));
if (Q->front != NULL) {
   Q->rear = Q->front;
   Q->front->next = NULL;
   return Q;
} else {
   return NULL;
}
}

// 入队
Status EnQueue(Queue *Q, int e) {
QNode newnode;
newnode = (QNode)malloc(sizeof(Node));
if (newnode != NULL) {
   newnode->elem = e;
   newnode->next = NULL;
   Q->rear->next = newnode;
   Q->rear = newnode;
   return OK;
} else {
   return FALSE;
}
}

// 出队
Status DeQueue(Queue *Q, int *e) {
QNode p;
if (Q->front == Q->rear) {
   return 0;
}
p = Q->front->next;
Q->front->next = p->next;
if (Q->rear == p) {
   Q->rear = Q->front;
}
*e = p->elem;
free(p);
return 1;
}

// 查找顶点位置
int LocateVex(Graph *G, int index) {
int i;
for (i = 0; i < G->vexnum; i++) {
   if (G->vertices.data == index)
         return i;
}
return -1;// 如果找不到顶点，返回-1
}

// 创建图
Status CreateGraph(Graph *G) {
int m, n, i, j, k, v1, v2;
ArcNode *p1, *q1, *p, *q;
printf("请输入VNode的编号: ");
scanf("%d", &m);
printf("请输入ArcNode的编号: ");
scanf("%d", &n);
G->vexnum = m;          // 顶点数目
G->arcnum = n;          // 边的数目

for (i = 0; i < G->vexnum; ++i) {
   G->vertices.data = i + 1;    // 顶点信息
   G->vertices.firstarc = NULL;
}

printf("输出VNode的信息:\n");
for (i = 0; i < G->vexnum; ++i)
   printf("v%d\n", G->vertices.data);

for (k = 0; k < G->arcnum; ++k) {
   printf("请输入第%d条边的起始点和终点: ", k + 1);
   scanf("%d%d", &v1, &v2);
   i = LocateVex(G, v1);
   j = LocateVex(G, v2);

   if (i >= 0 && j >= 0) {
         p = (ArcNode *)malloc(sizeof(ArcNode));
         p->adjvex = j;
         p->nextarc = NULL;
         if (!G->vertices.firstarc)
            G->vertices.firstarc = p;
         else {
            for (p1 = G->vertices.firstarc; p1->nextarc; p1 = p1->nextarc);
            p1->nextarc = p;
         }

         q = (ArcNode *)malloc(sizeof(ArcNode));
         q->adjvex = i;
         q->nextarc = NULL;
         if (!G->vertices.firstarc)
            G->vertices.firstarc = q;
         else {
            for (q1 = G->vertices.firstarc; q1->nextarc; q1 = q1->nextarc);
            q1->nextarc = q;
         }
   } else {
         printf("没有这个顶点!\n");
         --k;// 如果顶点不存在，重新输入这条边
   }
}

printf("邻接表为:\n");// 输出邻接表
for (i = 0; i < G->vexnum; ++i) {
   printf("\t%d v%d->", i, G->vertices.data);
   p = G->vertices.firstarc;
   while (p) {
         printf("%d->", p->adjvex);
         p = p->nextarc;
   }
   printf("NULL\n");
}
return OK;
}

int Visited;// 访问标志数组

// 广度优先遍历
void BFSTraverse(Graph G) {
int i, index;
ArcNode *temp;
Queue que;
InitQueue(&que);

for (i = 0; i < G.vexnum; i++) {
   Visited = 0;// 初始化访问标志数组
}

for (i = 0; i < G.vexnum; i++) {
   if (!Visited) {
         EnQueue(&que, i);
         Visited = 1;
         while (que.rear != que.front) {
            DeQueue(&que, &index);
            printf("%d ", G.vertices.data);
            temp = G.vertices.firstarc;
            while (temp) {
               if (!Visited) {
                     EnQueue(&que, temp->adjvex);
                     Visited = 1;
               }
               temp = temp->nextarc;
            }
         }
   }
}
printf("\n");
}

int main() {
Graph G;
CreateGraph(&G);
printf("广度优先遍历结果：\n");
BFSTraverse(G);
return 0;
}

王小二° 发表于 2024-6-6 00:02:31

小甲鱼的二师兄发表于 2024-6-5 23:44

感谢感谢

王小二° 发表于 2024-6-6 00:03:56

小甲鱼的二师兄发表于 2024-6-5 23:31

麻烦问一下，我的bfs函数问题出在哪里啊？

页: [1]

鱼C论坛's Archiver

C语言实现图的遍历