邻接链表实现图
/*
邻接链表表示法
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#define InfoType int //权值
#define VertexType int //顶点数据类型
#define OK 0 //操作成功执行
#define ERROR -1 //操作失败
#define OVERFLOW -2 //溢出
typedef int Status;
#define MAX_VERTEX_NUM 20 //最大顶点数
#define MAX_EDGE_NUM 40 //最大边数
#define QElemType VertexType
#include "queue.h"
enum Boolean { FALSE, TRUE };
Boolean visited[MAX_VERTEX_NUM]; //访问标志矢量数组
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;
int Kind;
}ALGraph;
Status LocateVex(ALGraph &G, int v)
{
int k, n = 0;
for (k = 0; k < G.vexnum; k++)
{
if (G.vertices[k].data == v)
{
n = k;
break;
}
}
return n;
}
Status FirstAdjvex(ALGraph &G, int v)
{
if (G.vertices[v].firstarc != NULL)
return (G.vertices[v].firstarc->adjvex);
else
return OVERFLOW;
}
Status NextAdjvex(ALGraph &G, int v, int w)
{
ArcNode *p;
p = G.vertices[v].firstarc;
while (p&&p->adjvex != w)
p = p->nextarc;
if (p)
{
if (p->nextarc != NULL)return(p->nextarc->adjvex);
else return OVERFLOW;
}
else
return OVERFLOW;
}
Status Build_AdjList(ALGraph &G)
{
int v, v1, v2, i, j;
ArcNode *q, *p;
printf("请输入图的顶点数：\n");
scanf("%d", &G.vexnum);
if (G.vexnum < 0) return ERROR;
printf("请输入图的边数：\n");
scanf("%d", &G.arcnum);
if (G.arcnum < 0) return ERROR;
for (v = 0; v < G.vexnum; v++) {
printf("顶点V%d：\n", v);
scanf("%d", &G.vertices[v].data);
G.vertices[v].firstarc = NULL;
}
for (v = 1; v <= G.arcnum; v++)
{
printf("请输入边的两个邻接顶点（逗号隔开）：\n");
scanf("%d,%d", &v1, &v2);
if ((i = LocateVex(G, v1)) < 0) return ERROR;
if ((j = LocateVex(G, v2)) < 0) return ERROR;
p = (ArcNode*)malloc(sizeof(ArcNode));
if (!G.vertices[i].firstarc)
G.vertices[i].firstarc = p;
else {
for (q = G.vertices[i].firstarc; q->nextarc != NULL; q = q->nextarc);
q->nextarc = p;
}
p->adjvex = j;
p->nextarc = NULL;
}
return OK;
}
Status printelem(VertexType d)
{
printf("V%d->", d);
return OK;
}
Status(*VisitFunc)(VertexType d);
void DFS(ALGraph &G, int v)
{
ArcNode *w;
visited[v] = TRUE;
//VisitFunc(v);
VisitFunc(G.vertices[v].data);
for (w = G.vertices[v].firstarc; w; w = w->nextarc)
if (!visited[w->adjvex]) DFS(G, w->adjvex);
}
void DFSTreaverse(ALGraph G, Status(*Visit)(VertexType d))
{
VisitFunc = Visit;
int v, n;
for (v = 0; v < G.vexnum; ++v) visited[v] = FALSE;
printf("请输入深度优先遍历起始顶点：\n");
scanf("%d", &n);
printf("深度优先遍历点顺序：\n");
DFS(G, n - 1);
for (v = 0; v < G.vexnum; ++v)
if (!visited[v]) DFS(G, v);
}
void BFS(ALGraph &G, int v)
{
int u, w;
LinkQueue Q;
InitQueue(Q);
visited[v] = TRUE;
VisitFunc(G.vertices[v].data);
//VisitFunc(v);
EnQueue(Q, v);
while (!QueueEmpty(Q)) {
DeQueue(Q, u);
for (w = FirstAdjvex(G, u); w >= 0; w = NextAdjvex(G, u, w))
if (!visited[w]) {
visited[w] = TRUE;
VisitFunc(G.vertices[w].data);
//VisitFunc(w);
EnQueue(Q, w);
}//endif
}//endwhile
DestroyQueue(Q);
}
void BFSTreaverse(ALGraph G, Status(*Visit)(VertexType d))
{
char n;
int v;
VisitFunc = Visit;
for (v = 0; v < G.vexnum; ++v) visited[v] = FALSE;
printf("请输入广度优先遍历起始顶点：\n"); fflush(stdin);
scanf("%c", &n);
printf("广度优先遍历点顺序：\n"); fflush(stdin);
BFS(G, LocateVex(G, n));
for (v = 0; v < G.vexnum; ++v)
if (!visited[v]) BFS(G, v);
}
int main(int argc, char *argv[])
{
ALGraph G;
Build_AdjList(G);
DFSTreaverse(G, printelem);
printf("\n");
BFSTreaverse(G, printelem);
printf("\n");
return 0;
}
队列头文件queue.h
#pragma once
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define QUEUE_INIT_SIZE 100
#define QUEUEINCREMENT 10
typedef int Status;
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q);
Status DestroyQueue(LinkQueue &Q);
Status ClearQueue(LinkQueue &Q);
Status QueueEmpty(LinkQueue Q);
int QueueLength(LinkQueue Q);
Status GetHead(LinkQueue &Q, QElemType &e);
Status EnQueue(LinkQueue &Q, QElemType e);
Status DeQueue(LinkQueue &Q, QElemType &e);
Status QueueTraverse(LinkQueue Q, Status(*visit)());
Status InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front)exit(OVERFLOW);
Q.front->next = NULL;
return OK;
}
Status DestroyQueue(LinkQueue &Q)
{
while (Q.front)
{
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
}
Status ClearQueue(LinkQueue &Q)
{
Q.front = Q.rear;
return OK;
}
Status QueueEmpty(LinkQueue Q)
{
if (Q.front == Q.rear)return OK;
else
return ERROR;
}
Status EnQueue(LinkQueue &Q, QElemType e)
{
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if (!p) exit(OVERFLOW);
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Status DeQueue(LinkQueue &Q, QElemType &e)
{
QueuePtr p;
if (Q.front == Q.rear) return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p) Q.rear = Q.front;
free(p);
return OK;
}
int QueueLength(LinkQueue Q)
{
return(Q.rear - Q.front);
}
Status GetHead(LinkQueue &Q, QElemType &e)
{
if (Q.front == Q.rear) return ERROR;
else return Q.front->data;
}
Status QueueTraverse(LinkQueue Q, Status(*visit)(QElemType e))
{
QueuePtr p = Q.front->next;
while (p != NULL)
{
visit(p->data);
p = p->next;
}
return OK;
}
网友评论