① 有向圖的鄰接表存儲如圖所示，請畫出其鄰接矩陣存儲結構
有向圖的鄰接表存儲如圖所示，其鄰接矩陣存儲如圖：
② 給出一個有向圖的鄰接表存，怎麼畫出其鄰接矩陣存儲，求詳解，謝謝了
將每一行的鏈表中的結點的鄰接點下標（比如第i個頭結點的鏈表中的弧結點中的信息為j），放到鄰接矩陣中就是A[i][j]=1，如果結點還有權值則為權值，除了這些非0元素外，其他的都是0（如果有權圖則其他的都是無窮大）
如果有向圖的鄰接表中有k個弧（邊）結點，則鄰接矩陣中就有k個1（或者權值）
③ 帶權鄰接矩陣的圖的鄰接矩陣表示法
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，完了後順鏈尋找沒有訪問的鄰接頂點，自然鏈表中的第一個結點就是v3，接著轉到v3再來深度優先，訪問v3後，在其鏈表中第一個鄰接頂點是v4
接著訪問v4，下面走不通，回到v3，繼續順鏈往後，自然是v5，v5的鄰接頂點中v2還沒有訪問
所以序列為v1, v3, v4, v5, v2
再看廣度優先，從某個頂點完成後，需要一口氣將其鄰接未訪問的所有頂點都訪問，後面類推
於是過程是先v1，再順鏈將v3，v2依次訪問完，然後再依次訪問v3和v2的各個未訪問鄰接頂點，v3鏈表中順鏈可以訪問v4，v5，所以最後訪問序列為v1, v3, v2, v4, v5
⑤ 請編寫一個完整的程序，建立有向圖的鄰接表存儲結構，要求：
給你一個鄰接表的完整程序：
#include <iostream.h>
struct node
{
int data;
node *next;
};
class list
{
public:
list(){head=NULL;};
void MakeEmpty();
int Length();
void Insert(int x,int i);//將x插入到第i個結點（不含頭結點）的之後
void Insertlist(int a,int b);//將節點b插入a之前
int Delete(int x);
int Remove(int i);
int Find(int x);
void Display();
private:
node *head;
};
void list::Display()
{
node *current=head;
while (current!=NULL)
{
cout<<current->data<<" ";
current=current->next;
}
cout<<endl;
}
void list::MakeEmpty()
{
head=NULL;
}
int list::Length()
{int n=1;
node *q=head;
if(q==NULL)
n=1;
else
while(q!=NULL)
{
n++;
q=q->next;
}
return n;
}
int list::Find(int x)//在鏈表中查找數值為x的結點，成功返回1，否則返回0
{
node *p=head;
while(p!=NULL&&p->data!=x)
p=p->next;
if(p->data==x)
return 1;
else
return 0;
}
void list::Insert (int x,int i)//將x插入到第i個結點（不含頭結點）的之後；
{
node *p;//p中放第i個結點
node *q;//q中放i後的結點
node *h;//h中存要插入的結點
h=new node;
h->data =x;
p=head;
if(p->next !=NULL) //鏈表不是只有一個結點或者空鏈表時候
{
int n=1;
while(p->next !=NULL)
{
n++;
p=p->next ;
}// 得到鏈表的結點的個數
p=head;//使p重新等於鏈首
if(i==n)//i=n時，直接加在最後面就行了
{
while(p->next !=NULL)
p=p->next;
p->next=h;
h->next =NULL;
}
else if(i<n&&i>1)//先找到第i個結點，用p存第i個結點，用q存i後的結點，用h存要插入的結點
{
for(int j=1;j<i;j++)
p=p->next;//找到第i個結點，用p存第i個結點
q=p->next;//q存i後的結點
p->next=h;
h->next=q;
}
else
cout<<"超出鏈表結點個數的范圍"<<endl;
}
else
cout<<"這個鏈表是空鏈表或者結點位置在首位"<<endl;
}
void list::Insertlist(int a,int b)//將b插入到結點為a之前
{
node *p,*q,*s;//p所指向的結點為a,s所指為要插入的數b,q所指向的是a前的結點
s=new node;
s->data=b;
p=head;
if(head==NULL)//空鏈表的時候
{
head=s;
s->next=NULL;
}
else
if(p->data==a)//a在鏈首時候
{
s->next=p;
head=s;
}
else
{
while(p->data!=a&&p->next!=NULL)//使p指向結點a,q指向a之前的結點
{
q=p;
p=p->next;
}
if(p->data==a)//若有結點a時候
{
q->next=s;
s->next=p;
}
else//沒有a的時候
{
p->next=s;
s->next=NULL;
}
}
}
int list::Delete(int x)//刪除鏈表中值為x的結點，成功返回1，否則返回0；
{
node *p,*q;
p=head;
if(p==NULL)
return 0;
if(p->data==x)
{
head=p->next;
delete p;
return 1;
}
else
{
while(p->data!=x&&p->next!=NULL)
{ q=p;
p=p->next;
}
if(p->data==x)
{
q->next =p->next;
delete p;
return 1;
}
else
return 0;
}
}
int list::Remove(int i)
{
node *p,*q;
p=head;
if(p!=NULL)
{ int n=1;
while(p->next !=NULL)
{
n++;
p=p->next ;
}//得到鏈表結點的個數
p=head;
if(i==n)//i結點在結尾的時候
{
while(p->next!=NULL)
{
q=p;
p=p->next;
}
q->next=NULL;
delete p;
return 1;
}
else if(i<n&&i>1)//i結點在中間的時候
{
for(int j=1;j<i;j++)
{
q=p;//q中放i前的結點
p=p->next ;//p中放第i個結點
}
q->next=p->next;
delete p;
return 1;
}
else if(i==1)//i結點在首位的時候
{
q=p->next;
head=q;
delete p;
return 1;
}
else
return 0;
}
else
return 0;
}
void main()
{
list A;
int data[10]={1,2,3,4,5,6,7,8,9,10};
A.Insertlist(0,data[0]);
for(int i=1;i<10;i++)
A.Insertlist(0,data[i]);
A.Display();
menu:cout<<"1.遍歷鏈表"<<'\t'<<"2.查找鏈表"<<'\t'<<"3.插入鏈表"<<endl;
cout<<"4.刪除鏈表"<<'\t'<<"5.鏈表長度"<<'\t'<<"6.置空鏈表"<<endl;
int m;
do
{
cout<<"請輸入你想要進行的操作（選擇對應操作前面的序號）："<<endl;
cin>>m;
}while(m<1||m>6);//當輸入的序號不在包括中，讓他重新輸入
switch(m)
{
case 1:
{
A.Display ();
goto menu;
};break;
case 2:
{
cout<<"請輸入你想要找到的結點："<<endl;
int c;
cin>>c;//輸入你想要找到的結點
if(A.Find (c)==1)
{
cout<<"可以找到"<<c<<endl;
A.Display ();//重新顯示出鏈表A
}
else
{
cout<<"鏈表中不存在"<<c<<endl;
A.Display ();//重新顯示出鏈表A
}
goto menu;
};break;
case 3:
{
cout<<"請選擇你要插入的方式(選擇前面的序號進行選擇）"<<endl;
cout<<"1.將特定的結點加入到特定的結點前"<<'\t'<<"2.將特定的結點加到特定的位置後"<<endl;
int b1;
do
{
cout<<"請輸入你想要插入的方式（選擇前面的序號進行選擇）："<<endl;
cin>>b1;
}while(b1<1||b1>2);//當輸入的序號不在包括中，讓他重新輸入
if(b1==1)
{
cout<<"請輸入你想要插入的數和想要插入的結點（為此結點之前插入）："<<endl;
int a1,a2;
cin>>a1>>a2;
A.Insertlist (a1,a2);//將a1插入到結點為a2結點之前
cout<<"此時鏈表為："<<endl;
A.Display ();//重新顯示出鏈表A
}
else
{
cout<<"請輸入你想要插入的數和想要插入的位置（為此結點之後插入）："<<endl;
int a1,a2;
cin>>a1>>a2;
A.Insert (a1,a2);//將a1插入到結點位置為a2的結點之後
cout<<"此時鏈表為："<<endl;
A.Display ();//重新顯示出鏈表A
}
goto menu;
};break;
case 4:
{
cout<<"請選擇你要刪除的方式(選擇前面的序號進行選擇）"<<endl;
cout<<"1.刪除特定的結點"<<'\t'<<"2.刪除特定位置的結點"<<endl;
int b1;
do
{
cout<<"請輸入你想要插入的方式（選擇前面的序號進行選擇）："<<endl;
cin>>b1;
}while(b1<1||b1>2);//當輸入的序號不在包括中，讓他重新輸入
if(b1==1)
{
cout<<"請輸入你想要刪除的結點："<<endl;
int a;
cin>>a;//輸入你想要刪除的結點
if(A.Delete (a)==1)
{
cout<<"成功刪除"<<a<<endl;
cout<<"刪除後的鏈表為："<<endl;
A.Display ();
}
else
{
cout<<"此鏈表為："<<endl;
A.Display ();//重新顯示出鏈表A
cout<<"鏈表中不存在"<<a<<endl;
}
}
else
{
cout<<"請輸入你想要刪除的結點位置："<<endl;
int b;
cin>>b;//輸入你想要刪除的結點的位置
if(A.Remove(b)==1)
{
cout<<"成功刪除第"<<b<<"個結點"<<endl;
cout<<"刪除後的鏈表為："<<endl;
A.Display ();//重新顯示出鏈表A
}
else
{
cout<<"當前鏈表的結點個數為："<<A.Length ()<<endl;
cout<<"您輸入的結點位置越界"<<endl;
}
}
goto menu;
};break;
case 5:
{
cout<<"這個鏈表的結點數為:"<<A.Length ()<<endl;
goto menu;
};break;
case 6:
{
A.MakeEmpty ();
cout<<"這個鏈表已經被置空"<<endl;
goto menu;
};break;
}
}
評論(3)|1
sunnyfulin |六級採納率46%
擅長：C/C++JAVA相關Windows數據結構及演算法網路其它產品
按默認排序|按時間排序
其他1條回答
2012-04-23 17:41121446881|六級
我寫了一個C語言的，只給你兩個結構體和一個初始化函數：
#include "stdio.h"
#include "malloc.h"
struct adjacentnext//鄰接表項結構體
{
int element;
int quanvalue;
struct adjacentnext *next;
};
struct adjacenthead//鄰接表頭結構體
{
char flag;
int curvalue;
int element;
struct adjacenthead *previous;
struct adjacentnext *son;
};
//初始化圖，用鄰接表實現
struct adjacenthead *mapinitialnize(int mapsize)
{
struct adjacenthead *ahlists=NULL;
struct adjacentnext *newnode=NULL;
int i;
int x,y,z;
ahlists=malloc(sizeof(struct adjacenthead)*mapsize);
if(ahlists==NULL)
return NULL;
for(i=0;i<mapsize;i++)
{
ahlists[i].curvalue=0;
ahlists[i].flag=0;
ahlists[i].previous=NULL;
ahlists[i].son=NULL;
ahlists[i].element=i+1;
}
scanf("%d%d%d",&x,&y,&z);//輸入源結點，目的結點，以及源結點到目的結點的路權值
while(x!=0&&y!=0)//x,y至少有一個零就結束
{
newnode=malloc(sizeof(struct adjacentnext));
newnode->element=y;
newnode->quanvalue=z;
newnode->next=ahlists[x-1].son;
ahlists[x-1].son=newnode;
scanf("%d%d%d",&x,&y,&z);
}
return ahlists;//返回鄰接表頭
}
⑥ 求！！！設有向圖的存儲結構為鄰接表,試定義鄰接表的結構,並編寫演算法計算給定有向圖中指定頂點的出度。
有個模板，可以參考一下嘛
http://wenku..com/view/2ed5c337ccbff121dd368383?fr=prin
⑦ 有向圖的鄰接矩陣存儲
有向圖的鄰接矩陣，用類似於二維鏈表做過，下面是c++的代碼：
//頂點結構
structVexNode
{
chardata;
ArcNode*firstarc;
};
//弧結構
structArcNode
{//鄰接頂點的下標
intadjvex;
ArcNode*nextarc;
};
classAdjList
{
private:
VexNodedata[100];
intvn,an;//頂點數弧數
public:
//構造函數以及其他的一些函數
AdjList();
virtual~AdjList();
};
⑧ 已知帶權有向圖如圖所示,畫出該圖的鄰接矩陣存儲結構.
∞ 2 ∞ 6 ∞ 9 ∞ ∞
∞ ∞ 30 1 ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ 5
∞ ∞ ∞ ∞ 2 ∞ ∞ ∞
∞ ∞ 8 ∞ ∞ ∞ 7 ∞
∞ ∞ ∞ ∞ 3 ∞ 24 ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ 21
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