① 有向图的邻接矩阵存储
有向图的邻接矩阵，用类似于二维链表做过，下面是c++的代码：
//顶点结构
structVexNode
{
chardata;
ArcNode*firstarc;
};
//弧结构
structArcNode
{//邻接顶点的下标
intadjvex;
ArcNode*nextarc;
};
classAdjList
{
private:
VexNodedata[100];
intvn,an;//顶点数弧数
public:
//构造函数以及其他的一些函数
AdjList();
virtual~AdjList();
};
② 有向图的邻接表存储如图所示，请画出其邻接矩阵存储结构
有向图的邻接表存储如图所示，其邻接矩阵存储如图：
③ 带权邻接矩阵的图的邻接矩阵表示法
1.图的邻接矩阵表示法
在图的邻接矩阵表示法中：
① 用邻接矩阵表示顶点间的相邻关系
② 用一个顺序表来存储顶点信息
2.图的邻接矩阵(Adjacency Matrix)
设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
【例】下图中无向图G 5 和有向图G 6 的邻接矩阵分别为A l 和A 2 。
3.网络的邻接矩阵
若G是网络，则邻接矩阵可定义为：
其中：
w ij 表示边上的权值;
∞表示一个计算机允许的、大于所有边上权值的数。
【例】下面带权图的两种邻接矩阵分别为A 3 和A 4 。
4.图的邻接矩阵存储结构形式说明
#define MaxVertexNum l00 //最大顶点数，应由用户定义
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
typedef struct{
VextexType vexs[MaxVertexNum] //顶点表
EdeType edges[MaxVertexNum][MaxVertexNum];
//邻接矩阵，可看作边表
int n，e; //图中当前的顶点数和边数
}MGragh;
注意：
① 在简单应用中，可直接用二维数组作为图的邻接矩阵(顶点表及顶点数等均可省略)。
② 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型。
③ 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。
④ 邻接矩阵表示法的空间复杂度S(n)=0(n 2 )。
5.建立无向网络的算法。
void CreateMGraph(MGraph *G)
{//建立无向网的邻接矩阵表示
int i，j，k，w;
scanf(%d%d，&G->n，&G->e); //输入顶点数和边数
for(i = 0;i < n;i++) //读人顶点信息，建立顶点表
{
G->vexs=getchar();
}
for(i = 0;i < n;i++)
{
for(j = 0;j < n;j++)
{
G->edges[j] = 0; //邻接矩阵初始化
}
}
for(k = 0;k < e;k++)
{//读入e条边，建立邻接矩阵
scanf(%d%d%d，&i，&j，&w); //输入边(v i ,v j )上的权w
G->edges[j]=w;
G->edges[j]=w;
}
}//CreateMGraph
该算法的执行时间是0(n+n 2 +e)。由于e
根据图的定义可知，图的逻辑结构分为两部分：V和E的集合。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，称这个二维数组为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。
④ 代码实现图的邻接矩阵存储，并打印结果图中的节点包括v1,v2,v3,v4 边包括：<v1,v2＞5
摘要 "void printGraph(MGraph *g) { //输出邻接矩阵
⑤ 1、参考某城市交通图（设该图中有6个城市），以邻接矩阵或邻接表存储该图，要求图中每一个城市的结点除了
二题懒得做，一题以前做过：
我用的是vc++工程
//************head.h*************
#define MaxVertexnum 25
#define MaxVerNum 25
typedef struct{
int p[25];
int d;
}path;
typedef struct{
int vexs[MaxVertexnum];
int edges_file[MaxVertexnum][MaxVertexnum];
int edges_cost[MaxVertexnum][MaxVertexnum];
int edges_time[MaxVertexnum][MaxVertexnum];
int Vnum,Enum;
}Mgraph, *PtrMgraph;
void create(PtrMgraph &M);
void Shortestpath_2(Mgraph *G,path pp[25]);
void shortestpath_1(Mgraph *G,int v0,path pp[25]);
void Bubble_sort(path R[],int n);
void print(int v0,path pp[25]);
void display();
//***********soure.cpp************
#include"header.h"
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
string stu[25]={"北京", "长春 " ,"成都" , "大连 ", "福州" ,"广州" ,"贵阳", "哈尔滨","呼和浩特",
"昆明","兰州","柳州", "南昌","南宁", "上海" ,"沈阳" ,"深圳"
,"天津", "武汉","乌鲁木齐","西安","西宁","徐州","郑州","株州"};
void create(PtrMgraph &M){
M=new Mgraph;
int i,j,a,b,k,m,t;
ifstream infile("城市.txt",ios::in);
if(!infile)
{
cerr<<"open error!"<<endl;
exit(1);
}
infile>>M->Vnum>>M->Enum;
for(i=0;i<M->Vnum;i++)
infile>>M->vexs[i];
for(i=0;i<M->Vnum;i++)
for(j=0;j<M->Vnum;j++){
M->edges_file[i][j]=50000;
M->edges_cost[i][j]=50000;
M->edges_time[i][j]=50000;
}
for(i=0;i<M->Enum;i++)
{
infile>>a>>b;
infile>>k>>m>>t;
M->edges_file[a-1][b-1]=k;
M->edges_file[b-1][a-1]=k;
M->edges_cost[a-1][b-1]=m;
M->edges_cost[b-1][a-1]=m;
M->edges_time[a-1][b-1]=t;
M->edges_time[b-1][a-1]=t;
}
infile.close();
//return M;
}
void Shortestpath_2(Mgraph *G,path pp[25]){
int v,w,u,i,j,k;
int p[25][25], D[25][25];
for(v=0;v<G->Vnum;++v)
for(w=0;w<G->Vnum;++w){
D[v][w]=G->edges_file[v][w];
if(D[v][w]<50000){
p[w][v]=v;
}
else
if(v!=w){
p[v][w]=-2;
}
else{
p[v][w]=-1;
}
}
for(u=0;u<G->Vnum;++u)
for(v=0;v<G->Vnum;++v)
for(w=0;w<G->Vnum;++w)
if(D[v][u]+D[u][w]<D[v][w]){
D[v][w]=D[v][u]+D[u][w];
p[v][w]=u;
}
/*for(i=0;i<7;i++)
for(j=0;j<9;j++)
cout<<p[i][j]<<" ";*/
cout<<"请输入 俩城市序号"<<endl;
cin>>i>>j;
cout<<D[i-1][j-1]<<":";
Mgraph *M;
create(M);
shortestpath_1(M,i-1,pp);
for(k=0;k<25;k++)
if(pp[k].d==D[i-1][j-1])
break;
int r=0;
while(pp[k].p[r]>0){
cout<<stu[pp[k].p[r]]<<"<--";
r++;
}
cout<<stu[i-1]<<endl;
/*cout<<j;
k=p[i][j];
while(k>0&&k!=i){
cout<<"<-"<<k;
k=p[i][k];
}
cout<<"<-"<<i<<endl;
/*for(i=0;i<G->Vnum;i++)
for(j=0;j<G->Vnum;j++)
if(p[i][j]>0&&i!=j){
cout<<i<<"->";
k=p[i][j];
cout<<k<<"->";
while(p[k][j]!=j)
{cout<<k<<"->";
k=p[k][j];
}
cout<<j<<endl;
cout<<"值为："<<D[i][j]<<endl;*/
}
void shortestpath_1(Mgraph *G,int v0,path pp[25]){
int P[25]={0},D[25]={50000};
int i,j,v,pre,w;
int min;
int final1[MaxVerNum];
for(v=0;v<G->Vnum;v++){
final1[v]=0;
D[v]=G->edges_file[v0][v];
P[v0]=-1;
if(D[v]<50000&&v!=v0)
P[v]=v0;
if(D[v]==50000)
P[v]=-2;
}
D[v0]=0;
final1[v0]=1;
for(i=1;i<G->Vnum;i++){
min=50000;
for(w=0;w<G->Vnum;w++)
if(!final1[w])
if(D[w]<min){
v=w;
min=D[w];
}
final1[v]=1;
for(w=0;w<G->Vnum;++w)
if(!final1[w]&&(min+G->edges_file[v][w]<D[w])){
D[w]=min+G->edges_file[v][w];
P[w]=v;
}
}
for(i=1;i<G->Vnum;i++){
if(P[i]==-2){
pp[i].d=50000;
pp[i].p[0]=i;
// cout<<"max"<<i<<endl;
}
else{
j=0;
pp[i].d=D[i];
pp[i].p[0]=i;
//cout<<D[i]<<i;
pre=P[i];
pp[i].p[++j]=pre;
while(pre>0){
//cout<<"<--"<<pre;
pre=P[pre];
pp[i].p[++j]=pre;
}
//cout<<"<--0"<<endl;
}
}
}
void Bubble_sort(path R[],int n){
int i,j,swap;
for(i=1;i<n;i++){
swap=0;
for(j=1;j<=n-i;j++ )
if(R[j].d>R[j+1].d){
R[0]=R[j];
R[j]=R[j+1];
R[j+1]=R[0];
swap=1;
}
if(swap==0)
break;
}
}
void print(int v0,path pp[25]){
Bubble_sort(pp,25);
int i,j;
cout<<"按里程升序排列："<<endl;
for(i=1;i<25;i++){
cout<<pp[i].d<<":";
j=0;
while(pp[i].p[j]>0){
cout<<stu[pp[i].p[j]]<<"<--";
j++;
}
cout<<stu[v0]<<endl;
}
}
void display(){
int i;
for(i=0;i<25;i++)
cout<<i+1<<" "<<stu[i]<<" ";
}
//***************mytest.cpp
#include<iostream>
#include<fstream>
#include"header.h"
using namespace std;
void main()
{ int a[25][25],b[25][25],n;
path pp[25];
for(int i=0;i<25;i++)
for(int j=0;j<25;j++)
pp[i].p[j]=0;
Mgraph *M;
create(M);
cout<<"********交通咨询系统**********"<<endl;
int ch;
cout<<"查询该城市到其余城市的交通信息 1"<<endl;
cout<<"查询俩城市之间的交通信息 2"<<endl;
cout<<"请选择!"<<endl;
cin>>ch;
while(ch!=0)
{
switch(ch){
case 1:cout<<"输入查询的城市"<<endl;display();cin>>n;shortestpath_1(M,n-1,pp); print(n-1,pp);
break;
case 2: Shortestpath_2(M,pp);break;
//case 0:cout<<"------exit!";break;
default:break;
}
cout<<"查询该城市到其余城市的交通信息 1"<<endl;
cout<<"查询俩城市之间的交通信息 2"<<endl;
cout<<"请选择!"<<endl;cin>>ch;
}
}
⑥ 存储图时，哪些情况用邻接矩阵方便
如果边比较少的情况下，用邻接矩阵节省存储空间。边比较多就可以选择邻接矩阵
⑦ 数据结构：画出下图的邻接矩阵存储结构
我定义一个int型二维数组 G[5][5].
点a，b,c,d分别定义编号为1,2,3,4
G[u][v]的值为零 则有向边(u,v)不联通
若值为1则有向边(u,v)联通
又因为在c,c ,java中 数组的范围是从0开始的
为了使用方便 我们不使用下标为0的数组元素
因为有四个点 所以我们定义一个5x5的二维数组
矩阵数据如下
00000
00110
00000
00001
01000
其中 G[1][2] G[1][3]G[3][4]G[4][1]的值为一
⑧ 请画出下图的邻接矩阵和邻接表的存储方式。 谁能帮忙解决下
邻接矩阵：
v0v1v2v3v4
v0 0 1 01 1
v11 0 11 0
v20 1 01 1
v31 1 10 1
v41 0 1 1 0
：
v0->
⑨ 用邻接矩阵法存储一个图所需的存储单元的数目与图的编数有关是对还是错
错 邻接矩阵只和点数有关
⑩ 用邻接矩阵储存图，所占用的储存空间大小只与图中顶点个数
图的邻接矩阵存储所占用空间大小只与顶点个数有关，更准确地说，设顶点n个，则与n^2成正比（n的平方）