『壹』 一個包含N個頂點、E條邊的簡單有向圖採用鄰接矩陣存儲結構
全國2001年10月數據結構試題及答案 12．假設一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關的所有弧的時間復雜度是( ) A．O(n)
『貳』 有關有向圖用鄰接矩陣存儲的時間復雜度
刪除結點O(n)
刪除頂點相鄰接所有有向邊的是O(n)
判斷為O(1)
出度O(n)
『叄』 圖的存儲結構可以採用鄰接矩陣和鄰接表，對於個有n 個頂點，e條邊的有向圖， (1)計算存儲結構分別
鄰接表所需的存儲空間為e（邊數），但不適合查詢兩點間是否存在路徑
鄰接矩陣所需的存儲空間為你n^2，適合查詢兩點間是否存在路徑
對於第二問，鄰接表所需的存儲空間為9900，鄰接矩陣所需的存儲空間為你n^2=10000，差不多，所以選性能更優的鄰接矩陣
實際上像（2）這種稠密圖（其實是個滿圖）一般適合鄰接矩陣
『肆』 要求採用鄰接矩陣作為無向圖的存儲結構，鄰接表作為有向圖的存儲結構，完成無向圖和有向圖的建立，並對建
#include"utility.h"
#include"adj_matrix_undir_graph.h"
#include"adj_list_dir_graph.h"
#include"dfs.h"
#include"bfs.h"
int main(void)
{
int n,j=0,i=0;
int m,e,b=0;
char vexs[20],c;
char nums[20];
cout<<"輸入無向圖的頂點個數n:"<<endl;
cin>>n;
cout<<"輸入頂點元素："<<endl;
for(i=0;i<n;i++)
{
cout<<"請輸入第"<<j<<"個結點"<<endl;
cin>>vexs[i];
j++;
}
cout<<"輸出無向圖的鄰接矩陣："<<endl;
AdjMatrixUndirGraph<char> aundir(vexs,n);
for(i=0;i<n;i++)
{
for(int v=1;v<n;v++)
{
cout<<"輸入Y/N，是否插入邊:";
cin>>c;
if(c == 'Y' )
aundir.InsertEdge(i,v);
}
}
Display(aundir);
cout<<"請輸入有向圖的頂點個數m：";
cin>>m;
for(int a=0;a<m;a++)
{
cout<<"輸入第"<<b<<"個頂點數據";
cin>>nums[a];
b++;
}
AdjListDirGraph<char> dir(nums,m);
for(int k=0;k<m;k++)
{
for(e=0;e<m;e++)
{
cout<<"是否插入邊V"<<k<<",V"<<e<<":";
cin>>c;
if(c == 'Y' )
dir.InsertEdge(k,e);
}
}
Display(dir);
cout<<"無向圖的深度遍歷：";
DFSTraverse<char>(aundir,Write<char>);
cout<<endl;
cout<<"無向圖的廣度遍歷：";
BFSTraverse<char>(aundir,Write<char>);
cout<<endl;
cout<<"有向圖的深度遍歷：";
DFSTraverse<char>(dir,Write<char>);
cout<<endl;
cout<<"有向圖的廣度遍歷：";
BFSTraverse<char>(dir,Write<char>);
『伍』 （1） 圖的建立，要求採用鄰接矩陣作為存儲結構。 （2） 輸出結點的度（或出度和入度），並求得圖的邊數。
就指針變數和一般變數本身而言，沒有區別。
但給指針變數申請分配內存時，申請到的內存是從內存堆空間申請的。而指針變數和一般變數則在在內存棧空間，由系統自動分配的。
『陸』 有向圖的鄰接矩陣存儲
有向圖的鄰接矩陣，用類似於二維鏈表做過，下面是c++的代碼：
//頂點結構
structVexNode
{
chardata;
ArcNode*firstarc;
};
//弧結構
structArcNode
{//鄰接頂點的下標
intadjvex;
ArcNode*nextarc;
};
classAdjList
{
private:
VexNodedata[100];
intvn,an;//頂點數弧數
public:
//構造函數以及其他的一些函數
AdjList();
virtual~AdjList();
};
『柒』 採用鄰接矩陣存儲結構對有向圖進行拓撲排序的演算法
lint topsort( ALGraph *G) /*拓撲排序*/
{ int i,j,k,top =-1;
EdgeNode *ptr;
for(i=0;i<G->n;i++) /*入度為0入棧*/
{ if(G->adjlist[i].indegree==0)
{ G->adjlist[i].indegree=top;
top=i; }
}
{if(top==-1) return -1; /*網中有迴路*/
j=top;
for(i=0;i<G->n;i++)
{ if(top==-1) return -1;/*AOV網中有迴路*/
j=top;
top=G->adjlist[top].indegree; /*從棧中退出一個入度為0的頂點並輸出*/
printf("->%s",G->adjlist[j].vertex);
ptr=G->adjlist[j].firstedge;
{ k=ptr->adjvex;
G->adjlist[k].indegree--; /*修改其他頂點的入度*/
if(G->adjlist[k].indegree==0) /*為0入棧*/
while(ptr!=NULL)
{
G->adjlist[k].indegree=top;
top=k;
}
ptr=ptr->next;
}
}
}
『捌』 設計一個採用鄰接矩陣存儲結構的圖類MGraph及深度優先遍歷非遞歸演算法。
你是要整個代碼還是要關鍵程序段？
我這邊的程序介面你也許不能用。
請詳細說明。
『玖』 若具有n個頂點的無向圖採用鄰接矩陣存儲方法，該鄰接矩陣一定為一個什麼矩陣
原則上的確是n的平方，不過由於無向圖的鄰接矩陣是一個對稱矩陣，只需要存儲下三角或者上三角的元素，個數就是從1加到n，就是n（n+1）/ 2，這是壓縮存儲，是用一維數組存放，一般好像不叫矩陣。
其實更精確地說，上面的數字個數是普通對稱矩陣的，這個鄰接矩陣的對角線一定為0，所以，只需要存儲1加到n-1，也就是n(n-1)/2就可以了。
用一個一維數組存放圖中所有頂點數據；用一個二維數組存放頂點間關系（邊或弧）的數據，這個二維數組稱為鄰接矩陣。鄰接矩陣又分為有向圖鄰接矩陣和無向圖鄰接矩陣。
(9)假設圖採用鄰接矩陣存儲擴展閱讀：
對無向圖而言，鄰接矩陣一定是對稱的，而且主對角線一定為零（在此僅討論無向簡單圖），副對角線不一定為0，有向圖則不一定如此。
在無向圖中，任一頂點i的度為第i列（或第i行）所有非零元素的個數，在有向圖中頂點i的出度為第i行所有非零元素的個數，而入度為第i列所有非零元素的個數。
用鄰接矩陣法表示圖共需要n^2個空間，由於無向圖的鄰接矩陣一定具有對稱關系，所以扣除對角線為零外，僅需要存儲上三角形或下三角形的數據即可，因此僅需要n（n-1）/2個空間。
『拾』 用鄰接矩陣儲存圖，所佔用的儲存空間大小隻與圖中頂點個數
圖的鄰接矩陣存儲所佔用空間大小隻與頂點個數有關，更准確地說，設頂點n個，則與n^2成正比（n的平方）