以邻接链表的方式确定一个无向网

发布网友 发布时间：2022-05-25 14:07

我来回答

共1个回答

热心网友 时间：2023-11-03 18:57

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
#define max 10

class node_shuzu;
//邻接链表链结点
class node_lianbiao
{
public:
int position;
int quan;
node_lianbiao * next;

node_lianbiao(int a,int b){position=a;quan=b; next=NULL;}
node_lianbiao(){next=NULL;}
~node_lianbiao(){}
};
//邻接链表数组结点
class node_shuzu
{
public:
node_lianbiao *next;
string data;

node_shuzu(){next=NULL;}
~node_shuzu(){}
};
//图类
class tu_juzhen
{
private:
int juzhen[max][max];
string dingdian[max];
int numding,numhu;
node_shuzu lianbiao[max];
public:
tu_juzhen(){}
void creat();
int locateding( string );//返回这个顶点的第几位
int isempty();//判断是否为空
void guangbianli();
void printgragh();
void prim();
void ktus();
};

int tu_juzhen::locateding(string b)
{
int i=0;
for(;i<numding;i++)
{
if(dingdian[i]==b) return i;
}
return -1;
}

void tu_juzhen::creat()
{
string data,data1,data2;
int n,m,num;
//输入顶点个数
cout<<"请输入顶点个数：";
cin>>numding;
//输入顶点
cout<<"请依次输入各个顶点：";
for(int i=0;i<numding;i++)
{
cin>>dingdian[i];
}
//以邻接链表确定有向网
node_lianbiao * * po[max];//指向数组链表的最后一位的next成员

for (int i=0;i<numding;i++)
{lianbiao[i].data=dingdian[i];po[i]=&lianbiao[i].next;}

cout<<"输入所有的弧，格式为:“顶点顶点权值”，以格式 0 0 0结束"<<endl;
do
{

cin>>data1>>data2>>num;
n=locateding(data1);
m=locateding(data2);
//node_lianbiao a(m,num);
if((n!=-1)&&(m!=-1))
{
*po[n]=new node_lianbiao(m,num);
po[n]=&((*po[n])->next);
*po[m]=new node_lianbiao(n,num);
po[m]=&((*po[m])->next);
}
}
while((data1!="0")&&(data2!="0")&&(num!=0));

//根据邻接链表建立邻接矩阵
node_lianbiao * po1;

for (int i=0;i<numding;i++)//初始化
for (int j=0;j<numding;j++)
juzhen[i][j]=0;

for(int i=0;i<numding;i++)
{
po1=lianbiao[i].next;
while(po1)
{
n=po1->position;
m=po1->quan;
po1=po1->next;
juzhen[i][n]=m;
};
}
}

void tu_juzhen::printgragh()//打印有向网的邻接矩阵
{
cout<<endl;
cout<<"邻接矩阵为："<<endl;
int i,j;
for(i=0;i<numding;i++)
{
for(j=0;j<numding;j++)
{
cout<<juzhen[i][j]<<" ";
}
cout<<endl;
}
}

void tu_juzhen::guangbianli()
{
int * flag =new int[numding];//记录顶点访问状态
int * ilie =new int[numding];//记录未广度遍历的顶点数
int front,rear;
front=0;rear=0;
int i;
cout<<endl;
cout<<"该图的广度优先遍历为："<<endl;
for( i=0;i<numding;i++)flag[i]=0;//状态初始化

do
{
for( i=0;i<numding;i++)if(flag[i]==0)break;
if(i!=numding)
{
cout<<"-->"<<dingdian[i]<<endl;
rear++;
ilie[rear]=i;
cout<<"入队列"<<dingdian[i]<<endl;
flag[i]=1;
do
{
cout<<"出队列"<<dingdian[ilie[front+1]]<<endl;
front=(front+1)%20;
for(int j=0;j<numding;j++)
{
if((juzhen[ilie[front]][j]!=0)* (flag[j]!=1))
{
rear++;
ilie[rear]=j;
cout<<"入队列"<<dingdian[j]<<endl;
flag[j]=1;
cout<<"-->"<<dingdian[j]<<endl;
}
}
}
while((((rear+1)%20)!=front) * (rear!=front));//队列结束条件。队列满或空
}
}
while(i!=numding);
cout<<endl;
}

void tu_juzhen::prim()
{
int flag[max],dian[max],n,m,l,p=0;//flag[]标志结点所属树,p表示已写出结点个数

int juzhen1[max][max];//矩阵的映像
for(int i=0;i<numding;i++)
for (int j=0;j<numding;j++)
juzhen1[i][j]=juzhen[i][j];
for(int i=0;i<numding;i++)flag[i]=0;//初始化

cout<<"普里姆算法"<<endl;
//先找到最小的一个弧
l=n=m=10000;//假设一个很大值
for(int i=0;i<numding;i++)
for (int j=i;j<numding;j++)
{
if((juzhen1[i][j]!=0)&&(juzhen1[i][j]<l))
{
l=juzhen1[i][j];
m=i;n=j;
}
}
p+=2;dian[0]=m;dian[1]=n;flag[n]=flag[m]=1;
cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;

while(p<numding)
{
l=n=m=10000;
for(int i=0;i<p;i++)
{
for (int j=0;j<numding;j++)
{
if((juzhen1[j][dian[i]]!=0)&&(juzhen1[j][dian[i]]<l)&&(flag[j]==0))
{
l=juzhen1[j][dian[i]];
n=dian[i];m=j;
}
}
}
if((m!=10000)&&(n!=10000)&&(l!=10000))
{
dian[p]=m;
p++;
cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;

flag[m]=1;
}
}
cout<<endl;
}

void tu_juzhen::ktus()
{
int flag[max],n,m,l,p,k;//flag[]标志结点所属树,p表示已写出弧个数

int juzhen1[max][max];//矩阵的映像
for(int i=0;i<numding;i++)
for (int j=0;j<numding;j++)
juzhen1[i][j]=juzhen[i][j];

cout<<"克鲁斯卡尔算法:"<<endl;

for(int i=0;i<numding;i++)flag[i]=0;//初始化
k=p=0;
while (p<(numding-1))
{
l=n=m=10000;//假设一个很大值

for(int i=0;i<numding;i++)
for (int j=0;j<numding;j++)
{
if((juzhen1[i][j]!=0)&&(juzhen1[i][j]<l))
{
l=juzhen1[i][j];
m=i;n=j;
}
}

if((m!=10000)&&(n!=10000)&&(l!=10000))
{
if(flag[n]!=0)
if(flag[m]!=0)
if(flag[n]==flag[m]) //成环情况
{continue;}
else
{
cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;
p++;
flag[numding]=flag[m];
for(int h=0;h<numding;h++)
if(flag[h]==flag[numding])
flag[h]=flag[n];
}
else
{cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;flag[m]=flag[n];p++;}//后结点为新
else
if(flag[m]!=0)
{cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;flag[n]=flag[m];p++;}//前结点为新
else
{cout<<dingdian[n]<<"与顶点"<<dingdian[m]<<"相连 权值为"<<l<<endl;flag[n]=flag[m]=k;p++;}//前后结点均为新

juzhen1[m][n]=juzhen1[n][m]=0;
}
k++;

};
cout<<endl;
}
void main()
{
tu_juzhen li;
li.creat();
li.printgragh();
li.guangbianli();

li.ktus();
li.prim();

}