#include
#include
#include
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef char VertexType;
typedef int VRType;
typedef int InfoType; //图中边上的权值信息
typedef int QElemType; //队列中节点数据类型
//邻接表存储图
typedef struct ArcNode
{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode* nextarc; //指向下一条弧的指针
InfoType* info; //该弧相关的信息的指针,如权值
}ArcNode;
typedef struct VNode
{
VertexType data; //顶点信息
ArcNode* firstarc; //指向第一条依附于该顶点的弧指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum, arcnum; //顶点数和弧数
}ALGraph;
//创建用于广度优先遍历的队列
typedef struct QNode
{
QElemType data;
struct QNode* qnext;
}QNode, * PQNode;
typedef struct Queue
{
PQNode front;
PQNode rear;
}Queue, * PQueue;
//初始化一个空队列
PQueue initQueue()
{
PQueue pqueue = (PQueue)malloc(sizeof(Queue));
PQNode pqnode = (PQNode)malloc(sizeof(QNode));
if (pqnode == NULL)
{
printf("队列头空间申请失败!\n");
exit(-1);
}
pqueue->front = pqueue->rear = pqnode;
pqnode->qnext = NULL;
return pqueue;
}
//队尾入队
void enQueue(PQueue pqueue, QElemType data)
{
PQNode pqnode = (PQNode)malloc(sizeof(QNode));
if (pqnode == NULL)
{
printf("队列结点申请失败!\n");
exit(-1);
}
pqnode->data = data;
pqnode->qnext = NULL;
pqueue->rear->qnext = pqnode;
pqueue->rear = pqnode;
}
//判断队列是否为空
bool isEmpty(PQueue pqueue)
{
if (pqueue->front == pqueue->rear)
return true;
return false;
}
//队头出队
QElemType deQueue(PQueue pqueue)
{
if (isEmpty(pqueue))
{
printf("队列为空\n");
exit(-1);
}
PQNode pqnode = pqueue->front->qnext;
pqueue->front->qnext = pqnode->qnext;
if (pqnode == pqueue->rear)
pqueue->rear = pqueue->front;
QElemType data = pqnode->data;
free(pqnode);
return data;
}
//确定图中顶点位置编号
int locateVex(ALGraph alg, char v)
{
int i;
for (i = 0; i < alg.vexnum; i++)
{
if (alg.vertices[i].data == v)
return i;
}
return -1;
}
//创建无向图
void createALGraph(ALGraph* alg)
{
int i, j, v, k;
printf("输入图的顶点数和边数\n");
scanf_s("%d %d", &(*alg).vexnum, &(*alg).arcnum);
printf("输入顶点名称\n");
getchar();
for (i = 0; i < (*alg).vexnum; i++)
{
printf("输入第%d个顶点名称:", i);
scanf_s("%c", &(*alg).vertices[i].data);
(*alg).vertices[i].firstarc = NULL;
getchar();
}
printf("输入图的边信息\n");
char v1, v2;
ArcNode* s ,*p;
for (k = 0; k < (*alg).arcnum; k++)
{
printf("输入第%d条边的两个节点v1 v2:", k);
scanf_s("%c %c", &v1, &v2);
i = locateVex((*alg), v1);
j = locateVex((*alg), v2);
//由于是无向图因此一条边需要关联两个节点
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = NULL;
if ((*alg).vertices[i].firstarc == NULL)
{
(*alg).vertices[i].firstarc = p;
}
else
{
s = (*alg).vertices[i].firstarc;
while (s->nextarc != NULL)
s = s->nextarc;
s->nextarc = p;
}
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = NULL;
if ((*alg).vertices[j].firstarc == NULL)
{
(*alg).vertices[j].firstarc = p;
}
else
{
s = (*alg).vertices[j].firstarc;
while (s->nextarc != NULL)
s = s->nextarc;
s->nextarc = p;
}
getchar();
}
}
bool visited[MAX_VERTEX_NUM]; //标记结点是否被遍历过,否为flase,是为true;
//深度优先遍历无向图
void DFS(ALGraph alg, int v)
{
//从第v个顶点出发递归的深度优先遍历图alg
ArcNode* p;
visited[v] = true;
printf("%c ", alg.vertices[v].data);
for (p = alg.vertices[v].firstarc; p != NULL; p = p->nextarc)
{
if (!visited[p->adjvex])
DFS(alg, p->adjvex);
}
}
void DFSTraverse(ALGraph alg)
{
//对邻接表存储的无向图进行深度优先遍历
printf("深度优先遍历序列:");
int v;
for (v = 0; v < alg.vexnum; v++)
visited[v] = false;
for (v = 0; v < alg.vexnum; v++)
{
if (!visited[v])
DFS(alg, v);
}
}
//广度优先遍历
void BFSTraverse(ALGraph alg)
{
printf("广度优先遍历序列:");
PQueue pqueue = initQueue();
ArcNode* p;
int i;
QElemType v;
for (i = 0; i < alg.vexnum; i++)
visited[i] = false;
for (i = 0; i < alg.vexnum; i++)
{
if (!visited[i])
{
visited[i] = true;
printf("%c ", alg.vertices[i].data);
enQueue(pqueue, i);
while (!isEmpty(pqueue))
{
v = deQueue(pqueue);
for (p = alg.vertices[v].firstarc; p != NULL; p = p->nextarc)
{
if (!visited[p->adjvex])
{
printf("%c ", alg.vertices[p->adjvex].data);
visited[p->adjvex] = true;
enQueue(pqueue, p->adjvex);
}
}
}
}
}
}
int main(int argc, char* argv[]) {
ALGraph alg;
createALGraph(&alg); //创建无向图
DFSTraverse(alg);
printf("\n");
BFSTraverse(alg);
printf("\n");
return 0;
}
我朋友在devC++上可以运行,但我在VS上会报错,说访问权限冲突,为什么呢,希望大家能帮帮我
那是因为越界或者你的数组下标是负数。
你把i和j打印出来,你会发现i、j是-1.
locateVex这个函数返回-1的情况你要考虑,不能直接把返回值作为下标
所以在for循环里面加个i、j判断即可。
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef char VertexType;
typedef int VRType;
typedef int InfoType; //图中边上的权值信息
typedef int QElemType; //队列中节点数据类型
//邻接表存储图
typedef struct ArcNode
{
int adjvex; //该弧所指向的顶点的位置
struct ArcNode* nextarc; //指向下一条弧的指针
InfoType* info; //该弧相关的信息的指针,如权值
}ArcNode;
typedef struct VNode
{
VertexType data; //顶点信息
ArcNode* firstarc; //指向第一条依附于该顶点的弧指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum, arcnum; //顶点数和弧数
}ALGraph;
//创建用于广度优先遍历的队列
typedef struct QNode
{
QElemType data;
struct QNode* qnext;
}QNode, *PQNode;
typedef struct Queue
{
PQNode front;
PQNode rear;
}Queue, *PQueue;
//初始化一个空队列
PQueue initQueue()
{
PQueue pqueue = (PQueue)malloc(sizeof(Queue));
PQNode pqnode = (PQNode)malloc(sizeof(QNode));
if (pqnode == NULL)
{
printf("队列头空间申请失败!\n");
exit(-1);
}
pqueue->front = pqueue->rear = pqnode;
pqnode->qnext = NULL;
return pqueue;
}
//队尾入队
void enQueue(PQueue pqueue, QElemType data)
{
PQNode pqnode = (PQNode)malloc(sizeof(QNode));
if (pqnode == NULL)
{
printf("队列结点申请失败!\n");
exit(-1);
}
pqnode->data = data;
pqnode->qnext = NULL;
pqueue->rear->qnext = pqnode;
pqueue->rear = pqnode;
}
//判断队列是否为空
bool isEmpty(PQueue pqueue)
{
if (pqueue->front == pqueue->rear)
return true;
return false;
}
//队头出队
QElemType deQueue(PQueue pqueue)
{
if (isEmpty(pqueue))
{
printf("队列为空\n");
exit(-1);
}
PQNode pqnode = pqueue->front->qnext;
pqueue->front->qnext = pqnode->qnext;
if (pqnode == pqueue->rear)
pqueue->rear = pqueue->front;
QElemType data = pqnode->data;
free(pqnode);
return data;
}
//确定图中顶点位置编号
int locateVex(ALGraph alg, char v)
{
int i;
for (i = 0; i < alg.vexnum; i++)
{
if (alg.vertices[i].data == v)
return i;
}
return -1;
}
//创建无向图
void createALGraph(ALGraph* alg)
{
int i, j, v, k;
printf("输入图的顶点数和边数\n");
scanf_s("%d %d", &(*alg).vexnum, &(*alg).arcnum);
printf("输入顶点名称\n");
getchar();
for (i = 0; i < (*alg).vexnum; i++)
{
printf("输入第%d个顶点名称:", i);
scanf_s("%c", &(*alg).vertices[i].data);
(*alg).vertices[i].firstarc = NULL;
getchar();
}
printf("输入图的边信息\n");
char v1, v2;
ArcNode* s, *p;
for (k = 0; k < (*alg).arcnum; k++)
{
printf("输入第%d条边的两个节点v1 v2:", k);
scanf_s("%c %c", &v1, &v2);
i = locateVex((*alg), v1);
j = locateVex((*alg), v2);
if (i<=0 || j<=0)
{
continue;
}
//由于是无向图因此一条边需要关联两个节点
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = NULL;
if ((*alg).vertices[i].firstarc == NULL)
{
(*alg).vertices[i].firstarc = p;
}
else
{
s = (*alg).vertices[i].firstarc;
while (s->nextarc != NULL)
s = s->nextarc;
s->nextarc = p;
}
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = NULL;
if ((*alg).vertices[j].firstarc == NULL)
{
(*alg).vertices[j].firstarc = p;
}
else
{
s = (*alg).vertices[j].firstarc;
while (s->nextarc != NULL)
s = s->nextarc;
s->nextarc = p;
}
getchar();
}
}
bool visited[MAX_VERTEX_NUM]; //标记结点是否被遍历过,否为flase,是为true;
//深度优先遍历无向图
void DFS(ALGraph alg, int v)
{
//从第v个顶点出发递归的深度优先遍历图alg
ArcNode* p;
visited[v] = true;
printf("%c ", alg.vertices[v].data);
for (p = alg.vertices[v].firstarc; p != NULL; p = p->nextarc)
{
if (!visited[p->adjvex])
DFS(alg, p->adjvex);
}
}
void DFSTraverse(ALGraph alg)
{
//对邻接表存储的无向图进行深度优先遍历
printf("深度优先遍历序列:");
int v;
for (v = 0; v < alg.vexnum; v++)
visited[v] = false;
for (v = 0; v < alg.vexnum; v++)
{
if (!visited[v])
DFS(alg, v);
}
}
//广度优先遍历
void BFSTraverse(ALGraph alg)
{
printf("广度优先遍历序列:");
PQueue pqueue = initQueue();
ArcNode* p;
int i;
QElemType v;
for (i = 0; i < alg.vexnum; i++)
visited[i] = false;
for (i = 0; i < alg.vexnum; i++)
{
if (!visited[i])
{
visited[i] = true;
printf("%c ", alg.vertices[i].data);
enQueue(pqueue, i);
while (!isEmpty(pqueue))
{
v = deQueue(pqueue);
for (p = alg.vertices[v].firstarc; p != NULL; p = p->nextarc)
{
if (!visited[p->adjvex])
{
printf("%c ", alg.vertices[p->adjvex].data);
visited[p->adjvex] = true;
enQueue(pqueue, p->adjvex);
}
}
}
}
}
}
int main(int argc, char* argv[]) {
ALGraph alg;
createALGraph(&alg); //创建无向图
DFSTraverse(alg);
printf("\n");
BFSTraverse(alg);
printf("\n");
return 0;
}