圖的幾種存儲結構：
1、鄰接矩陣
2、鄰接表
3、鏈式前向星
4、C++中vector的鄰接表實(shí)現（補充）
鄰接矩陣的好處：
（1）直觀(guān)、簡(jiǎn)單、好理解
（2）方便檢查任意一對定點(diǎn)間是否存在邊
（3）方便找任一頂點(diǎn)的所有“鄰接點(diǎn)”（有邊直接相連的頂點(diǎn)）
（4）方便計算任一頂點(diǎn)的度
對于無(wú)向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個(gè)數正好是第i個(gè)頂點(diǎn)的度。
對于有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個(gè)數正好是第i個(gè)頂點(diǎn)的出度（或入度）。
鄰接矩陣的局限性：時(shí)間復雜度O(n^2），空間復雜度O(n^2)
（1）浪費空間。對于稠密圖還是很合算的。
但是對于稀疏圖（點(diǎn)很多而邊很少）有大量無(wú)效元素。
（2）浪費時(shí)間。要確定圖中有多少條邊，則必須按行、按列對每個(gè)元素進(jìn)行檢測，所花費的時(shí)間代價(jià)很大。
bb這么多，我們直接來(lái)以OJ此專(zhuān)題第一題為例
這題二維數組map不能用int，會(huì )爆內存，bool可以自己百度，簡(jiǎn)而言之就是用于邏輯判斷，只有true和false兩種情況。
bool類(lèi)型在存儲二值變量，或者說(shuō)只有真假時(shí)，更具優(yōu)勢，因為只有0和1即false和true，省空間
（int型的0和1都是4字節，bool都是1字節）
- #include<stdio.h>
- #include<string.h>
- #include<stdbool.h>
- bool map[5001][5001];
- int main()
- {
- int n,m;
- int u,v;
- int q;
- while(~scanf("%d %d",&n,&m))
- {
- memset(map,false,sizeof(map));
- while(m--)
- {
- scanf("%d %d",&u,&v);
- map[u][v]=true;
- }
- scanf("%d",&q);
- while(q--)
- {
- scanf("%d %d",&u,&v);
- if(map[u][v])
- {
- printf("Yes\n");
- }else
- {
- printf("No\n");
- }
- }
- }
- return 0;
- }
在鄰接表中，對圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的節點(diǎn)表示依附于頂點(diǎn)i的邊（對有向圖是以頂點(diǎn)i為尾的邊）。每個(gè)單鏈表上附設一個(gè)表頭節點(diǎn)。
鄰接表的特點(diǎn)如下：
（1）鄰接表表示不唯一。這是因為在每個(gè)頂點(diǎn)對應的單鏈表中，各邊節點(diǎn)的鏈接次序可以是任意的，取決于建立鄰接表的算法以及邊的輸入次序。
（2）對于有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，其鄰接表有n個(gè)頂點(diǎn)節點(diǎn)和2e個(gè)邊節點(diǎn)。顯然，在總的邊數小于n(n-1)/2的情況下，鄰接表比鄰接矩陣要節省空間。
（3）對于無(wú)向圖，鄰接表的頂點(diǎn)i對應的第i個(gè)鏈表的邊節點(diǎn)數目正好是頂點(diǎn)i的度。
（4）對于有向圖，鄰接表的頂點(diǎn)i對應的第i個(gè)鏈表的邊節點(diǎn)數目?jì)H僅是頂點(diǎn)i的出度。其入度為鄰接表中所有adjvex域值為i的邊節點(diǎn)數目。
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- struct node
- {
- int data;
- struct node *next;
- };
- int main()
- {
- int n, u, j, i, v;
- struct node *p, *a[5050];
- while(~scanf("%d", &n))
- {
- for(i = 0; i < n; i++)
- a[i] = NULL;
- for(i = 0; i < n; i++)
- {
- for(j = 0; j < n; j++)
- {
- scanf("%d", &u); //審清題意
- if(u == 1)
- {
- if(a[i] == NULL)
- {
- p = (struct node *)malloc(sizeof(struct node));
- p -> data = j;
- p -> next = NULL;
- a[i] = p;
- }
- else
- {
- p = (struct node *)malloc(sizeof(struct node));
- p -> next = a[i] -> next;
- p -> data = j;
- a[i] -> next = p;
- }
- }
- }
- }
- int q;
- scanf("%d", &q);
- while(q--)
- {
- scanf("%d%d", &u, &v);
- p = a[u];
- int flag = 0;
- while(p)
- {
- if(p -> data == v)
- {
- flag = 1;
- break;
- }
- p = p -> next;
- }
- if(flag)
- printf("Yes\n");
- else
- printf("No\n");
- }
- }
- return 0;
- }
https://blog.csdn.net/Binary_Heap/article/details/78209086
這里用兩個(gè)東西：
1 結構體數組edge存邊，edge[i]表示第i條邊,
2 head[i]存以i為起點(diǎn)的第一條邊(在edge中的下標)
- struct edge{
- int to; //這條邊的終點(diǎn)
- int w; //權值
- int next; //下一條邊的存儲下標(默認0)
- }e[500010];
若以點(diǎn)u為起點(diǎn)的邊新增了一條，在edge中的下標為cnt.
那么edge[++cnt].next=head[u];然后head[u]=cnt.
即每次新加的邊作為第一條邊，最后倒序遍歷
- void add(int u, int v, int w)
- {
- e[cnt].to = v;
- e[cnt].w = w;
- e[cnt].next = head[u];//cnt為邊的計數，從1開(kāi)始計
- head[u] = cnt++; //第一條邊為當前邊
- }
遍歷以st為起點(diǎn)的邊
for(int i=head[st]; i!=0; i=edge[i].next)i 開(kāi)始為第一條邊，每次指向下一條(以0為結束標志) （若下標從0開(kāi)始，next應初始化-1）
鏈式前向星主要是用來(lái)優(yōu)化的，可以用來(lái)優(yōu)化BFS，SPFA算法等等。在做最短路的時(shí)候一直T就是因為沒(méi)有用鏈式前向星存邊導致的超時(shí)，所以這個(gè)坑我先和你們說(shuō)下。
vector是C++STL里面的一個(gè)東西，簡(jiǎn)單的來(lái)說(shuō)就是一個(gè)可變長(cháng)的數組，你可以通過(guò)往它里面壓入數據來(lái)使它變長(cháng)，
想深入了解的可以自己百度一波，還是以這道題為例：
- #include<iostream>
- #include<cstdio>
- #include<vector>//注意這個(gè)頭文件不能丟，要么你就去用萬(wàn)能頭
- using namespace std;
- #define N 500001
- vector<int>MAP[N];//可以理解為二維的，每個(gè)MAP可以包含若干項，這些項是以當前編號點(diǎn)為起點(diǎn)
- int main()
- {
- int n,m,u,v,i;
- while(~scanf("%d %d",&n,&m))
- {
- while(m--)
- {
- scanf("%d %d",&u,&v);
- MAP[u].push_back(v);//擴充
- }
- int q;
- scanf("%d",&q);
- while(q--)
- {
- scanf("%d %d",&u,&v);
- int len=MAP[u].size();
- int flag=0;
- for(i=0;i<len;i++)
- {
- if(MAP[u][i]==v)
- {
- flag=1;
- }
- }
- if(flag)
- {
- cout<<"Yes"<<endl;
- }else
- {
- cout<<"No"<<endl;
- }
- }
- for(int i=0; i<N; i++)
- {
- MAP[i].clear();
- }
- }
- return 0;
- }
嗯，目前我用過(guò)的圖的幾種存儲方式就這樣啦，謝謝大家觀(guān)賞拙作。
聯(lián)系客服
