实验七 图及其应用实验报告

int no;

//顶点编号 //顶点其他信息 //顶点类型

InfoType info;

} VertexType; {

typedef struct //图的定义

//邻接矩阵

int edges[MAXV][MAXV]; int n, e;

VertexType vexs[MAXV];

//顶点数，边数 //存放顶点信息 //图的邻接矩阵类型

//边的节点结构类型

} MGraph;

//以下定义邻接表类型

typedef struct ANode {

int adjvex; //该边的终点位置 struct ANode *nextarc;

//指向下一条边的指针

InfoType info; //该边的相关信息,这里用于存放权值

} ArcNode; typedef int Vertex;

typedef struct Vnode {

Vertex data; ArcNode *firstarc;

//顶点信息 //指向第一条边 //AdjList是邻接表类型 //邻接表头节点的类型

} VNode;

typedef VNode AdjList[MAXV]; typedef struct {

//------------------------------------- //--------带权图的算法----------------- //-------------------------------------

void MatToList1(MGraph g, ALGraph *&G) AdjList adjlist; //邻接表

int n, e; //图中顶点数n和边数e

//图的邻接表类型

} ALGraph;

//将邻接矩阵g转换成邻接表G { }

void DispMat1(MGraph g) //输出邻接矩阵g { }

void DispAdj1(ALGraph *G) int i, j;

