無向圖的存儲方法
C
10*10的矩陣存儲上三角，且對角線全為0，不用存儲對角線的值，即可得：1. 第一行存9個數，第二行存8個，......，直到最後一行存0個，進行壓縮存儲。2. 上三角存儲，即存儲的數值均是行標小於列標，(V6,V3)存儲的即為（V3,V6），它前面存入一維數組中的有9+8+2=19個（第一行9個，第二行8個，第三行從V3,V4開始存儲到V3,V6有2個），從1開始，它就放在B【20】
B. 數據結構中的圖 無向和有向，怎樣存入文件
通常圖都分為結點和弧，您存儲圖到文件可以按照這種方法來實現。
typedef struct {
int type; //標識是有向圖還是無向圖，例如0表示有向圖，非0表示無向圖
int vexnum;
char *arclist; //arclist指向一個vexnum*vexnum的矩陣，存儲節點間的弧
}CHART;
1. 寫文件時將上面的結構寫入文件，然後將vexnum*vexnum的弧矩陣寫入文件
2. 讀文件時先讀取上面的結構，然後依據vexnum先申請一個vexnum*vexnum大小的空間
賦值給arclist，然後從文件繼續讀取vexnum*vexnum大小的數據存儲到arclist指向的數
組中。
C. C語言數據結構無向圖刪除邊
//在用鄰接表方式存儲的無向圖g中，刪除邊(i,j)
void DeletEdge(AdjList g,int i,j)
{
//先刪除定點i的邊(i,j)
p=g[i].firstarc;
pre=null; //刪頂點i 的邊結點(i,j),pre是前驅指針
while (p)
if (p->adjvex==j)
{
if(pre==null) g[i].firstarc=p->next;
else pre->next=p->next;
free(p);//釋放結點空間
}
else
{
pre=p;
p=p->next;//沿鏈表繼續查找
}
//刪頂點j 的邊結點(j,i)
p=g[j].firstarc;
pre=null;
while (p)
if (p->adjvex==i)
{
if(pre==null)g[j].firstarc=p->next;
else pre->next=p->next;
free(p);//釋放結點空間
}
else
{
pre=p;
p=p->next;//沿鏈表繼續查找
}
}// DeletEdge
D. 有向圖和無向圖的有關知識
有/無 向圖如果給圖的每條邊規定一個方向，那麼得到的圖稱為有向圖，其邊也稱為有向邊。在有向圖中，與一個節點相關聯的邊有出邊和入邊之分，而與一個有向邊關聯的兩個點也有始點和終點之分。相反，邊沒有方向的圖稱為無向圖。[編輯]簡單圖一個圖如果沒有兩條邊，它們所關聯的兩個點都相同（在有向圖中，沒有兩條邊的起點終點都分別相同）；每條邊所關聯的是兩個不同的頂點則稱為簡單圖(simple graph)。簡單的有向圖和無向圖都可以使用以上的「二元組的定義」，但形如(x,x)的序對不能屬於E。而無向圖的邊集必須是對稱的，即如果 ，那麼 。[編輯]多重圖若允許兩結點間的邊數多於一條，又允許頂點通過同一條邊和自己關聯，則為多重圖的概念。它只能用「三元組的定義」。[編輯]基本術語在頂點1有一個環階（Order）：圖G中頂集V的大小稱作圖G的階。子圖（Sub-Graph）：圖G'稱作圖G的子圖如果以及 。生成子圖（Spanning Sub-Graph）：指滿足條件V(G') =V(G)的G的子圖G。度（Degree）是一個頂點的度是指與該頂點相關聯的總邊數，頂點v的度記作d(v)。度和邊有如下關系：。出度(out-degree) 和入度 (in-degree)：對有向圖而言，頂點的度還可分為出度和入度。一個頂點的出度為 do ，是指有 do 條邊以該頂點為起點，或說與該點關聯的出邊共有do條。入度的概念也類似。鄰接矩陣環(loop)：若一條邊的兩個頂點相同，則此邊稱作環。路徑（path）：從頂點 u 到頂點 v 的一條路徑是指一個序列v0,e1,v1,e2,v2,...ek,vk， ei的起點終點為vi及vi - 1； k 稱作路徑的長度； v_0=u，稱為路徑的起點； v_k=v，稱為路徑的終點。如果 u=v，稱該路徑是閉的，反之則稱為開的；如果 v_1 , ... , v_k 兩兩不等，則稱之為簡單路徑(simple path)（注意，u=v 是允許的）。行跡（trace）：如果路徑P(u,v)中邊各不相同，則該路徑稱為u到v的一條行跡。軌道（track）：即簡單路徑。閉的行跡稱作迴路（circuit），閉的軌道稱作圈（Cycle）。（現存文獻中的命名法並無統一標准。比如在另一種定義中，walk 對應上述的 path，path 對應上述的 track ， trail 對應上述的 trace。）距離（distance）： 從頂點 u 出發到頂點 v 的最短路徑若存在，則此路徑的長度稱作從 u 到 v 的距離。若從 u 到 v 根本不存在路徑，則記該距離為無窮（∞）。距離矩陣橋（bridge）：若去掉一條邊，便會使得整個圖不連通，該邊稱為橋。[編輯]圖的存儲表示數組（鄰接矩陣）存儲表示（有向或無向）鄰接表存儲表示前向星存儲表示有向圖的十字鏈表存儲表示無向圖的鄰接多重表存儲表示一個不帶權圖中若兩點不相鄰，鄰接矩陣相應位置為0，對帶權圖(網)，相應位置為∞。一個圖的鄰接矩陣表示是唯一的，但其鄰接表表示不唯一。在鄰接表中，對圖中每個頂點建立一個單鏈表（並按建立的次序編號），第i個單鏈表中的結點表示依附於頂點vi的邊（對於有向圖是以頂點vi為尾的弧）。每個結點由兩個域組成：鄰接點域(adjvex)，用以指示與vi鄰接的點在圖中的位置，鏈域(nextarc)用以指向依附於頂點vi的下一條邊所對應的結點。如果用鄰接表存放網（帶權圖）的信息，則還需要在結點中增加一個存放權值的域（info）。每個頂點的單鏈表中結點的個數即為該頂點的出度(與該頂點連接的邊的總數)。無論是存儲圖或網，都需要在每個單鏈表前設一表頭結點，這些表頭結點的第一個域data用於存放結點vi的編號i，第二個域firstarc用於指向鏈表中第一個結點。[編輯]圖的遍歷圖的遍歷方法有深度優先搜索法和廣度(寬度)優先搜索法。深度優先搜索法是樹的先根遍歷的推廣，它的基本思想是：從圖G的某個頂點v0出發，訪問v0，然後選擇一個與v0相鄰且沒被訪問過的頂點vi訪問，再從vi出發選擇一個與vi相鄰且未被訪問的頂點vj進行訪問，依次繼續。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則退回到已被訪問的頂點序列中最後一個擁有未被訪問的相鄰頂點的頂點w，從w出發按同樣的方法向前遍歷，直到圖中所有頂點都被訪問。其遞歸演算法如下：Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數void DFSTraverse (Graph G, Status(*Visit)(int v)){ VisitFunc = Visit; for(v=0; v<G.vexnum; ++v) visited[v] = FALSE; //訪問標志數組初始化 for(v=0; v<G.vexnum; ++v) if(!visited[v]) DFS(G, v); //對尚未訪問的頂點調用DFS}void DFS(Graph G, int v){ //從第v個頂點出發遞歸地深度優先遍歷圖Gvisited[v]=TRUE; VisitFunc(v); //訪問第v個頂點for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))//FirstAdjVex返回v的第一個鄰接頂點，若頂點在G中沒有鄰接頂點，則返回空(0)，//若w是v的鄰接頂點，NextAdjVex返回v的（相對於w的）下一個鄰接頂點。//若w是v的最後一個鄰接點，則返回空(0)。 if(!visited[w]) DFS(G, w); //對v的尚未訪問的鄰接頂點w調用DFS}圖的廣度優先搜索是樹的按層次遍歷的推廣，它的基本思想是：首先訪問初始點vi，並將其標記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點vi1,vi2, …, vi t，並均標記已訪問過，然後再按照vi1,vi2, …, vi t的次序，訪問每一個頂點的所有未被訪問過的鄰接點，並均標記為已訪問過，依次類推，直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。其非遞歸演算法如下：Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數void BFSTraverse (Graph G, Status(*Visit)(int v)){ VisitFunc = Visit;for(v=0; v<G.vexnum, ++v) visited[v] = FALSE; initQueue(Q); //置空輔助隊列Q for(v=0; v<G.vexnum; ++v) if(!visited[v]){ visited[v]=TRUE; VisitFunc(v); EnQueue(Q, v); //v入隊列 while(!QueueEmpty(Q)){ DeQueue(Q, u); //隊頭元素出隊並置為u for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w)) if(!Visited[w]){ //w為u的尚未訪問的鄰接頂點 Visited[w]=TRUE; VisitFunc(w); EnQueue(Q, w); } } }}
[編輯]圖的重要類型樹平面圖連通圖強連通圖有向無環圖AOV網AOE網完全圖：每一對不同頂點間都有邊相連的的圖，記作Kn。二分圖：頂集，且每一條邊都有一個頂點在X中，而另一個頂點在Y中。完全二分圖：二分圖G中若任意兩個X和Y中的頂點都有邊相連。若，則圖G記作Km,n。正則圖：如果圖中所有頂點的度皆相等，則此圖稱為正則圖歐拉圖:存在經過所有邊一次(可以多次經過點)的路徑的圖哈密頓圖:存在經過所有點一次的路徑的圖
E. 【數據結構】計算頂點數目超大（達千萬級別）的無向圖的連通分量數，如何用文本文件存儲
第一行存儲頂點個數
從第二行開始，每一行存兩個定點編號代表一條邊（例如：329 744 這就代表329號頂點到744號頂點的一條邊）
這些邊可以按照第一個頂點編號來進行排序這樣便於索引，利用二分搜索可以很快找到相應的邊
F. 無向圖的鄰接矩陣可用一維數組存儲對嗎
習慣上無向圖的鄰接矩陣一般用二維數組存儲，這樣使用方便。當然，任意二維數組都是可以用一維數組存儲的，只是用起來不方便。
G. 怎樣將一棵二叉樹的存儲結構轉化為一個無向圖的存儲結構，誰能說說編程思想啊
圖的存儲機構一般用鄰接矩陣或鄰接表,二叉樹一般是鏈表結構,就是把鏈表變成臨近矩陣了,用中序形勢對鏈表節點進行編號和訪問並做為臨近矩陣的順序,用中序訪問,對當前節點和後繼節點判斷,然後置對應的矩陣為1,(a[當前],[後繼]=1 ,a[後繼],[當前]=1 ) ,中序訪問完就可以了
H. 無向圖的鄰接表存儲方式和深度優先遍歷的方法（代碼）
type
node=record
y:longint;
flag:boolean;
next:longint;
p:-1..1;
end;
var
n,m,i,j,x,y:longint;
map:array [0..40000] of node;
a:array [0..40000] of longint;
procere dfs(i:longint);
var
j:longint;
begin
j:=a[i];
while j>-1 do begin
if map[j].flag then begin
map[j].flag:=false;
map[j xor 1].flag:=false;
if map[j].p>-1 then begin
map[j].p:=0;
writeln(i);
dfs(map[j].y);
map[j].p:=1;
end;
end;
j:=map[j].next;
end;
end;
begin
readln(n,m);
for i:=1 to n do a[i]:=-1;
for j:=1 to m do begin
readln(x,y);
map[2*j-2].y:=y;
map[2*j-2].next:=a[x];
map[2*j-2].flag:=true;
a[x]:=2*j-2;
map[2*j-1].y:=x;
map[2*j-1].next:=a[y];
map[2*j-1].flag:=true;
a[y]:=2*j-1;
end;
map[a[1]].p:=0;
dfs(1);
map[a[1]].p:=1;
end.
I. 圖的存儲結構——所存儲的信息有哪些
一、鄰接矩陣存儲方法
鄰接矩陣是表示頂點之間相鄰關系的矩陣。
設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為圖的邊數。
J. 對於有n個頂點的無向圖，怎樣存儲可以省一半空間
原則上的確是n的平方，不過由於無向圖的鄰接矩陣是一個對稱矩陣，只需要存儲下三角或者上三角的元素，個數就是從1加到n，就是n（n+1）/ 2，不過題目問錯了，這是壓縮存儲，是用一維數組存放，一般好像不叫矩陣
其實更精確地說，上面的數字個數是普通對稱矩陣的，這個鄰接矩陣的對角線一定為0，所以，只需要存儲1 加到n-1，也就是n(n-1)/2就可以了