实践四：图及图的应用
1.实验目的要求
理解图的基本概念，两种主要的存储结构。
掌握在邻接链表存储结构下的图的深度优先递归遍历、广度优先遍历。
通过选做题"最短路径问题"认识图及其算法具有广泛的应用意义。
实验要求：正确调试程序。
写出实验报告。
2.实验主要内容
2.1 在邻接矩阵存储结构下的图的深度优先递归遍历、广度优先遍历。
2.1.1 要完成图的两种遍历算法，首先需要进行图的数据初始化。
为把时间主要花在遍历算法的实现上，图的初始化采用结构体声明时初始化的方法。
示例代码如下：
#include "stdio.h"
typedef int Arcell;
typedef int AdjMatrix[5][5];
typedef struct {
char vexs[5];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
void main(){
MGraph g={
{'a','b','c','d','e'},
{{0,1,0,1,0},
{1,0,0,0,1},
{1,0,0,1,0},
{0,1,0,0,1},
{1,0,0,0,0}} ,5,9};
}
2.1.2 深度优先遍历算法7.5中FirstAdjVex方法和NextAdjVex方法需要自己实现。
2.2 拓扑排序，求图的拓扑序列
2.3 "最短路径问题"，以校园导游图为实际背景进行设计。
（选做）
程序代码如下：
#include <stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX 20
#define NULL 0
#define OK 1
#define OVERFLOW -2
#define ERROR 0
typedef int Status;
typedef int Boolean;
typedef int QElemType;
// 图的邻接矩阵存储结构typedef struct ArcCell{
int adj;
}ArcCell, AdjMatrix[20][20];
typedef struct {
char vexs[20];
AdjMatrix arcs;
int vexnum,arcnum; }Graph;
//队列的链式存储结构typedef struct QNode{
QElemType data;
struct QNode * next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q){
//构造一个空队列
Q.front=Q.rear =(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
Status EnQueue(LinkQueue &Q, QElemType e){
//插入元素e为Q的新的队尾元素
QueuePtr 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){
//若队列不空，则删除Q的对头元素，用e返回其值，并返回OK;
//否则返回ERROR
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;
}
Status QueueEmpty(LinkQueue Q){
//若队列Q为空队列，则返回TRUE
if(Q.rear==Q.front)
return TRUE;
else
return FALSE;
}
Boolean visited[MAX];
Status(*VisitFunc)(char v);
Status Visit(char v){
//visit函数
printf("%c ",v);
return 0;
}
int FirstAdjVex(Graph G,int v){
int i;
for(i=0;i<G.vexnum;i++){
if(G.arcs[v][i].adj==1)
return i;
}
return -1;
}
int NextAdjVex(Graph G,int v,int w){
int i;
for(i=w+1;i<G.vexnum;i++){
if(G.arcs[v][i].adj==1)
return i;
}
return -1;
}
void DFS(Graph G,int v){
int w;
visited[v] = TRUE; VisitFunc(G.vexs[v]);
for(w=FirstAdjVex(G,v); w >= 0; w=NextAdjVex(G,v,w)) if(!visited[w]) DFS(G,w);
}
/* 图的深度优先搜索 */
void DFSTraverse(Graph G,Status(*Visit)(char v)){
VisitFunc = Visit;
int v;
for(v=0; v<G.vexnum; ++v) visited[v] = FALSE;
for(v=0; v<G.vexnum; ++v)
if(!visited[v]) DFS(G,v);
}
/* 图的广度优先搜索 */
void BFSTraverse(Graph G, Status(*Visit)(char)){
int v,w,u;
LinkQueue q;
for(v=0; v<G.vexnum; ++v) visited[v] = FALSE;
InitQueue(q);
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v] = TRUE; Visit(G.vexs[v]);
EnQueue(q,v);
while(!QueueEmpty(q)){
DeQueue(q,u);
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!visited){
visited[w] = TRUE; Visit(G.vexs[w]);
EnQueue(q,w);
}
}
}
}
/* 输出邻接矩阵 */
void PrintGraph(Graph G)
{
int i,j;
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
{
printf("%d ",G.arcs[i][j].adj);
}
printf("\n");
}
}
void main(){
Graph g={
{'a','b','c','d','e','f','g','h'},
{{0,1,1,0,0,0,0,0,0},
{1,0,0,1,1,0,0,0},
{1,0,0,0,0,1,1,0},
{0,1,0,0,0,0,0,1},
{0,1,0,0,0,0,0,1},
{0,0,1,0,0,0,1,0},
{0,0,1,0,0,1,0,0},
{0,0,0,1,1,0,0,0}} ,8,18};
printf("图的邻接矩阵为：\n");
PrintGraph(g);
printf("\n图的深度优先搜索为：\n");
DFSTraverse(g,Visit);
printf("\n图的广度优先搜索为：\n");
BFSTraverse(g,Visit);
printf("\n");
}
输出结果为：。