#include<stdlib.h>
#define MaxSize 20
struct ArcNode
{
int adjvex
struct ArcNode *nextarc
}
struct Vnode
{
int data
struct ArcNode *firstarc
}
struct Vnode AdjList[MaxSize]
int m,n,v,cord
void main()
{
void creatgraph(struct Vnode A[MaxSize])
void dfs(struct Vnode A[MaxSize])
do
{
printf("\n主菜单")
printf("\n 1 建立无向图的邻接表")
printf("\n 2 按深度遍历图")
printf("\n 3 结束程序运行")
printf("\n-----------------------------------"扮灶)
printf("\n请输入您的选择 1, 2, 3 -->")
scanf("%d",&cord)
switch(cord)
{
case 1:
creatgraph(AdjList)
break
case 2:
dfs(AdjList)
break
case 3:
exit(0)
}
}while(cord<=3)
}//main end
void creatgraph(struct Vnode A[MaxSize])
{
int i,j,k
struct ArcNode *p
printf("input arces and vexes:")
scanf("%d %d"袜橡,&m,&n)
for(k=0k<nk++)
{
printf("\ninput arc:")
scanf("%d%d",&i,&j)
p=(struct ArcNode*)malloc(sizeof(struct ArcNode))
p->adjvex=j
p->nextarc=A[i-1].firstarc
A[i-1].firstarc=p
p=(struct ArcNode*)malloc(sizeof(struct ArcNode))
p->adjvex=i
p->nextarc=A[j-1].firstarc
A[j-1].firstarc=p
}
printf("\n")
for(k=0k<nk++)
{
printf("%d",A[k].data)
p=A[k].firstarc
while(p)
{
printf("%d",p->adjvex)
p=p->nextarc
}
printf("\n")
}
}///厅好扮creatgraph end
void dfs(struct Vnode A[MaxSize])
{
struct ArcNode *p,*ar[MaxSize]
int x,i,y,top=-1
int visited[MaxSize]
for(i=0i<ni++)
visited[i]=0
printf("\ninput x:")
scanf("%d",&x)
printf("%d",x)
visited[x-1]=1
p=A[x-1].firstarc
while((p)||(top>=0))
{
if(!p)
{
p=ar[top]
top--
}
y=p->adjvex
if(visited[y-1]==0)
{
visited[y-1]=1
printf("->%d",y)
p=p->nextarc
if(p)
{
top++
ar[top]=p
}
p=A[y-1].firstarc
}
else p=p->nextarc
}
}
#include <iostream>#include <fstream>
using namespace std
class edgeset{
public:
int from//边起始点
int end/巧御/边终止点
int w//边的权值
}//定义一个类用来存放图的边的信息（kruskal算法中用到）
//==============prim算法=============================
void prim(int a[11][11],int (&path)[11][11]){
cout<<"运用prim算法"<<endl
int i,j,k
int mini,minj,min,sum=0
a[0][0]=-1
cout<<"通道铺设情况：(0-10分别对应点a-k)"<<endl
for(k=1k<11k++){
min=100
for(i=0i<11i++){
for(j=0j<11j++){
if(a[i][i]+a[j][j]==-1 &&a[i][j]>0 &&a[i][j]<min){
min=a[i][j]
mini=i
minj=j
}
}
}
if(a[mini][mini]==-1){
cout<枣锋<"("<<mini<<","<<minj<<")"
path[mini][minj]=a[mini][minj]
path[minj][mini]=a[mini][minj]
a[minj][minj]=-1
}
else{
cout<<"("<<mini<<","<<minj<<")"
path[mini][minj]=a[mini][minj]
a[mini][mini]=-1
path[minj][mini]=a[mini][minj]
}
sum=sum+min
}
cout<<endl
cout<<"建设费用为:"<<sum<<endl
//=============最小生成树的邻接矩阵输出==============
cout<<"最小生成树对应的邻接矩阵为："<<endl
for(int x=0x<11x++){
for(int y=0y<11y++){
cout<<path[x][y]<<" "
}
cout<<endl
}
}
//===================================================
//===========kruskal算法=============================
void kruskal(int a[11][11],int(&kpath)[11][11]){
cout<<"运用kruskal算法"<<endl
int i,j,k,d
int num=0
edgeset edge[18]
//将邻接矩阵中权值大于1的边对应的点及凳宽晌权值存到一个边类
for(i=0i<11i++){
for(j=i+1j<11j++){
if(!a[i][j]==0){
edge[num].from=i
edge[num].end=j
edge[num].w=a[i][j]
num++
}
}
}
edgeset tmp
//===================================================
//=======将边按权值大小排序==========================
for(i=1i<18i++){
for(j=0j<18-ij++){
if(edge[j].w>edge[j+1].w){
tmp=edge[j]
edge[j]=edge[j+1]
edge[j+1]=tmp
}
}
}
//===================================================
int m1,m2
edgeset c[11]
int s[11][11]
for(i=0i<11i++)
for(j=0j<11j++){
if(i==j)
s[i][j]=1
else
s[i][j]=0
}
k=1
d=0
int sum=0
cout<<"通道铺设情况：(0-10分别对应点a-k)"<<endl
while(k<11){
for(i=0i<11i++){
if(s[i][edge[d].from]==1)
m1=i
if(s[i][edge[d].end]==1)
m2=i
}
if(m1!=m2){
c[k-1]=edge[d]
cout<<"("<<c[k-1].from<<","<<c[k-1].end<<")"
kpath[c[k-1].from][c[k-1].end]=c[k-1].w
kpath[c[k-1].end][c[k-1].from]=c[k-1].w
sum=sum+c[k-1].w
k++
for(j=0j<11j++){
if(s[m2][j]!=0){
s[m1][j]=s[m2][j]
s[m2][j]=0
}
}
}
d++
}
cout<<endl
cout<<"建设费用为："<<sum<<endl
//=============最小生成树的邻接矩阵输出==============
cout<<"最小生成树对应的邻接矩阵为："<<endl
for(int x=0x<11x++){
for(int y=0y<11y++){
cout<<kpath[x][y]<<" "
}
cout<<endl
}
}
void main(){
int h,z
int a[11][11]
int path[11][11]={0}
//==============数据读入（图的邻接矩阵）=============
ifstream in("picture.txt")
for(h=0h<11h++){
for(z=0z<11z++){
in>>a[h][z]
}
}
//===================================================
cout<<"图的邻接矩阵："<<endl
for(int i=0i<11i++){
for(int j=0j<11j++){
cout<<a[i][j]<<" "
}
cout<<endl
}
int kpath[11][11]={0}
int b[11][11]
ifstream in2("picture.txt")
for(h=0h<11h++){
for(z=0z<11z++){
in2>>b[h][z]
}
}
int ch
cout<<"请选择算法(1:prim算法/2:kruskal算法):"
cin>>ch
cout<<endl
switch(ch){
case 1:prim(a,path)//调用prim算法函数
break
case 2:kruskal(b,kpath)
break
}
}
//希望对你有所帮助
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）