NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » 一般 » 綜合討論區
 不用內建作連接圖的方法

作者 主題: 不用內建作連接圖的方法  (閱讀 1867 次)

lose

  • 新手
  • *
  • 文章數: 12
    • 檢視個人資料
不用內建作連接圖的方法
« 於: 十一月 29, 2009, 10:34:33 am »

在下分享一個無聊的東西  看看就好
通常在寫圖的時候
常常會卡在如何記如連接的部份     雖然說內建很好用
但是不會用內建的話  通常卻是用開一個陣列 char map[][];  去標記1
當作有連接 不過這樣的話  假使不是好的一張圖  所連接的邊  就會很少
就必須找到一個好的紀錄方法  來減少在做處理時候的次數  
如果不用內建的話
作法 I  :
    大開char map[N+1][N+1]; 去紀錄
    這樣的話  可能會有很多空的部份
    EX.
代碼: [選擇]
   while(scanf(“%d %d”,&N,&M)==2)
      {
        char map[100][100];//初使設定為0
         for(a=0;a<M;a++)
             scanf(“%d %d”,&x,&y),map[x][y]=1;
      }
作法 II :
    大開int map[N+1][K+1];
    N是點的編號最大號碼 K是一個點所能連接的最大節點個數
    當然這樣做的話,
    就必須再多一個陣列 int pt[N+1];去紀錄該點所連 接的節點個數
    EX.
代碼: [選擇]
     while(scanf(“%d %d”,&N,&M)==2)
      {
        int map[100][50],pt[100];//初使設定為0
         for(a=0;a<M;a++)
             scanf(“%d %d”,&x,&y),map[x][pt[x]++]=y;
      }
作法 III:
    當然大開 int map[N+1][K+1];
    還是有可能會得到一個RE,畢竟沒分配的那麼均勻
    所以假使他的邊最多有M個的話
    要記錄x->y的話
    則開 int xy[M][2]; //[][0]存放x [][1]存放y
    若會重複使用的話  最好將xy[][]對x做排序(y移動)
    如同上面的一樣  必須紀錄該點所連接的個數  所以必須開
    int pt[N+1];去紀錄該點所連接的節點個數  
    但是存的部份  依舊不是很容易找到  所以要開一個陣列 int sp[N+1];
    去紀錄x點在int xy[][] 的 最小索引值
    之後若要找x所連接的部份的話  則直接從
    
代碼: [選擇]
xy[sp[x]][1]->xy[sp[x]+pt[x]][1] 這些就都是x所連接的點了
代碼: [選擇]
#include<stdlib.h>
#include<stdio.h>
#define MAX 1000000001
int min(int x,int y)
{
     if(x>=y) return y;
     else return x;
}
int ptime[10002]={0},SP[10002]={0};
int data[1000000][3];
int MergeSort(int,int);
int Merge(int,int,int);
main()
{
  int N,M;
  while(scanf("%d %d",&M,&N)==2) //編號1~M個節點 有N個編
     {
        int a,b,c,d,x,y;
        for(a=0;a<N;a++)
           {
             scanf("%d %d %d",&x,&y,&d); //X->Y 權值 d
             data[a][0]=x,data[a][1]=y,data[a][2]=d;
             ptime[x]++; //紀錄點的個數
           }
        MergeSort(0,N-1);  //對X做排序
        for(a=1;a<=M;a++)    SP[a]=MAX; //先將索引值設定MAX
        for(a=0;a<N;a++)   //找出最小的索引值
            SP[data[a][0]]=min(a,SP[data[a][0]]);
        for(a=1;a<=M;a++)
          {
           printf("%d \n",a);
           for(b=SP[a],c=0;c<ptime[a];b++,c++)
             printf("    ->%d %d\n",data[b][1],data[b][2]);
          }
        for(a=1;a<=M;a++)// 用完記得歸0
           ptime[a]=0;
     }
   return 0;
}
int MergeSort(int l,int h)
{
   if(l<h)
      {
         int m=(l+h)/2;
         MergeSort(l,m);
         MergeSort(m+1,h);
         Merge(l,m,h);
      }
}
int x[100001][3];
int Merge(int l,int m,int h)
{
   int in1=l,in2=m+1,out=l;
   int top=0,a,b;
   while(in1<=m&&in2<=h)
      if(data[in1][0]>data[in2][0])
           x[top][2]=data[in2][2],x[top][1]=data[in2][1],x[top++][0]=data[in2++][0];
      else
           x[top][2]=data[in1][2],x[top][1]=data[in1][1],x[top++][0]=data[in1++][0];
   while(in1<=m)
       x[top][2]=data[in1][2],x[top][1]=data[in1][1],x[top++][0]=data[in1++][0];
   while(in2<=h)
       x[top][2]=data[in2][2],x[top][1]=data[in2][1],x[top++][0]=data[in2++][0];
   for(a=l,b=0;a<=h;a++,b++)
      data[a][0]=x[b][0],data[a][1]=x[b][1],data[a][2]=x[b][2];
}
做排序的部份  由於連接圖可能有很多重複的點  
對於快排可能比較不利  經過測試  合併排序會比較好
因為C語言沒有內建的  (貌似
而且不會用指標去做連接  所以才出此下策…
« 上次編輯: 十一月 29, 2009, 10:50:46 am 由 lose »
記錄

firejox

  • 新手
  • *
  • 文章數: 4
    • 檢視個人資料
Re: 不用內建作連接圖的方法
« 回覆 #1 於: 九月 24, 2011, 03:49:41 am »

其實可以用鄰接表建一張圖
用鄰接表就不會在稀疏圖會浪費空間
參考看看吧

有向圖建表大致如下
代碼: [選擇]
while (scanf("%d%d",&N,&M)!=EOF) {
    int first[N];
    int u[M],v[M];/*u -> v*/
    int next[M];
    for (i = 0;i < N;i++) first[i] = -1; /*initialize*/
    for (i = 0;i < M;i++) {
        scanf("%d%d",&u[i],&v[i]);
        next[i] = first[u[i]];
        first[u[i]] = i;
        }   
    }
假如要搜尋的話就可以這樣
代碼: [選擇]
for (i = first[a];i != -1;i = next[i])
    printf("%d\n",v[i]);

至於無向圖的話就可以視為雙向去做
所以可以變成這樣
代碼: [選擇]
while (scanf("%d%d",&N,&M)!=EOF) {
    int first[N];
    int node[M][2];
    int next[M*2];
    for (i = 0;i < N;i++) first[i] = -1;
    for (i = 0;i < M;i++) {
        scanf("%d%d",&node[i][0],&node[i][1]);
       
        j = i*2;tmp = node[i][1];
        next[j] = first[tmp];
        first[tmp] = j;
       
        j = i*2+1;tmp = node[i][0];
        next[j] = first[tmp];
        first[tmp] = j;
        }   
    }
搜尋就只要
代碼: [選擇]
for (i = first[a];i != -1;i = next[i])
    printf("%d\n",node[i>>1][i&1]);
這樣就可以了
記錄
+ NPSC補完計劃 » 一般 » 綜合討論區
 不用內建作連接圖的方法