for (i = 0; ifor (j = 0; jif (g.edges[i][j] == INF)

printf(\"%3s\∞\"); printf(\"%3d\else

int i, j;

ArcNode *p; //表结点结构类型 G = (ALGraph *)malloc(sizeof(ALGraph)); for (i = 0; ifor (i = 0; i//给邻接表中所有头节点的指针域置初值 //检查邻接矩阵中每个元素

G->adjlist[i].firstarc = NULL; for (j = g.n - 1; j >= 0; j--)

if (g.edges[i][j] != 0 && g.edges[i][j] != INF) //存在一条边 {

p = (ArcNode *)malloc(sizeof(ArcNode)); //创建一个节点*p p->adjvex = j; //终点信息 p->info = g.edges[i][j]; //权值信息 p->nextarc = G->adjlist[i].firstarc; G->adjlist[i].firstarc = p;

}

//将*p链到链表后

G->n = g.n; G->e = g.e;

printf(\"\\n\");

//输出邻接表G { }

int visited[MAXV] = { 0 }; //全局数组

void DFS(ALGraph *G, int v) //深度优先递归算法 { }

void BFS(ALGraph *G, int v) //广度优先遍历 {

ArcNode *p;

visited[v] = 1; //置已访问标记 printf(\"%3d\ while (p != NULL) { }

if (visited[p->adjvex] == 0)

DFS(G, p->adjvex);

//p指向顶点v的下一条弧的弧头结点

//若p->adjvex顶点未访问,递归访问它

//输出被访问顶点的编号

//p指向顶点v的第一条弧的弧头结点

p = G->adjlist[v].firstarc; int i; ArcNode *p; for (i = 0; in; i++) { }

p = G->adjlist[i].firstarc; printf(\"%3d: \while (p != NULL) { }

printf(\"\\n\");

printf(\"%3d(%d)\p = p->nextarc;

p = p->nextarc;

}

ArcNode *p;

int queue[MAXV], front = 0, rear = 0; int visited[MAXV]; int w, i;

for (i = 0; in; i++) visited[i] = 0; printf(\"%3d\

visited[v] = 1; rear = (rear + 1) % MAXV; queue[rear] = v; while (front != rear) { }

printf(\"\\n\");

front = (front + 1) % MAXV; w = queue[front]; p = G->adjlist[w].firstarc; while (p != NULL) { }

if (visited[p->adjvex] == 0) { }

p = p->nextarc;

//找下一个邻接顶点

printf(\"%3d\ //访问相邻顶点 visited[p->adjvex] = 1; queue[rear] = p->adjvex;

//置该顶点已被访问的标志

//该顶点进队

rear = (rear + 1) % MAXV;

//若当前邻接顶点未被访问

//出队并赋给w

//找与顶点w邻接的第一个顶点

//v进队 //若队列不空时循环

//访问标志数组初始化 //输出被访问顶点的编号

//置已访问标记

//定义循环队列并初始化 //定义存放结点的访问标志的数组

void Prim(MGraph g, int v) //prim 算法求最小生成树 {

/***初始化lowcost数组，closest数组(即从起点开始设置lowcost数组，closest

数组相应的值，以便后续生成使用)***/

int lowcost[MAXV], min, n = g.n; int closest[MAXV], i, j, k;

for (i = 0; i < g.n; i++)//赋初值，即将closest数组都赋为第一个结点v，lowcost{ }

/**********************************开始生成其他的结点

for (i = 1; i < g.n; i++)//接下来找剩下的n-1个结点（g.n是图的节点个数） {

/*****找到一个结点，该节点到已选节点中的某一个结点的权值是当前最min = INF;//INF表示正无穷（每查找一个结点，min都会重新更新为INF，for (j = 0; j < g.n; j++)//遍历所有结点 { }

/****************输出被连接结点与连接结点，以及它们的权值printf(\"边(%d,%d)权为:%d\\n\

/***********更新lowcost数组，closest数组，以便生成下一个结点lowcost[k] = 0;//表明k结点已被选了(作标记) //选中一个结点完成连接之后，作数组相应的调整 for (j = 0; j < g.n; j++)//遍历所有结点

if (lowcost[j] != 0 && lowcost[j] < min)//若该结点还未被选且权值小于之{ }

min = lowcost[j];//更新min的值 k = j;//记录当前最小权重的结点的编号

closest[i] = v;

lowcost[i] = g.edges[v][i];//g.edges[v][i]的值指的是结点v到i节点的权重

数组赋为第一个结点v到各结点的权重

*********************************/

小的*****/

以便获取当前最小权重的结点）

前遍历所得到的最小值

***************/

************/

{

/* if语句条件的说明：

* （1）g.edges[k][j] != 0是指k！=j，即跳过自身的结点

* （2）g.edges[k][j]是指刚被选的结点k到结点j的权重，lowcost[j]是

指之前遍历的所有结点与j结点的最小权重。若g.edges[k][j] < lowcost[j],则说明当前刚被选的结点k与节点j之间存在更小的权重，则需要更新

} int main() {

ALGraph *G; MGraph g;

int path[MAXV], i, j, v = 0; g.n = 6; g.e = 10; int A[MAXV][6] = {

{ 0, 5, INF, 7, INF, INF }, { INF, 0, 4, INF, INF, INF }, { 8, INF, 0, INF, INF, 9 }, { INF, INF, 5, 0, INF, 6 }, { INF, INF, INF, 5, 0, INF }, { 3, INF, INF, INF, 1, 0 } };

}

}

*/

if (g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j]) { }

//更新lowcost数组，closest数组

lowcost[j] = g.edges[k][j];//更新权重，使其当前最小

closest[j] = k;//进入到该if语句里，说明刚选的结点k与当前结点j

有更小的权重，则closest[j]的被连接结点需作修改为k

for (i = 0; ifor (j = 0; j}

g.edges[i][j] = A[i][j];

printf(\"有向图G的邻接矩阵:\\n\"); DispMat1(g);

G = (ALGraph *)malloc(sizeof(ALGraph)); MatToList1(g, G);

printf(\"图G的邻接表:\\n\"); DispAdj1(G); //输出邻接表 //G = (ALGraph *)malloc(sizeof(ALGraph)); printf(\"从顶点0开始的DFS(递归算法):\\n\"); DFS(G, 0); printf(\"\\n\");

printf(\"从顶点0开始的BFS(非递归算法):\\n\"); BFS(G, 0); printf(\"\\n\");

printf(\"普里姆算法求解结果:\\n\"); Prim(g, 0); return 0;

主要代码二： #include #define maxn 200 #define inf 1e9 int n; char v[maxn]; int hash[maxn]; int e[maxn][maxn]; int dis[maxn]; int path[maxn]; int visit[maxn];

void Dijkstra(int x) {

}

int k,min;

for(int i=1; i<=n; i++) { } dis[x]=0; visit[x]=1;

for(int t=0; tmin=inf;

for(int i=1; i<=n; i++) { } visit[k]=1;

for(int i=1; i<=n; i++) { }

if(!visit[i] && dis[i]>dis[k]+e[k][i]) { }

dis[i]=dis[k]+e[k][i]; path[i]=k;

if(!visit[i] && dis[i]k=i; min=dis[i];

dis[i]=e[x][i]; visit[i]=0; if(e[x][i]path[i]=x; path[i]=-1; else

void printpath(int x) { } int main() {

int m,d; char x,y; while(1) {

scanf(\"%d %d\if(n==0 && m==0) { } while(m--) { } getchar();

scanf(\"%c %c\

getchar();

scanf(\"%c %c %d\

e[hash[x]][hash[y]]=e[hash[y]][hash[x]]=d; getchar(); scanf(\"%c\hash[v[i]]=i; break;

for(int j=0; je[i][j]=inf;

for(int i=0; iprintpath(path[x]); printf(\"%c \

for(int i=1; i<=n; i++)

} } Dijkstra(hash[x]); printf(\"%d\\n\int p=path[hash[y]]; printpath(path[hash[y]]); printf(\"%c\\n\return 0; 4、实验结果分析及总结体会： 实验结果一： 实验结果二： 总结体会： 通过本次实验对图有了更深一步的认识，对图的邻接矩阵、邻接表的表示方法 ，图的遍历有了更深的理解，能够较好的掌握邻接矩阵，邻接表的表示原理，对图的遍历规则认识更加透彻，还学会了图的连通性及有向无环图的应用，对图有了更进一步的看法。