图的邻接表创造及遍历输出

#include<iostream>

using namespace std;

#define MVNum 100

#define MaxInt 32767//代表无穷大

#define MVNum 100//最大顶点数 

int visited[100]={0}; 

/*邻接矩阵表示图*/ 

typedef char VerTexType;//假设顶点的数据类型为字符型

typedef int ArcType;//假设边的权值类型为整型

typedef struct 

{

VerTexType vexs[MVNum];//顶点表

AreType arcs[MVNum][MVNum];//邻接矩阵

int vexnum,arcnum;//图的点数和边数 

 }AMGraph;

 /*创建邻接矩阵*/ 

Status CreateUDN(AMGraph &G)

{

cin>>G.vexnum>>G.arcnum;//输入总顶点数边总边数

for(int i=0;i<G.vexnum;i++)

{

cin>>G.vexs[i];//输入点的信息 

}

for(int i=0;i<G.vexnum;i++)//初始化邻接矩阵 

for(int j=0;j<G.vexnum;j++)

G.arcs[i][j]=MaxInt;

for(int k=0;k<G.arcnum;k++)

{  int w;//w为权值 

cin>>v1>>v2>>w;

i=LocateVex(G,v1); 

j=LocateVex(G,v2);

G.arcs[i][j]=w;

G.arcs[j][i]=G.arcs[i][j]; 

}

return OK; 

 } 

/*邻接表表示图 */

typedef struct ArcNode  //边结点 

{ int adjvex;

  struct ArcNode *nextarc;

}ArcNode;

typedef struct VNode  //顶点(表头)信息 

{ int data;

  ArcNode *firstarc;//向后接边节点 

}VNode,AdjList[MVNum];

typedef struct  //邻接表 

{ AdjList vertices;

  int vexnum,arcnum;

}ALGraph;

int LocateVex(ALGraph G,int v)

{ for(int i=0;i<G.vexnum;i++)

{

if(G.vertices[i].data==v)

return i;//返回该节点的下标 

}

}

/*创建邻接表表示图 */

int CreateUDG(ALGraph &G)

{ printf("请分别输入总顶点数和总边数：");

  cin>>G.vexnum>>G.arcnum;

  int i,j,k;

  for(i=0;i<G.vexnum;i++)

  { cout<<"请输入顶点值"<<endl; 

    cin>>G.vertices[i].data;

    G.vertices[i].firstarc=NULL;

  }

  for(k=0;k<G.arcnum;k++)

  { int v1,v2;

    cout<<"请输入该边依附的顶点:"<<endl;

    cin>>v1>>v2; 

    i=LocateVex(G,v1);

    j=LocateVex(G,v2);

    ArcNode *p1=new ArcNode;

    p1->adjvex=G.vertices[j].data;//将节点值赋值 

    p1->nextarc=G.vertices[i].firstarc;

    G.vertices[i].firstarc=p1;

    ArcNode *p2=new ArcNode;

    p2->adjvex=G.vertices[i].data;

    p2->nextarc=G.vertices[j].firstarc;

    G.vertices[j].firstarc=p2;

  }

  return 1;

} 

/*DFS深度遍历图*/ 

void DFS_AL(ALGraph G,int v)//下标v 

{

cout<<G.vertices[v].data<<" ";//输出遍历的节点值 

visited[v]=1;

ArcNode *p=G.vertices[v].firstarc;

while(p)

{

int w=p->adjvex;//w为节点值 

if(visited[LocateVex(G,w)]==0)

DFS_AL(G,LocateVex(G,w));

p=p->nextarc;

}

}

/*普里姆算法*/

struct 

{

VerTexType adjvex;//最小边在U中的那个顶点

ArcType lowcost;//最小边的权值 

 }closedge[MVNum];

 void MiniApanTree_Prim(AMGraph G,VerTexType u)//u为起点 

 {

  int k=LocateVex(G,u);

  for(int j=0;j<G.vexnum;j++)

  {

  if(j!=k)

  closedge[j]={u,G.arcs[k][j]};//adjvex,lowcost 

}

closedge[k].lowcost=0;

for(int i=1;i<G.vexnum;i++)//只需要选n-1个点 

{

k=Min(closedge); 

  } 

  } 

int main()

{ ALGraph G;

  CreateUDG(G);

  int i;

  for(i=0;i<G.vexnum;i++)

  { VNode temp=G.vertices[i];

    ArcNode *p=temp.firstarc;//指向下一个邻接点  

    if(p==NULL)

    { cout<<G.vertices[i].data<<endl;

    }

    else

    { cout<<temp.data;

      while(p)

      { 

  cout<<"->"<<p->adjvex;

        p=p->nextarc;

  } 

}

cout<<endl;

  }

  int v;

  cout<<"请输入出发顶点值："; 

  cin>>v;  

  DFS_AL(G,LocateVex(G,v));//输入顶点值，但是以下标运算 

   return 0; 

}

/*图的邻接表过程下标和节点值的操作是关键*/ 

/*在一个连通网的所有生成树中，各边的代价之和最小的那颗生成树称为该连通树的最小代价生成树*/