① 有向圖的鄰接矩陣存儲
有向圖的鄰接矩陣，用類似於二維鏈表做過，下面是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的平方）