图这一章我一直觉得自己学的不是很好。。。这次就只放代码,不敢多说什么了。
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
#define MAXVEX 100
typedef struct EdgeNode{ //边表结点
int adjvex; //邻接点域,存储该顶点对应的下标
EdgeType weight; //用于存储权值,对于非网图可以不需要
struct EdgeNode *next; //链域,指向下一个邻接点
}EdgeNode;
typedef struct VertexNode{ //顶点表结点
VertexType data; //顶点域
EdgeNode *firstedge; //边表头指针
}VertexNode, AdjList[MAXVEX];
typedef struct{
AdjList adjList;
int numVertexes, numEdges; //图中当前顶点数和边数
}GraphAdjList;
/*头插法建立图的邻接表结构*/
void CreatALGraph(GraphAdjList *G){
int i, j, k;
EdgeNode *e;
printf("请输入顶点数和边数:");
scanf("%d, %d", &G->numVertexes, &G->numEdges); //输入顶点数和边数
for (i = 0; i < G->numVertexes; i++){ //读入顶点信息,建立顶点表
scanf("%c", &G->adjList[i].data); //输入顶点信息
G->adjList[i].firstedge = NULL; //将边表置为空表
}
for (k = 0; k < G->numEdges; k++){ //建立边表
printf("输入(vi, vj)上的顶点序号:\n");
scanf("%d, %d", &i, &j); //输入(vi, vj)上的顶点序号
e = (EdgeNode *)malloc(sizeof(EdgeNode)); //向内存申请空间
e->adjvex = j; //邻接序号为j
e->next = G->adjList[i].firstedge; //将e指针指向当前顶点所指向的结点
G->adjList[i].firstedge = e; //将当前顶点的指针指向e
e = (EdgeNode *)malloc(sizeof(EdgeNode)); //向内存申请空间,生成边表结点
e->adjvex = i; //邻接序号为i
e->next = G->adjList[j].firstedge; //将e指针指向当前顶点指向的结点
G->adjList[j].firstedge = e; //将当前顶点的指针指向e
}
}
typedef int Boolean; //Boolean是布尔类型,其值为TRUE 或者FLASE
Boolean visited[MAXVEX]; //访问标志的数组
/*邻接矩阵的深度优先递归算法*/
void DFS(GraphAdjList G, int i){
EdgeNode *p;
visited[i] = TRUE;
printf("%c", G.adjList[i].data); //打印定点,也可以是其它操作
p = G.adjList[i].firstedge;
while (p){
if (!visited[p->adjvex])DFS(G, p->adjvex); //对未访问的邻接顶点递归调用
p = p->next;
}
}
/*邻接矩阵的深度遍历操作*/
void DFSTraverse(GraphAdjList G){
int i;
for (i = 0; i < G.numVertexes; i++){
visited[i] = FALSE; //初始化所有顶点状态都是未访问的状态
}
for (i = 0; i < G.numVertexes; i++){
if (!visited[i])DFS(G, i); //对未访问过的顶点调用DFS,若连通图,只会执行一次
}
}
typedef int Boolean; //Boolean是布尔类型,其值为TRUE 或者FLASE
Boolean visited[MAXVEX]; //访问标志的数组
#define QElemType int // 元素类型定义为图结点
#define MAXSIZE 1000
typedef struct {
QElemType data[MAXSIZE];
int front;
int rear;
}SqQueue;
/*----------以下为队列的基本操作函数----------*/
/*初始化一个空队列*/
Status InitQueue(SqQueue *Q){
if (!Q)return ERROR; //若空间分配失败,则返回ERROR
Q->front = 0;
Q->rear = 0;
return OK;
}
/*判断SqQueue是否为空*/
Status IsQueueEmpty(SqQueue Q){
if (Q.rear == Q.front)return TRUE; //若尾指针指向头指针,则为空队列,返回TRUE
else{ return FALSE; } //否则返回FALSE
}
/*插入元素e为新的队尾元素*/
Status EnQueue(SqQueue *Q, QElemType e){
if ((Q->rear + 1) % MAXSIZE == Q->front)return ERROR; // 若队列已满,则返回ERROR
Q->data[Q->rear] = e; //e 入队列
Q->rear = (Q->rear + 1) % MAXSIZE; //队尾指针后移
return OK;
}
/*若队列不空,则删除队头元素,并用e返回其值*/
Status DeQueue(SqQueue *Q, QElemType *e){
if (Q->front == Q->rear)return ERROR; //若队列为空,则返回ERROR
*e = Q->data[Q->front]; //若队列不为空,用e接收队头元素
Q->front = (Q->front + 1) % MAXSIZE; //队头指针后移
return OK;
}
/*----------队列的基本操作函数完----------*/
/*----------以下为广度优先遍历算法---------*/
void BFSTraverse(GraphAdjList G){
int i;
SqQueue Q;
EdgeNode* p;
for (i = 0; i < G.numVertexes; i++){
visited[i] = FALSE;
}
InitQueue(&Q); //初始化一辅助用的队列
for (i = 0; i < G.numVertexes; i++){ //对每一个顶点做循环
if (!visited[i]){ //若未访问过,则如下处理
visited[i] = TRUE; //将当前结点设为已访问
printf("%c", G.adjList[i].data);//打印顶点,也可以改为其它操作
EnQueue(&Q, i); //将该顶点入队列
while (!IsQueueEmpty(Q)){
DeQueue(&Q, &i); //将队头元素出队,并赋给e
p = G.adjList[i].firstedge; //找到当前顶点边表头指针
while (p){
if (!visited[p->adjvex]){//若当前结点未被访问过
printf("%c", G.adjList[p->adjvex].data);
EnQueue(&Q, p->adjvex);
}
p = p->next; //指针指向下一个邻接点
}
}
}
}
}