Структура данных для представления графа

Множество OG(u)={v: (u,v)<=E} вершин графа G, являющихся концами ребер, выходящих из u называем окрестностью вершины u. Окрестность вершины i представляем списком, элементами которого являются пары вида (j, W(i, j)). Сам граф будет представлен массивом ADJ[1..n] указателей на списки, соответствующие окрестностям вершин.

Таким образом

  • если |OG(i)|=0, то ADJ[i]=nil,
  • в противном случае ADJ[i] является указателем на список, составленный из  вершин окрестности OG(i); элемент этого списка представляет собой имя j очередной вершины j<=OG(i), вес w = W(i,j) ребра (i,j) и указатель next на следующую вершину из OG(i); если вся окрестность исчерпана, то next = nil.

Ниже приведена часть кода программы, реализующей инициализацию графа.

<span style="color: #0000ff;">struct vtype</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">int name;</span>
<span style="color: #0000ff;">int w ;</span>
<span style="color: #0000ff;">vtype *next ;</span>
<span style="color: #0000ff;">void new_elem()</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">name = 0 ;</span>
<span style="color: #0000ff;">w = 0;</span>
<span style="color: #0000ff;">next = NULL ;</span>
<span style="color: #0000ff;">};</span>
<span style="color: #0000ff;">};</span>
<span style="color: #0000ff;">vtype** ADJ ;</span>
<span style="color: #0000ff;">int** my_graf ;</span>
<span style="color: #0000ff;">void init_graf(int n, int m)</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">int i,j,k, k1;</span>
<span style="color: #0000ff;">vtype* p ;</span>
<span style="color: #0000ff;">my_graf = new int* [n] ;</span>
<span style="color: #0000ff;">float mn;</span>
<span style="color: #0000ff;"> </span>
<span style="color: #0000ff;">ADJ =new vtype*[n] ;</span>
<span style="color: #0000ff;"> </span>
<span style="color: #0000ff;">for(i = 0 ; i &lt;n; ++i)</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">my_graf[i] = new int[n] ;</span>
<span style="color: #0000ff;">for(j = 0 ; j &lt; n ; ++j)</span>
<span style="color: #0000ff;">my_graf[i][j] = 0 ;</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;"> </span>
<span style="color: #0000ff;">mn = m / n ;</span>
<span style="color: #0000ff;">k = 0;</span>
<span style="color: #0000ff;">if(((m/2))||(m &lt; n))</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">for(i = 0 ; i &lt; n; ++i)</span>
<span style="color: #0000ff;">for(j = 0 ;j &lt; n; ++j)</span>
<span style="color: #0000ff;">if((i!=j)&amp;&amp;(k &lt;= (mn * (i+1))))</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">my_graf[i][j] = my_rand(r,q) ;</span>
<span style="color: #0000ff;">++k ;</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;">else</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">for(i = 0 ; i &lt; n; ++i)</span>
<span style="color: #0000ff;">for(j = 0 ;j &lt; n; ++j)</span>
<span style="color: #0000ff;">if((i!=j)&amp;&amp;(k &lt; (mn * (i+1))))</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">my_graf[i][j] = my_rand(r,q) ;</span>
<span style="color: #0000ff;">++k ;</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;"> </span>
<span style="color: #0000ff;"> </span>
<span style="color: #0000ff;">for(i = 0; i &lt; n; ++i)</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">ADJ[i] = NULL ;</span>
<span style="color: #0000ff;">for(j = 0 ; j &lt; n ; ++j)</span>
<span style="color: #0000ff;">if((i != j)&amp;&amp;(my_graf[i][j]&gt;0))</span>
<span style="color: #0000ff;">{</span>
<span style="color: #0000ff;">p = new vtype ;</span>
<span style="color: #0000ff;">(*p).name = j ;</span>
<span style="color: #0000ff;">(*p).w = my_graf[i][j] ;</span>
<span style="color: #0000ff;">(*p).next = ADJ[i] ;</span>
<span style="color: #0000ff;">ADJ[i] = p ;</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;">}</span>
<span style="color: #0000ff;">};</span>

Оставить комментарий

Вы должны быть зарегистрированы чтобы комментировать.