图的操作算法(2)

（7）最小生成树的运行结果： 2、在实验过程中遇到的问题与解决方法： 图的操作对于我们来说是一道难题，我们之前没有接触过类似的程序，因为图是没有一个固定的顶点了，所有的点都可以作为顶点，这也是图与数最大的区别。图是一种多对多的结构，对于图的操作来说，最关键的是要建立不同顶点之间的联系，通过变量的改变或者其他操作使得两个顶点建立了联系。求最短路径之类的操作就是在顶点建立联系的基础上对于图的更深一步的操作，通过对于顶点之间联系的变动来建立新的联系。 开始的时候不知道如何通过逻辑关系建立图中各个顶点的关系。后来通过查课本和资料，建立了各个顶点之间的联系。 指导老师评阅意见 指导老师： 2013 年 12 月 5 日 填写内容时，可把表格扩大。

附：实验源程序代码

（1） 存储矩阵和最短路径的程序： #include #include #define MAX 100

#define MAXINT 1000 /*typedef struct node{ int number; struct node *next; }edgeNode;*/ typedef struct { int vexnum; int arcnum;

int arcs[MAX][MAX]; }Mgragh;

int creat_mgragh(Mgragh &mg) { int i=0; int j=0; int k=0; int weight; cout<<\输入顶点数\ cin>>mg.vexnum; cout<<\输入边数\ cin>>mg.arcnum; for(i=0;i

{ mg.arcs[i][j]=MAXINT; } } for(k;k

cin>>i;

if(i<=mg.vexnum) {

cout<<\输入边的终点：\终点的顶点不可超过\ while(1) {

cin>>j;

if(j<=mg.vexnum) {

cout<<\输入权值\ cin>>weight; mg.arcs[i-1][j-1]=weight; //mg.arcs[j-1][i-1]=weight; break; } else

cout<<\重新输入！\ }

break;

} else

cout<<\重新输入！\ } } for(i=0;i

void Dijkstra(Mgragh &g,int v0)

{

creat_mgragh(g); int path[MAX]; int dist[MAX];

int s[MAX];//s数组用来放在s中的顶点，开始的时候只有v0 ；当s[v]==0时，则v没有在s数组中 int v;

for(v=1;v

s[v]=0;

dist[v]=g.arcs[v0][v];

if(dist[v]

//cout<

dist[v0]=0;

s[v0]=1;

for(int i=0;i

int min=MAXINT; v=-1; //int w；

for(int w=1;w

if(s[w]==0&&dist[w]

v=w;

min=dist[w]; } }

if(v!=-1) {

s[v]=1;//将该v放入s数组中 for(int j=0;j

if(s[j]==0&&(min+g.arcs[v][j]

dist[j]=min+g.arcs[v][j]; path[j]=v; } }

} }

for(int i=1;i

{

if(dist[i]

cout<<\ int next=path[i]; while(next!=v0) {

cout<<\ next=path[next]; }

cout<<\ } else if(i!=v0)

cout<<\ } }

int main() { Mgragh mg; //creat_mgragh(mg); int v0=0; Dijkstra(mg,v0); system(\ return 0; }

（2） 最小生成树的程序

#include #include #define TURE 999 typedef struct ArcNode { char vexs[10]; int edgs[10][10]; int n,e; }MGraph; struct edg { int v1; int v2; int cost;

}A[10],B[10]; //创建图

void GreateMGraph(MGraph *G) {