图的建立及遍历输出

发布网友 发布时间：2022-04-19 09:43

我来回答

共1个回答

热心网友 时间：2023-07-01 15:42

#include <iostream.h>
#include <stdlib.h>

#define INFINITY 0

#define MAX_VERTEX_NUM 10 //最大顶点数

#define MAX_EDGE_NUM 40 //最大边数

typedef enum {DG,DN,UDG,UDN}Graphkind;

typedef char VertexType; //顶点数据类型

typedef struct ArcCell
{
int adj; //无权图，1或0表示相邻否；带权图则是权值。
//int *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数。
Graphkind kind;
}MGraph;

int LocateVex(MGraph G,VertexType v1)
{
int i;
for(i=0;i<G.vexnum;i++)
if(G.vexs[i]==v1)
return i;
return -1;
}

int CreatUDN(MGraph &G)
// 采用数组表示法，构造无向网 G
{
VertexType v1,v2;
int w,j;
cout<<"输入图的顶点数"<<endl;
cin>>G.vexnum;
cout<<"输入图的弧数"<<endl;
cin>>G.arcnum;
for(int i=0;i<G.vexnum;i++)
{
cout<<"输入顶点向量"<<endl;
cin>>G.vexs[i];
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j].adj=INFINITY;
}
for(int k=0;k<G.arcnum;++k) //构造邻接矩阵
{
cout<<"输入边依附的两个顶点"<<endl;
cin>>v1>>v2;
cout<<"输入此边的权值"<<endl;
cin>>w;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=G.arcs[i][j].adj;
}
return 1;
}

void dispMGraph(MGraph G)
{
cout<<"图的邻接矩阵图是："<<endl;
for(int i=0;i<G.vexnum;i++)
{
for(int j=0;j<G.vexnum;j++)
cout<<" "<<G.arcs[i][j].adj;
cout<<endl;
}
}

void main()
{
MGraph G;
CreatUDN(G);
dispMGraph(G);
}

// 邻接表 表示:

#include <iostream.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 20 //最大顶点数

#define MAX_EDGE_NUM 40 //最大边数

int visited[ MAX_VERTEX_NUM];

typedef int VertexType ; //顶点数据类型

typedef struct ArcNode
{
int adjvex;
int weight;
struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;

void CreateDG(ALGraph &G)
{
int i,j,k;
ArcNode *p;
cout<<"创建一个图:"<<endl;
cout<<"顶点数:"; cin>>G.vexnum;cout<<endl;
cout<<"边数:"; cin>>G.arcnum; cout<<endl;
for(i=0;i<G.vexnum;i++)
{
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
for(k=0;k<G.arcnum;k++)
{
cout<<"请输入第"<<k+1<<"条边:";
cin>>i>>j;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
}
}

void Disp(ALGraph G)
{
int i,j;
ArcNode *p;
cout<<"输出图为:"<<endl;
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
j=0;
while(p!=NULL)
{
cout<<"("<<i<<","<<p->adjvex<<")";
p=p->nextarc;
j=1;
}
if(j==1)
cout<<endl;
}
}

void dfs(ALGraph G,int v) //深度优先遍历
{
ArcNode *p;
cout<<v<<" ";
visited[v]=1;
p=G.vertices[v].firstarc;
while(p!=NULL)
{ if(!visited[p->adjvex])
dfs(G,p->adjvex);
p=p->nextarc;
}
return ;
}

void dfs1(ALGraph G)
{
int i;
for(i=0;i<G.vexnum;i++)
if(visited[i]==0)
dfs(G,i);
}

void main()
{
ALGraph G;
CreateDG(G);
int v;
Disp(G);
cout<<"输入顶点:";
cin>>v;
cout<<"深度优先序列:";
dfs1(G);
cout<<endl;
}