『壹』 OD矩陣和鄰接矩陣是一回事么
這是圖論的知識，OD矩陣是圖頂點的出度的矩陣 圖的鄰接矩陣如下介紹 1．圖的鄰接矩陣表示法 在圖的鄰接矩陣表示法中： ① 用鄰接矩陣表示頂點間的相鄰關系 ② 用一個順序表來存儲頂點信息 2．圖的鄰接矩陣(Adacency Matrix) 設G=(V，E)是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質的n階方陣： 【例】下圖中無向圖G 5 和有向圖G 6 的鄰接矩陣分別為A l 和A 2 。 從圖的鄰接矩陣表示法中可以得到如下結論： （1）對於n個頂點的無向圖，有A（i，i）=0，1≤i≤n。 （2）無向圖的鄰接矩陣是對稱的，即A（i，j）=A（j，i），1≤i≤n，1≤j≤n。 （3）有向圖的鄰接矩陣不一定對稱的。因此用鄰接矩陣來表示一個具有n個頂點的有向圖時需要n 2 個單位來存儲鄰接矩陣；對有n個頂點的無向圖則需存入上（下）三角形，故只需n（n+1）/2個單位。 （4）無向圖的鄰接矩陣的第i行（或第i列）非零元素的個數正好是第i個頂點的度TD（v i ）。 （5）有向圖的鄰接矩陣的第i行（或第i列）非零元素的個數正好是第i個頂點的出度OD（v i ）[或入度ID（v i ）]。 3．網（帶權值的圖）的鄰接矩陣 若G是網路，則鄰接矩陣可定義為： 其中： w ij 表示邊上的權值； ∞表示一個計算機允許的、大於所有邊上權值的數。 【例】下面(a)是一個帶權圖，（b）是對應的鄰接矩陣的存儲結構 （a）帶權圖 （b）鄰接矩陣 4．鄰接矩陣的圖類 const int MaxVertices=10; const int MaxWeight=32767; class AdjMWGraph { private: int Vertices[10]; //頂點信息的數組 int Edge[MaxVertices][MaxVertices]; //邊的權值信息的矩陣 int numE; //當前的邊數 int numV; //當前的頂點數 public: ………; //公有函數 private: ………; //私有函數 } 注意： ① 在簡單應用中，可直接用二維數組作為圖的鄰接矩陣（頂點表及頂點數等均可省略）。 ② 當鄰接矩陣中的元素僅表示相應的邊是否存在時，EdgeTyPe可定義為值為0和1的枚舉類型。 ③ 無向圖的鄰接矩陣是對稱矩陣，對規模特大的鄰接矩陣可壓縮存儲。 ④ 鄰接矩陣表示法的空間復雜度S(n)=0(n 2 )。
『貳』 設計一個採用鄰接矩陣存儲結構的圖類MGraph及深度優先遍歷非遞歸演算法。
你是要整個代碼還是要關鍵程序段？
我這邊的程序介面你也許不能用。
請詳細說明。
『叄』 c/c++圖的鄰接矩陣存儲結構
關於圖的深度優先遍歷代碼如下：
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TURE 1
#define OK 1
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20 //最大頂點個數
typedef struct ArcCell{
int adj; //頂點關系類型。用1或0表示相鄰與否
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //二維數組
typedef struct {
char vexs[MAX_VERTEX_NUM]; //頂點向量
AdjMatrix arcs; //鄰接矩陣
int vexnum,arcnum; //頂點數和弧數
}MGraph;
int LocateVex(MGraph G,char u)
{ //若圖G中存在頂點u，則返回該頂點在圖中的位置；否則返回-1
int i;
for(i=0;i<G.vexnum;i++)
if(G.vexs[i]==u)
return i;
else return -1;
}
int CreateDG(MGraph G){ //構造有向圖G
int i,j,k;
char va,vb;
printf("請輸入有向圖G的頂點數 弧數：");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("請輸入%d個頂點的值(<5個字元)：\n",G.vexnum);
for(i=0;i<G.vexnum;i++) scanf("%s",&G.vexs[i]); //構造頂點向量
for(i=0;i<G.vexnum;i++) //初始化鄰接矩陣
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j].adj=0;
}
printf("請輸入%d條弧的弧尾 弧頭：\n",G.arcnum);
for(k=0;k<G.arcnum;++k)
{
scanf("%s%s%*c",&va,&vb);
i=LocateVex(G,va);
j=LocateVex(G,vb);
G.arcs[i][j].adj=1;
}
return OK;
}
int FirstAdjVex(MGraph G,char v)
{ //返回v的第一個鄰接頂點的序號。若頂點在G中沒有鄰接頂點，則返回-1
int i,k;
k=LocateVex(G,v); //k為頂點v在圖G中的序號
for(i=0;i<G.vexnum;i++)
if(G.arcs[k][i].adj!=0)
return i;
else return -1;
return OK;
}
int NextAdjVex(MGraph G,char v,char w)
{ //返回v的相對於（w）的下一個鄰接頂點的序號，若w是v的最後一個鄰接頂點，則返回-1
int i,k1,k2;
k1=LocateVex(G,v); //k1為頂點v在圖G中的序號
k2=LocateVex(G,w); //k2為頂點w在圖G中的序號
for(i=k2+1;i<G.vexnum;i++)
if(G.arcs[k1][i].adj!=0)
return i;
else return -1;
return OK;
}
int visited[MAX_VERTEX_NUM];
int DFS(MGraph G,int v)
{ //從第v個頂點出發遞歸的深度優先遍歷圖G
int w;
visited[v]=TURE; //設置訪問標志為TURE
printf("%s",G.vexs[v]);
for(w=FirstAdjVex(G,G.vexs[v]);w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))
if(!visited[w])
DFS(G,w); //對尚未訪問的序號為w的鄰接頂點遞歸的調用DFS
return OK;
}
int DFSTraverse(MGraph G)
{ //從第一個頂點起，深度優先遍歷圖G
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; //訪問標志數組初始化
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); //對尚未訪問的頂點v調用DFS
printf("\n");
return OK;
}
int main()
{
MGraph G;
CreateDG(G);
DFSTraverse(G);
system("pause");
return OK;
}
廣度可以自己參照改寫。。
『肆』 鄰接矩陣vex是什麼意思
typedef char VertexType[MAX_NAME];
。。。。。
2. typedef struct
3. {
4. VertexType vexs[MAX_VERTEX_NUM]; // 頂點向量
5. AdjMatrix arcs; // 鄰接矩陣
6. int vexnum,arcnum; // 圖的當前頂點數和弧數
7. GraphKind kind; // 圖的種類標志
8. } MGraph;
。。。。。。
9.
10. VertexType *GetVex(MGraph G,int v)
11. {
12. // 初始條件: 圖G存在，v是G中某個頂點的序號。操作結果: 返回v的值
13. if(v>=G.vexnum||v<0)
14. exit(ERROR);
15. return G.vexs[v];
16. }
17. int main()
18. {
19. .
20. printf("%s ",*GetVex(G,v));
21. ..
22. }
編譯執行時，提示「15行：warning: function returns address of local variable」，執行時到這個函數就卡住了，問一下怎麼修改？
『伍』 在線急求熟悉圖的兩種常用的存儲結構，鄰接矩陣和鄰接表。
#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define maxvernum 100
typedef struct node
{
int adjvex;
struct node *next;
}nodetype;
typedef struct frontnode
{
int data;
struct node *next;
}frontnodetype;
frontnodetype adjlist[maxvernum];
/*********************************************/
void main()
{
void bfs(frontnodetype g[],int v,int c[]);
void travelgraph(frontnodetype g[],int n);
frontnodetype adjlist[6];
int i,j,m;
for(i=1;i<=5;i++)
{
adjlist[i].data=i;
adjlist[i].next=NULL;
}
for(j=1;j<=5;j++)
{
printf("進入第%d次循環\n",j);
printf("開始輸入前請輸入一個不為0的m值以便輸入\n");
scanf("%d",&m);
while(m!=0)
{
int x;
printf("請輸入結點序號（x=0表示後面沒有結點）：\n");
if(x!=0)
{
scanf("%d",&x);
nodetype *p;
p=(nodetype *)malloc(sizeof(nodetype));
p->adjvex=x;p->next=NULL;
p->next=adjlist[j].next;
adjlist[j].next=p;
}
else break;
printf("是否停止？（m為0時停止輸入，m為1時繼續輸入。）\n");
scanf("%d",&m);
}
}
printf("廣度優先搜索序列為：\n");
travelgraph(adjlist,5);
}
/************************************************/
void bfs(frontnodetype g[],int v,int c[])
{
int q[6],r=0,f=0;
nodetype *p;
c[v]=1;
printf("%d\n",v);
q[0]=v;
whille(f<=r)
{
v=q[f++];
p=g[v].next;
while(p!=NNLL)
{
v=p->adjvex;
if(c[v]==0)
{
c[v]=1;
printf("%d\n",v);
}
p=p->next;
}
}
}
/************************************************/
void travelgraph(frontnodetype g[],int n)
{
int v;
int c[6];
for(v=1;v<=n;v++)
c[v]=0;
for(v=1;v<=n;v++)
if(c[v]==0)
dfs(g,v,c);
}
『陸』 圖的鄰接矩陣和鄰接表的存儲結構各有什麼特點
圖的鄰接表數據類型描述如下：
const int N=maxn； // maxn表示圖中最大頂點數
const int E=maxe ； // maxe圖中最大邊數
struct Edge{
int u,v; //邊所鄰接的兩個頂點
int w; //邊的權值
int next; //邊指針，指向下一條邊的內存池地址
}edge[E]; // 靜態內存池，用於分配邊
int head[N]; // 表頭
int num; // 內存池的指針
『柒』 圖的存儲結構——所存儲的信息有哪些
一、鄰接矩陣存儲方法
鄰接矩陣是表示頂點之間相鄰關系的矩陣。
設G=(V，E)是具有n（n＞0）個頂點的圖，頂點的順序依次為0～n-1，則G的鄰接矩陣A是n階方陣，其定義如下：
（1）如果G是無向圖，則：
A[i][j]=1：若(i,j)∈E(G) 0:其他
（2）如果G是有向圖，則：
A[i][j]=1：若<i,j>∈E(G) 0:其他
（3）如果G是帶權無向圖，則：
A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他
（4）如果G是帶權有向圖，則：
A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j∞：其他
注意：帶權圖和不帶權圖表示的元素類型不同。
帶權圖（不論有向還是無向圖）A[i][j]用double表示，不帶權圖（不論有向還是無向圖）A[i][j]用int表示。
用一維數組G[ ]存儲有4個頂點的無向圖如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
則頂點2和頂點0之間是有邊的。
如：
鄰接矩陣的特點如下：
（1）圖的鄰接矩陣表示是唯一的。
（2）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，按照壓縮存儲的思想，在具體存放鄰接矩陣時只需存放上（或下）三角形陣的元素即可。
（3）不帶權的有向圖的鄰接矩陣一般來說是一個稀疏矩陣。因此，當圖的頂點較多時，可以採用三元組表的方法存儲鄰接矩陣。
（4）對於無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的度。
（5）對於有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的出度（或入度）。
（6）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連。但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。
鄰接矩陣的數據類型定義如下：
#define MAXV <最大頂點個數>
typedef struct
{ int no; //頂點編號
InfoType info; //頂點其他信息
} VertexType; //頂點類型
typedef struct //圖的定義
{ int edges[MAXV][MAXV]; //鄰接矩陣
int n，e; //頂點數，弧數
VertexType vexs[MAXV]; //存放頂點信息
} MGraph; //圖的鄰接矩陣表示類型
二、 鄰接表存儲方法
圖的鄰接表存儲方法是一種順序分配與鏈式分配相結合的存儲方法。
在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的節點表示依附於頂點i的邊（對有向圖是以頂點i為尾的邊）。每個單鏈表上附設一個表頭節點。
其中，表節點由三個域組成，adjvex指示與頂點i鄰接的點在圖中的位置，nextarc指示下一條邊或弧的節點，info存儲與邊或弧相關的信息，如權值等。
表頭節點由兩個域組成，data存儲頂點i的名稱或其他信息，firstarc指向鏈表中第一個節點。
typedef struct ANode
{ int adjvex; //該邊的終點編號
struct ANode *nextarc; //指向下一條邊的指針
InfoType info; //該邊的相關信息
} ArcNode; //邊表節點類型
typedef struct Vnode
{ Vertex data; //頂點信息
ArcNode *firstarc; //指向第一條邊
} VNode; //鄰接表頭節點類型
typedef VNode AdjList[MAXV]; //AdjList是鄰接表類型
typedef struct
{ AdjList adjlist; //鄰接表
int n,e; //圖中頂點數n和邊數e
} ALGraph; //完整的圖鄰接表類型
鄰接表的特點如下：
（1）鄰接表表示不唯一。這是因為在每個頂點對應的單鏈表中，各邊節點的鏈接次序可以是任意的，取決於建立鄰接表的演算法以及邊的輸入次序。
（2）對於有n個頂點和e條邊的無向圖，其鄰接表有n個頂點節點和2e個邊節點。顯然，在總的邊數小於n(n-1)/2的情況下，鄰接表比鄰接矩陣要節省空間。
（3）對於無向圖，鄰接表的頂點i對應的第i個鏈表的邊節點數目正好是頂點i的度。
（4）對於有向圖，鄰接表的頂點i對應的第i個鏈表的邊節點數目僅僅是頂點i的出度。其入度為鄰接表中所有adjvex域值為i的邊節點數目。
例， 給定一個具有n個節點的無向圖的鄰接矩陣和鄰接表。
（1）設計一個將鄰接矩陣轉換為鄰接表的演算法；
（2）設計一個將鄰接表轉換為鄰接矩陣的演算法；
（3）分析上述兩個演算法的時間復雜度。
解：
（1）在鄰接矩陣上查找值不為0的元素，找到這樣的元素後創建一個表節點並在鄰接表對應的單鏈表中採用前插法插入該節點。
void MatToList(MGraph g，ALGraph *&G)
//將鄰接矩陣g轉換成鄰接表G
{ int i，j，n=g.n; ArcNode *p; //n為頂點數
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<n;i++) //給所有頭節點的指針域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++) //檢查鄰接矩陣中每個元素
for (j=n-1;j>=0;j--)
if (g.edges[i][j]!=0)
{ p=(ArcNode *)malloc(sizeof(ArcNode));
//創建節點*p
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;
//將*p鏈到鏈表頭
G->adjlist[i].firstarc=p;
}
G->n=n;G->e=g.e;
}
（2）在鄰接表上查找相鄰節點，找到後修改相應鄰接矩陣元素的值。
void ListToMat(ALGraph *G，MGraph &g)
{ int i，j，n=G->n;ArcNode *p;
for (i=0;i<n;i++)
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ g.edges[i][p->adjvex]=1;
p=p->nextarc;
}
}
g.n=n;g.e=G->e;
}
（3）演算法1的時間復雜度均為O(n2)。演算法2的時間復雜度為O(n+e)，其中e為圖的邊數。
『捌』 有向圖的鄰接矩陣存儲
有向圖的鄰接矩陣，用類似於二維鏈表做過，下面是c++的代碼：
//頂點結構
structVexNode
{
chardata;
ArcNode*firstarc;
};
//弧結構
structArcNode
{//鄰接頂點的下標
intadjvex;
ArcNode*nextarc;
};
classAdjList
{
private:
VexNodedata[100];
intvn,an;//頂點數弧數
public:
//構造函數以及其他的一些函數
AdjList();
virtual~AdjList();
};
『玖』 試以鄰接矩陣為存儲結構，寫出連通圖的深度優先搜索演算法。
/* MGraph.cc: 圖的鄰接矩陣存儲表示和實現 */
/* 包含圖類型Graph定義；創建圖；深度優先遍歷；廣度優先遍歷 */
/* 用到引用型參數，在TC下無法通過編譯，VC等C++編譯器可通過 */
#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX
#define VType char //頂點值類型
#define EType int //邊權值類型
#define MAXVNUM 50 //最大頂點個數
#define DIGRAPH 0 //有向圖(網)
#define UNDIGRAPH 1 //無向圖(網)
#define INVALID INT_MAX //無效權值(最大整數表示無窮大)
#define EMPTY -1 //"空"頂點序號
//定義鄰接矩陣表示的圖類型Graph:
typedef struct
{
VType v[MAXVNUM]; //頂點序列(頂點編號從0開始)
EType w[MAXVNUM][MAXVNUM]; //鄰接矩陣
int vn, en; //頂點數,邊數
int kind; //圖的種類：=DIGRAPH表示有向圖(網)，=UNDIGRAPH表示無向圖(網)
}Graph;
int visited[MAXVNUM]; //訪問標志數組(=1已訪問，=0未訪問)。遍歷時用到的全局量。
/* 創建圖G
參數Vex是存放頂點序列的數組
參數VVW是整數數組，以{Vi,Vj,Wij,...,-1}的形式依次存放各邊的起止點序號(Vi,Vj)和權(Wij)，-1是數據結束標志
參數kind=DIGRAPH表示有向圖(網)，=UNDIGRAPH表示無向圖(網)
*/
void CreateGraph(Graph &G, VType *Vex, int VVW[], int kind)
{
int i, j, p, n, w;
n = strlen(Vex);
G.vn = n; //頂點數
G.kind = kind; //圖的種類
//置頂點序列:
for (i = 0; i < n; i++)
G.v[i] = Vex[i];
//初始化鄰接矩陣:
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
G.w[i][j] = INVALID;
//構造鄰接矩陣:
p = 0; //VVW數組元素「指針」
n = 0; //邊計數器
while (VVW[p] != -1)
{//只要p未到結束位置便繼續:
i = VVW[p]; //邊的起點序號
j = VVW[p + 1]; //邊的終點序號
w = VVW[p + 2]; //邊的權
G.w[i][j] = w; //置鄰接矩陣的(i,j)位置元素
if (G.kind == UNDIGRAPH) //若是無向圖(網),
G.w[j][i] = G.w[i][j]; //則置(i,j)的對稱位置(j,i)
n++; //邊計數器加1
p += 3; //p指向下一組(Vi,Vj,Wij)
}//end while
G.en = n; //邊數
}//CreateGraph
/* 返回G中頂點i的一個未曾訪問過的鄰接點(序號) */
int NextAdjVex(Graph &G, int i)
{
int j, a;
a = EMPTY; //鄰接點序號初始為"空"
//在鄰接矩陣的第v行找有效元素：
for (j = 0; j < G.vn; j++)
{
if (G.w[i][j] == INVALID) //若當前元素是無效元素,
continue; //則繼續找。
if (!visited[j])
{//若當前有效元素未曾訪問過,則作為鄰接點a:
a = j;
break;
}//end if
}//end for
return a;
}//NextAdjVex
/* 訪問頂點i */
void visit(Graph &G, int i)
{
printf("%c", G.v[i]);
}//visit
/* 從第i個頂點出發深度優先遍歷連通圖G */
/* 調用DFS前可能需初始化數組visited[] */
void DFS(Graph &G, int i)
{int a;
visit(G, i); //訪問i頂點
visited[i] = 1; //標注i頂點已訪問
a = NextAdjVex(G, i); //找出一個i的鄰接點a
while (a != EMPTY)
{//只要a存在便繼續:
if (visited[a] == 0) //若a未曾訪問,
DFS(G, a); //則從a出發繼續進行深度優先遍歷。
a = NextAdjVex(G, i); //找出i的下一個鄰接點a
}//end while
}//DFS
/* 從第i個頂點出發深度優先遍歷圖G */
void DFSTrav(Graph &G, int i)
{int k;
//初始化各頂點的訪問標志為0(未曾訪問):
for (k = 0; k < G.vn; k++)
visited[k] = 0;
DFS(G, i); //從i出發遍歷
//若G非連通圖，執行一次DFS無法遍歷所有頂點，還需用如下for對尚未訪問的頂點DFS。
//若G是連通圖，執行一次DFS就已遍歷所有頂點，此時如下for什麼也不做，因所有visited=1。
for (k = 0; k < G.vn; k++)
if (!visited[k]) DFS(G, k); //對尚未訪問的頂點DFS
}//DFSTrav
//顯示圖的鄰接矩陣
void ShowM(Graph &G)
{
int row, col, n;
n = G.vn; //頂點數
//以表格形式輸出數組：
//輸出表頭：
printf(" ");
for(col = 0; col < n; col++)
printf("%3d",col);
printf("\n");
printf("---+");
for(col = 0; col < n; col++)
printf("---");
printf("\n");
//輸出表體(矩陣元素)：
for(row = 0; row < n; row++)
{
printf("%3d|", row);
for(col = 0; col < n; col++)
{
if (G.w[row][col] == INVALID)
printf("%3c", '*');
else
printf("%3d", G.w[row][col]);
}//end for col
printf("\n");
}//end for row
printf("\n");
}//ShowM