ਗ੍ਰਾਫਾਂ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਡੇਟਾ ਢਾਂਚੇ: ਮੌਜੂਦਾ ਅਤੇ ਦੋ "ਲਗਭਗ ਨਵੇਂ" ਦੀ ਸਮੀਖਿਆ

ਹਾਈ ਹਰ ਕੋਈ

ਇਸ ਨੋਟ ਵਿੱਚ, ਮੈਂ ਕੰਪਿਊਟਰ ਵਿਗਿਆਨ ਵਿੱਚ ਗ੍ਰਾਫਾਂ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਵਰਤੀਆਂ ਜਾਣ ਵਾਲੀਆਂ ਮੁੱਖ ਡਾਟਾ ਢਾਂਚਿਆਂ ਨੂੰ ਸੂਚੀਬੱਧ ਕਰਨ ਦਾ ਫੈਸਲਾ ਕੀਤਾ ਹੈ, ਅਤੇ ਮੈਂ ਕੁਝ ਹੋਰ ਅਜਿਹੇ ਢਾਂਚਿਆਂ ਬਾਰੇ ਵੀ ਗੱਲ ਕਰਾਂਗਾ ਜੋ ਕਿਸੇ ਤਰ੍ਹਾਂ ਮੇਰੇ ਲਈ "ਕ੍ਰਿਸਟਾਲ" ਹਨ।

ਇਸ ਲਈ, ਆਓ ਸ਼ੁਰੂ ਕਰੀਏ. ਪਰ ਸ਼ੁਰੂ ਤੋਂ ਹੀ ਨਹੀਂ - ਮੈਂ ਸੋਚਦਾ ਹਾਂ ਕਿ ਅਸੀਂ ਸਾਰੇ ਪਹਿਲਾਂ ਹੀ ਜਾਣਦੇ ਹਾਂ ਕਿ ਗ੍ਰਾਫ ਕੀ ਹੈ ਅਤੇ ਉਹ ਕੀ ਹਨ (ਨਿਰਦੇਸ਼ਿਤ, ਅਣ-ਨਿਰਦੇਸ਼ਿਤ, ਵਜ਼ਨ, ਅਣ-ਵਜ਼ਨ, ਕਈ ਕਿਨਾਰਿਆਂ ਅਤੇ ਲੂਪਸ ਦੇ ਨਾਲ ਜਾਂ ਬਿਨਾਂ)।

ਇਸ ਲਈ, ਆਓ ਚੱਲੀਏ। ਸਾਡੇ ਕੋਲ "ਗ੍ਰਾਫ ਸਟੋਰੇਜ" ਲਈ ਡੇਟਾ ਢਾਂਚੇ ਲਈ ਕਿਹੜੇ ਵਿਕਲਪ ਹਨ?

1. ਮੈਟ੍ਰਿਕਸ ਡੇਟਾ ਢਾਂਚੇ

1.1 ਅਨੁਕੂਲਤਾ ਮੈਟ੍ਰਿਕਸ। ਅਡਜੈਂਸੀ ਮੈਟ੍ਰਿਕਸ ਇੱਕ ਮੈਟ੍ਰਿਕਸ ਹੈ ਜਿੱਥੇ ਕਤਾਰ ਅਤੇ ਕਾਲਮ ਸਿਰਲੇਖ ਗ੍ਰਾਫ ਦੇ ਸਿਰਲੇਖਾਂ ਦੀਆਂ ਸੰਖਿਆਵਾਂ ਨਾਲ ਮੇਲ ਖਾਂਦੇ ਹਨ, ਅਤੇ ਇਸਦੇ ਹਰੇਕ ਤੱਤ a(i,j) ਦਾ ਮੁੱਲ ਕੋਨਾਵਾਂ ਦੇ ਵਿਚਕਾਰ ਕਿਨਾਰਿਆਂ ਦੀ ਮੌਜੂਦਗੀ ਜਾਂ ਗੈਰਹਾਜ਼ਰੀ ਦੁਆਰਾ ਨਿਰਧਾਰਤ ਕੀਤਾ ਜਾਂਦਾ ਹੈ। i ਅਤੇ j (ਇਹ ਸਪੱਸ਼ਟ ਹੈ ਕਿ ਇੱਕ ਨਿਰਦੇਸਿਤ ਗ੍ਰਾਫ਼ ਲਈ ਅਜਿਹਾ ਮੈਟ੍ਰਿਕਸ ਸਮਮਿਤੀ ਹੋਵੇਗਾ, ਜਾਂ ਅਸੀਂ ਇਸ ਗੱਲ ਨਾਲ ਸਹਿਮਤ ਹੋ ਸਕਦੇ ਹਾਂ ਕਿ ਅਸੀਂ ਸਾਰੇ ਮੁੱਲਾਂ ਨੂੰ ਮੁੱਖ ਵਿਕਰਣ ਦੇ ਉੱਪਰ ਹੀ ਸਟੋਰ ਕਰਦੇ ਹਾਂ)। ਬਿਨਾਂ ਵਜ਼ਨ ਵਾਲੇ ਗ੍ਰਾਫ਼ਾਂ ਲਈ, a(i,j) ਨੂੰ i ਤੋਂ j ਤੱਕ ਕਿਨਾਰਿਆਂ ਦੀ ਸੰਖਿਆ ਦੁਆਰਾ ਸੈੱਟ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ (ਜੇਕਰ ਅਜਿਹਾ ਕੋਈ ਕਿਨਾਰਾ ਨਹੀਂ ਹੈ, ਤਾਂ a(i,j)= 0), ਅਤੇ ਵਜ਼ਨ ਵਾਲੇ ਗ੍ਰਾਫ਼ਾਂ ਲਈ, ਭਾਰ ਦੁਆਰਾ ਵੀ ਜ਼ਿਕਰ ਕੀਤੇ ਕਿਨਾਰਿਆਂ ਦਾ (ਕੁੱਲ ਭਾਰ)।

1.2 ਘਟਨਾ ਮੈਟ੍ਰਿਕਸ। ਇਸ ਸਥਿਤੀ ਵਿੱਚ, ਸਾਡਾ ਗ੍ਰਾਫ ਇੱਕ ਸਾਰਣੀ ਵਿੱਚ ਵੀ ਸਟੋਰ ਕੀਤਾ ਜਾਂਦਾ ਹੈ ਜਿਸ ਵਿੱਚ, ਇੱਕ ਨਿਯਮ ਦੇ ਤੌਰ ਤੇ, ਕਤਾਰ ਸੰਖਿਆਵਾਂ ਇਸਦੇ ਸਿਰਲੇਖਾਂ ਦੀਆਂ ਸੰਖਿਆਵਾਂ ਨਾਲ ਮੇਲ ਖਾਂਦੀਆਂ ਹਨ, ਅਤੇ ਕਾਲਮ ਸੰਖਿਆਵਾਂ ਪੂਰਵ-ਸੰਖਿਆ ਵਾਲੇ ਕਿਨਾਰਿਆਂ ਨਾਲ ਮੇਲ ਖਾਂਦੀਆਂ ਹਨ। ਜੇਕਰ ਇੱਕ ਸਿਰਾ ਅਤੇ ਕਿਨਾਰਾ ਇੱਕ ਦੂਜੇ ਨਾਲ ਵਾਪਰਦਾ ਹੈ, ਤਾਂ ਅਨੁਸਾਰੀ ਸੈੱਲ ਵਿੱਚ ਇੱਕ ਗੈਰ-ਜ਼ੀਰੋ ਮੁੱਲ ਲਿਖਿਆ ਜਾਂਦਾ ਹੈ (ਅਨ-ਨਿਰਦੇਸ਼ਿਤ ਗ੍ਰਾਫਾਂ ਲਈ, 1 ਲਿਖਿਆ ਜਾਂਦਾ ਹੈ ਜੇਕਰ ਸਿਖਰ ਅਤੇ ਕਿਨਾਰਾ ਘਟਨਾ ਹਨ, ਓਰੀਐਂਟਿਡ ਗ੍ਰਾਫ਼ਾਂ ਲਈ - “1” ਜੇਕਰ ਕਿਨਾਰਾ ਸਿਰੇ ਤੋਂ “ਬਾਹਰ ਨਿਕਲਦਾ ਹੈ” ਅਤੇ “-1” ਜੇਕਰ ਇਸ ਵਿੱਚ “ਸ਼ਾਮਲ” ਹੈ (ਇਹ ਯਾਦ ਰੱਖਣਾ ਕਾਫ਼ੀ ਆਸਾਨ ਹੈ, ਕਿਉਂਕਿ “ਘਟਾਓ” ਚਿੰਨ੍ਹ ਵੀ “-1” ਨੰਬਰ ਵਿੱਚ “ਸ਼ਾਮਲ” ਜਾਪਦਾ ਹੈ)। ਭਾਰ ਵਾਲੇ ਗ੍ਰਾਫਾਂ ਲਈ, ਦੁਬਾਰਾ, 1 ਅਤੇ -1 ਦੀ ਬਜਾਏ, ਤੁਸੀਂ ਕਿਨਾਰੇ ਦਾ ਕੁੱਲ ਵਜ਼ਨ ਨਿਰਧਾਰਤ ਕਰ ਸਕਦੇ ਹੋ।

2. ਗਣਨਾ ਡੇਟਾ ਢਾਂਚੇ

2.1 ਅਨੁਕੂਲਤਾ ਸੂਚੀ। ਖੈਰ, ਇੱਥੇ ਸਭ ਕੁਝ ਸਧਾਰਨ ਜਾਪਦਾ ਹੈ. ਗ੍ਰਾਫ਼ ਦਾ ਹਰੇਕ ਸਿਰਲੇਖ, ਆਮ ਤੌਰ 'ਤੇ, ਕਿਸੇ ਵੀ ਗਣਨਾ ਢਾਂਚੇ (ਸੂਚੀ, ਵੈਕਟਰ, ਐਰੇ, ...) ਨਾਲ ਜੁੜਿਆ ਹੋ ਸਕਦਾ ਹੈ, ਜੋ ਦਿੱਤੇ ਗਏ ਇੱਕ ਦੇ ਨਾਲ ਲੱਗਦੇ ਸਾਰੇ ਸਿਰਲੇਖਾਂ ਦੀਆਂ ਸੰਖਿਆਵਾਂ ਨੂੰ ਸਟੋਰ ਕਰੇਗਾ। ਨਿਰਦੇਸ਼ਿਤ ਗ੍ਰਾਫ਼ਾਂ ਲਈ, ਅਸੀਂ ਅਜਿਹੀ ਸੂਚੀ ਵਿੱਚ ਸਿਰਫ਼ ਉਹਨਾਂ ਸਿਰਲੇਖਾਂ ਨੂੰ ਜੋੜਾਂਗੇ ਜਿਨ੍ਹਾਂ ਵਿੱਚ ਇੱਕ ਵਿਸ਼ੇਸ਼ਤਾ ਵਰਟੈਕਸ ਤੋਂ "ਨਿਰਦੇਸ਼ਿਤ" ਕਿਨਾਰਾ ਹੈ। ਭਾਰ ਵਾਲੇ ਗ੍ਰਾਫਾਂ ਲਈ ਲਾਗੂ ਕਰਨਾ ਵਧੇਰੇ ਗੁੰਝਲਦਾਰ ਹੋਵੇਗਾ।

2.2 ਪੱਸਲੀਆਂ ਦੀ ਸੂਚੀ। ਕਾਫ਼ੀ ਇੱਕ ਪ੍ਰਸਿੱਧ ਡਾਟਾ ਬਣਤਰ. ਕਿਨਾਰਿਆਂ ਦੀ ਸੂਚੀ, ਜਿਵੇਂ ਕਿ ਕੈਪਟਨ ਸਪੱਸ਼ਟਤਾ ਸਾਨੂੰ ਦੱਸਦੀ ਹੈ, ਅਸਲ ਵਿੱਚ ਗ੍ਰਾਫ ਦੇ ਕਿਨਾਰਿਆਂ ਦੀ ਇੱਕ ਸੂਚੀ ਹੈ, ਜਿਸ ਵਿੱਚੋਂ ਹਰ ਇੱਕ ਸ਼ੁਰੂਆਤੀ ਸਿਰਲੇਖ, ਅੰਤ ਦੇ ਸਿਖਰ ਦੁਆਰਾ ਨਿਰਧਾਰਤ ਕੀਤਾ ਗਿਆ ਹੈ (ਅਨਿਰਦੇਸ਼ਿਤ ਗ੍ਰਾਫਾਂ ਲਈ ਇੱਥੇ ਆਰਡਰ ਮਹੱਤਵਪੂਰਨ ਨਹੀਂ ਹੈ, ਹਾਲਾਂਕਿ ਤੁਸੀਂ ਏਕੀਕਰਣ ਲਈ ਵੱਖੋ-ਵੱਖਰੇ ਨਿਯਮਾਂ ਦੀ ਵਰਤੋਂ ਕਰੋ, ਉਦਾਹਰਨ ਲਈ, ਵਧਦੇ ਕ੍ਰਮ ਵਿੱਚ ਸਿਰਿਆਂ ਨੂੰ ਨਿਰਧਾਰਤ ਕਰਨਾ) ਅਤੇ ਭਾਰ (ਸਿਰਫ਼ ਭਾਰ ਵਾਲੇ ਗ੍ਰਾਫਾਂ ਲਈ)।

ਤੁਸੀਂ ਉੱਪਰ ਸੂਚੀਬੱਧ ਮੈਟ੍ਰਿਕਸ ਸੂਚੀਆਂ ਨੂੰ ਹੋਰ ਵਿਸਤਾਰ ਵਿੱਚ ਦੇਖ ਸਕਦੇ ਹੋ (ਅਤੇ ਦ੍ਰਿਸ਼ਟਾਂਤ ਦੇ ਨਾਲ), ਉਦਾਹਰਨ ਲਈ, ਇੱਥੇ.

2.3 ਅਨੁਕੂਲਤਾ ਐਰੇ। ਸਭ ਤੋਂ ਆਮ ਬਣਤਰ ਨਹੀਂ. ਇਸਦੇ ਮੂਲ ਰੂਪ ਵਿੱਚ, ਇਹ ਇੱਕ ਗਣਨਾ ਬਣਤਰ (ਐਰੇ, ਵੈਕਟਰ) ਵਿੱਚ "ਪੈਕਿੰਗ" ਨਾਲ ਜੁੜੀਆਂ ਸੂਚੀਆਂ ਦਾ ਇੱਕ ਰੂਪ ਹੈ। ਅਜਿਹੇ ਐਰੇ ਦੇ ਪਹਿਲੇ n (ਗ੍ਰਾਫ਼ ਦੇ ਸਿਰਲੇਖਾਂ ਦੀ ਸੰਖਿਆ ਦੇ ਅਨੁਸਾਰ) ਤੱਤਾਂ ਵਿੱਚ ਉਸੇ ਐਰੇ ਦੇ ਸ਼ੁਰੂਆਤੀ ਸੂਚਕਾਂਕ ਹੁੰਦੇ ਹਨ, ਜਿਸ ਤੋਂ ਸ਼ੁਰੂ ਕਰਦੇ ਹੋਏ ਦਿੱਤੇ ਗਏ ਇੱਕ ਦੇ ਨਾਲ ਲੱਗਦੇ ਸਾਰੇ ਸਿਰਲੇਖ ਇੱਕ ਕਤਾਰ ਵਿੱਚ ਲਿਖੇ ਜਾਂਦੇ ਹਨ।

ਇੱਥੇ ਮੈਨੂੰ ਸਭ ਤੋਂ ਸਮਝਣ ਯੋਗ (ਆਪਣੇ ਲਈ) ਵਿਆਖਿਆ ਮਿਲੀ: ejuo.livejournal.com/4518.html

3. ਅਡਜੇਸੈਂਸੀ ਵੈਕਟਰ ਅਤੇ ਐਸੋਸੀਏਟਿਵ ਐਡਜੈਂਸੀ ਐਰੇ

ਇਹ ਪਤਾ ਚਲਿਆ ਕਿ ਇਹਨਾਂ ਲਾਈਨਾਂ ਦਾ ਲੇਖਕ, ਇੱਕ ਪੇਸ਼ੇਵਰ ਪ੍ਰੋਗਰਾਮਰ ਨਹੀਂ ਹੈ, ਪਰ ਜੋ ਸਮੇਂ-ਸਮੇਂ 'ਤੇ ਗ੍ਰਾਫਾਂ ਨਾਲ ਨਜਿੱਠਦਾ ਹੈ, ਅਕਸਰ ਕਿਨਾਰਿਆਂ ਦੀਆਂ ਸੂਚੀਆਂ ਨਾਲ ਨਜਿੱਠਦਾ ਹੈ. ਦਰਅਸਲ, ਇਹ ਸੁਵਿਧਾਜਨਕ ਹੈ ਜੇਕਰ ਗ੍ਰਾਫ ਵਿੱਚ ਕਈ ਲੂਪਸ ਅਤੇ ਕਿਨਾਰੇ ਹਨ। ਅਤੇ ਇਸ ਲਈ, ਕਿਨਾਰਿਆਂ ਦੀਆਂ ਕਲਾਸਿਕ ਸੂਚੀਆਂ ਦੇ ਵਿਕਾਸ ਵਿੱਚ, ਮੈਂ ਉਹਨਾਂ ਦੇ "ਵਿਕਾਸ/ਸ਼ਾਖਾ/ਸੋਧ/ਮਿਊਟੇਸ਼ਨ" ਵੱਲ ਧਿਆਨ ਦੇਣ ਦੀ ਤਜਵੀਜ਼ ਕਰਦਾ ਹਾਂ, ਅਰਥਾਤ: ਅਡਜੇਸੈਂਸੀ ਵੈਕਟਰ ਅਤੇ ਐਸੋਸਿਏਟਿਵ ਐਡਜੈਂਸੀ ਐਰੇ।

3.1 ਅਨੁਕੂਲਤਾ ਵੈਕਟਰ

ਕੇਸ (a1): ਬਿਨਾਂ ਵਜ਼ਨ ਵਾਲਾ ਗ੍ਰਾਫ

ਅਸੀਂ ਇੱਕ ਅਨਵੇਟਡ ਗ੍ਰਾਫ਼ ਲਈ ਇੱਕ ਅਡਜੈਂਸੀ ਵੈਕਟਰ ਨੂੰ ਕਾਲ ਕਰਾਂਗੇ ਇੱਕ ਬਰਾਬਰ ਸੰਖਿਆ ਦੇ ਪੂਰਨ ਅੰਕਾਂ (a[2i], a[2i+1],..., ਜਿੱਥੇ i ਨੂੰ c 0 ਨੰਬਰ ਦਿੱਤਾ ਗਿਆ ਹੈ), ਜਿਸ ਵਿੱਚ ਸੰਖਿਆਵਾਂ ਦਾ ਹਰੇਕ ਜੋੜਾ a[2i] ਹੈ, a[2i+1] ਕ੍ਰਮਵਾਰ a[2i] ਅਤੇ a[2i+1] ਦੇ ਵਿਚਕਾਰ ਇੱਕ ਗ੍ਰਾਫ਼ ਕਿਨਾਰੇ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ।
ਇਸ ਰਿਕਾਰਡਿੰਗ ਫਾਰਮੈਟ ਵਿੱਚ ਇਹ ਜਾਣਕਾਰੀ ਨਹੀਂ ਹੈ ਕਿ ਕੀ ਗ੍ਰਾਫ ਨੂੰ ਨਿਰਦੇਸ਼ਿਤ ਕੀਤਾ ਗਿਆ ਹੈ (ਦੋਵੇਂ ਵਿਕਲਪ ਸੰਭਵ ਹਨ)। ਡਾਇਗ੍ਰਾਫ ਫਾਰਮੈਟ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਸਮੇਂ, ਕਿਨਾਰੇ ਨੂੰ a[2i] ਤੋਂ a[2i+1] ਵੱਲ ਨਿਰਦੇਸ਼ਿਤ ਮੰਨਿਆ ਜਾਂਦਾ ਹੈ। ਇੱਥੇ ਅਤੇ ਹੇਠਾਂ: ਬਿਨਾਂ ਨਿਰਦੇਸ਼ਿਤ ਗ੍ਰਾਫ਼ਾਂ ਲਈ, ਜੇਕਰ ਲੋੜ ਹੋਵੇ, ਤਾਂ ਰਿਕਾਰਡਿੰਗ ਕੋਣਾਂ ਦੇ ਕ੍ਰਮ ਲਈ ਲੋੜਾਂ ਲਾਗੂ ਕੀਤੀਆਂ ਜਾ ਸਕਦੀਆਂ ਹਨ (ਉਦਾਹਰਨ ਲਈ, ਇਸ ਨੂੰ ਨਿਰਧਾਰਤ ਕੀਤੇ ਗਏ ਨੰਬਰ ਦੇ ਹੇਠਲੇ ਮੁੱਲ ਵਾਲਾ ਸਿਖਰ ਪਹਿਲਾਂ ਆਉਂਦਾ ਹੈ)।

C++ ਵਿੱਚ, std::vector ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਇੱਕ ਅਡਜੈਂਸੀ ਵੈਕਟਰ ਨਿਰਧਾਰਤ ਕਰਨ ਦੀ ਸਲਾਹ ਦਿੱਤੀ ਜਾਂਦੀ ਹੈ, ਇਸਲਈ ਇਸ ਡੇਟਾ ਢਾਂਚੇ ਦਾ ਨਾਮ।

ਕੇਸ (a2): ਬਿਨਾਂ ਵਜ਼ਨ ਵਾਲਾ ਗ੍ਰਾਫ, ਕਿਨਾਰੇ ਦੇ ਵਜ਼ਨ ਪੂਰਨ ਅੰਕ ਹਨ

ਕੇਸ (a1) ਦੇ ਨਾਲ ਸਮਾਨਤਾ ਦੁਆਰਾ, ਅਸੀਂ ਸੰਖਿਆਵਾਂ (a[3i], a[3i+1], a[3i+2], ਸੰਖਿਆਵਾਂ ਦੇ ਕ੍ਰਮਬੱਧ ਸੈੱਟ (ਡਾਇਨਾਮਿਕ ਐਰੇ) ਦੇ ਨਾਲ ਪੂਰਨ ਅੰਕ ਦੇ ਭਾਰ ਵਾਲੇ ਗ੍ਰਾਫ ਲਈ ਅਡਜੈਂਸੀ ਵੈਕਟਰ ਕਹਿੰਦੇ ਹਾਂ। ..., ਜਿੱਥੇ i ਨੂੰ c 0 ਨੰਬਰ ਦਿੱਤਾ ਗਿਆ ਹੈ), ਜਿੱਥੇ ਨੰਬਰ a[3i], a[3i+1], a[3i+2] ਨੰਬਰਾਂ ਦਾ ਹਰੇਕ "ਤਿਹਰੀ" a[3i] ਨੰਬਰ ਵਾਲੇ ਸਿਰਲੇਖਾਂ ਦੇ ਵਿਚਕਾਰ ਗ੍ਰਾਫ ਦਾ ਇੱਕ ਕਿਨਾਰਾ ਨਿਸ਼ਚਿਤ ਕਰਦਾ ਹੈ। ਅਤੇ a[3i+1], ਕ੍ਰਮਵਾਰ, ਅਤੇ ਮੁੱਲ a [3i+2] ਇਸ ਕਿਨਾਰੇ ਦਾ ਭਾਰ ਹੈ। ਅਜਿਹੇ ਗ੍ਰਾਫ ਨੂੰ ਜਾਂ ਤਾਂ ਨਿਰਦੇਸ਼ਿਤ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ ਜਾਂ ਨਹੀਂ।

ਕੇਸ (ਬੀ): ਬਿਨਾਂ ਵਜ਼ਨ ਵਾਲਾ ਗ੍ਰਾਫ਼, ਗੈਰ-ਪੂਰਨ ਅੰਕ ਵਾਲੇ ਕਿਨਾਰੇ ਦਾ ਵਜ਼ਨ

ਕਿਉਂਕਿ ਇੱਕ ਐਰੇ (ਵੈਕਟਰ) ਵਿੱਚ ਵਿਭਿੰਨ ਤੱਤਾਂ ਨੂੰ ਸਟੋਰ ਕਰਨਾ ਅਸੰਭਵ ਹੈ, ਉਦਾਹਰਨ ਲਈ, ਹੇਠਾਂ ਦਿੱਤਾ ਲਾਗੂ ਕਰਨਾ ਸੰਭਵ ਹੈ। ਗ੍ਰਾਫ ਨੂੰ ਵੈਕਟਰਾਂ ਦੇ ਇੱਕ ਜੋੜੇ ਵਿੱਚ ਸਟੋਰ ਕੀਤਾ ਜਾਂਦਾ ਹੈ, ਜਿਸ ਵਿੱਚ ਪਹਿਲਾ ਵੈਕਟਰ ਗ੍ਰਾਫ ਦਾ ਨੇੜੇ ਦਾ ਵੈਕਟਰ ਹੁੰਦਾ ਹੈ, ਬਿਨਾਂ ਵਜ਼ਨ ਦੱਸੇ, ਅਤੇ ਦੂਜੇ ਵੈਕਟਰ ਵਿੱਚ ਅਨੁਸਾਰੀ ਵਜ਼ਨ ਹੁੰਦੇ ਹਨ (C++: std::pair ਲਈ ਸੰਭਵ ਲਾਗੂ ਕਰਨਾ ). ਇਸ ਤਰ੍ਹਾਂ, ਪਹਿਲੇ ਵੈਕਟਰ ਦੇ ਸੂਚਕਾਂਕ 2i, 2i+1 ਦੇ ਅਧੀਨ ਕੋਣਾਂ ਦੇ ਇੱਕ ਜੋੜੇ ਦੁਆਰਾ ਪਰਿਭਾਸ਼ਿਤ ਕਿਨਾਰੇ ਲਈ, ਭਾਰ ਦੂਜੇ ਵੈਕਟਰ ਦੇ ਸੂਚਕਾਂਕ i ਦੇ ਹੇਠਾਂ ਤੱਤ ਦੇ ਬਰਾਬਰ ਹੋਵੇਗਾ।

ਖੈਰ, ਇਹ ਕਿਉਂ ਜ਼ਰੂਰੀ ਹੈ?

ਖੈਰ, ਇਹਨਾਂ ਸਤਰਾਂ ਦੇ ਲੇਖਕ ਨੇ ਬਹੁਤ ਸਾਰੀਆਂ ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਇਹ ਕਾਫ਼ੀ ਲਾਭਦਾਇਕ ਪਾਇਆ. ਖੈਰ, ਰਸਮੀ ਦ੍ਰਿਸ਼ਟੀਕੋਣ ਤੋਂ, ਹੇਠਾਂ ਦਿੱਤੇ ਫਾਇਦੇ ਹੋਣਗੇ:

• ਅਡਜੈਂਸੀ ਵੈਕਟਰ, ਜਿਵੇਂ ਕਿ ਕਿਸੇ ਹੋਰ "ਗਿਣਤੀ" ਬਣਤਰ ਦੀ ਤਰ੍ਹਾਂ, ਕਾਫ਼ੀ ਸੰਖੇਪ ਹੈ, ਅਡਜੈਂਸੀ ਮੈਟ੍ਰਿਕਸ (ਸਪਾਰਸ ਗ੍ਰਾਫਾਂ ਲਈ) ਨਾਲੋਂ ਘੱਟ ਮੈਮੋਰੀ ਲੈਂਦਾ ਹੈ, ਅਤੇ ਲਾਗੂ ਕਰਨਾ ਮੁਕਾਬਲਤਨ ਆਸਾਨ ਹੁੰਦਾ ਹੈ।
• ਗ੍ਰਾਫ ਦੇ ਸਿਰਲੇਖਾਂ ਨੂੰ, ਸਿਧਾਂਤ ਵਿੱਚ, ਨਕਾਰਾਤਮਕ ਸੰਖਿਆਵਾਂ ਨਾਲ ਵੀ ਚਿੰਨ੍ਹਿਤ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ। ਉਦੋਂ ਕੀ ਜੇ ਅਜਿਹੇ "ਵਿਗਾੜ" ਦੀ ਲੋੜ ਹੈ?
• ਗ੍ਰਾਫ਼ਾਂ ਵਿੱਚ ਵੱਖ-ਵੱਖ ਵਜ਼ਨ (ਸਕਾਰਾਤਮਕ, ਨਕਾਰਾਤਮਕ, ਇੱਥੋਂ ਤੱਕ ਕਿ ਜ਼ੀਰੋ) ਦੇ ਨਾਲ, ਕਈ ਕਿਨਾਰਿਆਂ ਅਤੇ ਕਈ ਲੂਪਸ ਹੋ ਸਕਦੇ ਹਨ। ਇੱਥੇ ਕੋਈ ਪਾਬੰਦੀਆਂ ਨਹੀਂ ਹਨ।
• ਤੁਸੀਂ ਕਿਨਾਰਿਆਂ ਨੂੰ ਵੱਖ-ਵੱਖ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਵੀ ਨਿਰਧਾਰਤ ਕਰ ਸਕਦੇ ਹੋ - ਪਰ ਇਸ ਬਾਰੇ ਹੋਰ ਜਾਣਕਾਰੀ ਲਈ, ਸੈਕਸ਼ਨ 4 ਦੇਖੋ।

ਹਾਲਾਂਕਿ, ਇਹ ਮੰਨਿਆ ਜਾਣਾ ਚਾਹੀਦਾ ਹੈ ਕਿ ਇਹ "ਸੂਚੀ" ਕਿਨਾਰੇ ਤੱਕ ਤੁਰੰਤ ਪਹੁੰਚ ਦਾ ਮਤਲਬ ਨਹੀਂ ਹੈ। ਅਤੇ ਇੱਥੇ ਐਸੋਸੀਏਟਿਵ ਅਡਜੈਂਸੀ ਐਰੇ ਬਚਾਅ ਲਈ ਆਉਂਦਾ ਹੈ, ਜਿਸ ਬਾਰੇ ਹੇਠਾਂ ਚਰਚਾ ਕੀਤੀ ਗਈ ਹੈ।

3.2 ਐਸੋਸੀਏਟਿਵ ਅਡਜੈਂਸੀ ਐਰੇ

ਇਸ ਲਈ, ਜੇਕਰ ਕਿਸੇ ਖਾਸ ਕਿਨਾਰੇ ਤੱਕ ਪਹੁੰਚ, ਇਸਦਾ ਭਾਰ ਅਤੇ ਹੋਰ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਸਾਡੇ ਲਈ ਮਹੱਤਵਪੂਰਨ ਹਨ, ਅਤੇ ਯਾਦਦਾਸ਼ਤ ਦੀਆਂ ਲੋੜਾਂ ਸਾਨੂੰ ਅਡਜੈਂਸੀ ਮੈਟ੍ਰਿਕਸ ਦੀ ਵਰਤੋਂ ਕਰਨ ਦੀ ਇਜਾਜ਼ਤ ਨਹੀਂ ਦਿੰਦੀਆਂ, ਤਾਂ ਆਓ ਇਸ ਬਾਰੇ ਸੋਚੀਏ ਕਿ ਅਸੀਂ ਇਸ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਅਡਜੈਂਸੀ ਵੈਕਟਰ ਨੂੰ ਕਿਵੇਂ ਬਦਲ ਸਕਦੇ ਹਾਂ। ਇਸ ਲਈ, ਕੁੰਜੀ ਗ੍ਰਾਫ਼ ਦਾ ਇੱਕ ਕਿਨਾਰਾ ਹੈ, ਜਿਸਨੂੰ ਪੂਰਨ ਅੰਕਾਂ ਦੇ ਇੱਕ ਕ੍ਰਮਬੱਧ ਜੋੜੇ ਦੇ ਰੂਪ ਵਿੱਚ ਨਿਰਧਾਰਤ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ। ਇਹ ਕਿਹੋ ਜਿਹਾ ਦਿਸਦਾ ਹੈ? ਕੀ ਇਹ ਇੱਕ ਸਹਿਯੋਗੀ ਐਰੇ ਵਿੱਚ ਇੱਕ ਕੁੰਜੀ ਨਹੀਂ ਹੈ? ਅਤੇ, ਜੇਕਰ ਹਾਂ, ਤਾਂ ਅਸੀਂ ਇਸਨੂੰ ਲਾਗੂ ਕਿਉਂ ਨਹੀਂ ਕਰਦੇ? ਸਾਡੇ ਕੋਲ ਇੱਕ ਐਸੋਸਿਏਟਿਵ ਐਰੇ ਹੈ ਜਿੱਥੇ ਹਰੇਕ ਕੁੰਜੀ - ਪੂਰਨ ਅੰਕਾਂ ਦਾ ਇੱਕ ਕ੍ਰਮਬੱਧ ਜੋੜਾ - ਇੱਕ ਮੁੱਲ - ਇੱਕ ਪੂਰਨ ਅੰਕ ਜਾਂ ਇੱਕ ਅਸਲ ਸੰਖਿਆ ਜੋ ਕਿਨਾਰੇ ਦੇ ਭਾਰ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ ਨਾਲ ਜੁੜਿਆ ਹੋਵੇਗਾ। C++ ਵਿੱਚ, std::map ਕੰਟੇਨਰ (std::map) ਦੇ ਅਧਾਰ ਤੇ ਇਸ ਢਾਂਚੇ ਨੂੰ ਲਾਗੂ ਕਰਨ ਦੀ ਸਲਾਹ ਦਿੱਤੀ ਜਾਂਦੀ ਹੈ , int> ਜਾਂ std::map , double>), ਜਾਂ std::ਮਲਟੀਮੈਪ ਜੇਕਰ ਕਈ ਕਿਨਾਰਿਆਂ ਦੀ ਉਮੀਦ ਕੀਤੀ ਜਾਂਦੀ ਹੈ। ਖੈਰ, ਸਾਡੇ ਕੋਲ ਗ੍ਰਾਫਾਂ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਇੱਕ ਢਾਂਚਾ ਹੈ ਜੋ "ਮੈਟ੍ਰਿਕਸ" ਬਣਤਰਾਂ ਨਾਲੋਂ ਘੱਟ ਮੈਮੋਰੀ ਲੈਂਦਾ ਹੈ, ਕਈ ਲੂਪਸ ਅਤੇ ਕਿਨਾਰਿਆਂ ਨਾਲ ਗ੍ਰਾਫਾਂ ਨੂੰ ਪਰਿਭਾਸ਼ਿਤ ਕਰ ਸਕਦਾ ਹੈ, ਅਤੇ ਵਰਟੇਕਸ ਨੰਬਰਾਂ ਦੀ ਗੈਰ-ਨਕਾਰਾਤਮਕਤਾ ਲਈ ਸਖਤ ਲੋੜਾਂ ਵੀ ਨਹੀਂ ਹਨ (ਮੈਨੂੰ ਨਹੀਂ ਪਤਾ ਕਿਸ ਨੂੰ ਇਸਦੀ ਲੋੜ ਹੈ, ਪਰ ਫਿਰ ਵੀ).

4. ਡਾਟਾ ਬਣਤਰ ਭਰੇ ਹੋਏ ਹਨ, ਪਰ ਕੁਝ ਗੁੰਮ ਹੈ

ਅਤੇ ਇਹ ਸੱਚ ਹੈ: ਕਈ ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਹੱਲ ਕਰਦੇ ਸਮੇਂ, ਸਾਨੂੰ ਗ੍ਰਾਫ ਦੇ ਕਿਨਾਰਿਆਂ ਨੂੰ ਕੁਝ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਨਿਰਧਾਰਤ ਕਰਨ ਦੀ ਲੋੜ ਹੋ ਸਕਦੀ ਹੈ ਅਤੇ, ਇਸਦੇ ਅਨੁਸਾਰ, ਉਹਨਾਂ ਨੂੰ ਸਟੋਰ ਕਰਨਾ ਚਾਹੀਦਾ ਹੈ। ਜੇਕਰ ਇਹਨਾਂ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਨੂੰ ਸਪਸ਼ਟ ਰੂਪ ਵਿੱਚ ਪੂਰਨ ਅੰਕਾਂ ਤੱਕ ਘਟਾਉਣਾ ਸੰਭਵ ਹੈ, ਤਾਂ ਸੰਜੋਗ ਵੈਕਟਰ ਅਤੇ ਐਸੋਸਿਏਟਿਵ ਅਡਜੈਂਸੀ ਐਰੇ ਦੇ ਵਿਸਤ੍ਰਿਤ ਸੰਸਕਰਣਾਂ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ ਅਜਿਹੇ "ਵਾਧੂ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਵਾਲੇ ਗ੍ਰਾਫ" ਨੂੰ ਸਟੋਰ ਕਰਨਾ ਸੰਭਵ ਹੈ।

ਇਸ ਲਈ, ਆਓ ਅਸੀਂ ਇੱਕ ਭਾਰ ਰਹਿਤ ਗ੍ਰਾਫ਼ ਕਰੀਏ, ਜਿਸ ਦੇ ਹਰੇਕ ਕਿਨਾਰੇ ਲਈ ਸਟੋਰ ਕਰਨਾ ਜ਼ਰੂਰੀ ਹੈ, ਉਦਾਹਰਨ ਲਈ, ਪੂਰਨ ਅੰਕਾਂ ਦੁਆਰਾ ਨਿਰਧਾਰਤ 2 ਵਾਧੂ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ। ਇਸ ਸਥਿਤੀ ਵਿੱਚ, ਇਸਦੇ ਨਾਲ ਲੱਗਦੇ ਵੈਕਟਰ ਨੂੰ "ਜੋੜਿਆਂ" ਦੇ ਨਹੀਂ, ਸਗੋਂ ਪੂਰਨ ਅੰਕਾਂ (a[2i], a[2i+1], a[2i+2], a ਦੇ "ਚੌਥਾਈ" ਦੇ ਇੱਕ ਕ੍ਰਮਬੱਧ ਸੈੱਟ ਵਜੋਂ ਪਰਿਭਾਸ਼ਿਤ ਕਰਨਾ ਸੰਭਵ ਹੈ. [2i+3]…), ਜਿੱਥੇ a[2i+2] ਅਤੇ a[2i+3] ਸੰਬੰਧਿਤ ਕਿਨਾਰੇ ਦੀਆਂ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਨੂੰ ਨਿਰਧਾਰਤ ਕਰਨਗੇ। ਕਿਨਾਰਿਆਂ ਦੇ ਪੂਰਨ ਅੰਕ ਵਜ਼ਨ ਵਾਲੇ ਗ੍ਰਾਫ਼ ਲਈ, ਕ੍ਰਮ ਆਮ ਤੌਰ 'ਤੇ ਸਮਾਨ ਹੁੰਦਾ ਹੈ (ਸਿਰਫ਼ ਫ਼ਰਕ ਇਹ ਹੋਵੇਗਾ ਕਿ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਕਿਨਾਰੇ ਦੇ ਭਾਰ ਦਾ ਅਨੁਸਰਣ ਕਰਨਗੀਆਂ ਅਤੇ ਐਲੀਮੈਂਟਸ a[2i+3] ਅਤੇ a[2i+4] ਦੁਆਰਾ ਨਿਰਧਾਰਤ ਕੀਤੀਆਂ ਜਾਣਗੀਆਂ। , ਅਤੇ ਕਿਨਾਰੇ ਨੂੰ ਖੁਦ 4 ਨਹੀਂ, ਸਗੋਂ 5 ਆਰਡਰ ਕੀਤੇ ਨੰਬਰ ਦਿੱਤੇ ਜਾਣਗੇ)। ਅਤੇ ਗੈਰ-ਪੂਰਨ ਅੰਕ ਵਾਲੇ ਕਿਨਾਰੇ ਦੇ ਵਜ਼ਨ ਵਾਲੇ ਗ੍ਰਾਫ ਲਈ, ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਨੂੰ ਇਸਦੇ ਅਣ-ਵਜ਼ਨ ਵਾਲੇ ਹਿੱਸੇ ਵਿੱਚ ਲਿਖਿਆ ਜਾ ਸਕਦਾ ਹੈ।

ਪੂਰਨ ਅੰਕ ਦੇ ਕਿਨਾਰੇ ਦੇ ਵਜ਼ਨ ਵਾਲੇ ਗ੍ਰਾਫਾਂ ਲਈ ਇੱਕ ਐਸੋਸਿਏਟਿਵ ਅਡਜਸੈਂਸੀ ਐਰੇ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਸਮੇਂ, ਕਿਸੇ ਇੱਕ ਸੰਖਿਆ ਨੂੰ ਨਹੀਂ, ਸਗੋਂ ਸੰਖਿਆਵਾਂ ਦੀ ਇੱਕ ਐਰੇ (ਵੈਕਟਰ) ਦੇ ਰੂਪ ਵਿੱਚ ਨਿਰਧਾਰਤ ਕਰਨਾ ਸੰਭਵ ਹੈ, ਜੋ ਕਿ ਕਿਨਾਰੇ ਦੇ ਭਾਰ ਤੋਂ ਇਲਾਵਾ, ਇਸਦੇ ਹੋਰ ਸਾਰੇ ਜ਼ਰੂਰੀ ਹਨ। ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ। ਇਸ ਦੇ ਨਾਲ ਹੀ, ਗੈਰ-ਅੰਤਰ ਅੰਕ ਵਜ਼ਨ ਦੇ ਮਾਮਲੇ ਲਈ ਇੱਕ ਅਸੁਵਿਧਾ ਇੱਕ ਫਲੋਟਿੰਗ ਪੁਆਇੰਟ ਨੰਬਰ ਦੇ ਨਾਲ ਇੱਕ ਚਿੰਨ੍ਹ ਨਿਰਧਾਰਤ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੋਵੇਗੀ (ਹਾਂ, ਇਹ ਇੱਕ ਅਸੁਵਿਧਾ ਹੈ, ਪਰ ਜੇਕਰ ਅਜਿਹੇ ਬਹੁਤ ਸਾਰੇ ਚਿੰਨ੍ਹ ਨਹੀਂ ਹਨ, ਅਤੇ ਜੇਕਰ ਤੁਸੀਂ ਡਾਨ ਉਹਨਾਂ ਨੂੰ ਬਹੁਤ "ਛਲ" ਡਬਲ ਸੈੱਟ ਨਾ ਕਰੋ, ਫਿਰ ਇਹ ਕੁਝ ਵੀ ਨਹੀਂ ਹੋ ਸਕਦਾ)। ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ C++ ਵਿੱਚ ਐਕਸਟੈਂਡਡ ਐਸੋਸੀਏਟਿਵ ਅਡਜੈਂਸੀ ਐਰੇ ਨੂੰ ਇਸ ਤਰ੍ਹਾਂ ਪਰਿਭਾਸ਼ਿਤ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ: std::map , std::vector> ਜਾਂ std::map , std::vector, ਜਿਸ ਵਿੱਚ "ਕੁੰਜੀ-ਮੁੱਲ-ਵੈਕਟਰ" ਵਿੱਚ ਪਹਿਲਾ ਮੁੱਲ ਕਿਨਾਰੇ ਦਾ ਭਾਰ ਹੋਵੇਗਾ, ਅਤੇ ਫਿਰ ਇਸ ਦੀਆਂ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਦੇ ਸੰਖਿਆਤਮਕ ਅਹੁਦਿਆਂ 'ਤੇ ਸਥਿਤ ਹੈ।

ਸਾਹਿਤ:

ਆਮ ਤੌਰ 'ਤੇ ਗ੍ਰਾਫ ਅਤੇ ਐਲਗੋਰਿਦਮ ਬਾਰੇ:

1. ਕੋਰਮੇਨ, ਥਾਮਸ ਐਚ., ਲੀਜ਼ਰਸਨ, ਚਾਰਲਸ ਆਈ., ਰਿਵੈਸਟ, ਰੋਨਾਲਡ ਐਲ., ਸਟੀਨ, ਕਲਿਫੋਰਡ। ਐਲਗੋਰਿਦਮ: ਨਿਰਮਾਣ ਅਤੇ ਵਿਸ਼ਲੇਸ਼ਣ, ਦੂਜਾ ਐਡੀਸ਼ਨ: ਟ੍ਰਾਂਸ. ਅੰਗਰੇਜ਼ੀ ਤੋਂ - ਐੱਮ.: ਵਿਲੀਅਮਜ਼ ਪਬਲਿਸ਼ਿੰਗ ਹਾਊਸ, 2।
2. ਹਾਰਰੀ ਫਰੈਂਕ। ਗ੍ਰਾਫ ਥਿਊਰੀ. ਐੱਮ.: ਮੀਰ, 1973।
ਲੇਖਕ ਦੀ ਰਿਪੋਰਟ ਇਹਨਾਂ ਸਮਾਨ ਵੈਕਟਰ ਅਤੇ ਆਸ-ਪਾਸ ਦੇ ਸਹਿਯੋਗੀ ਐਰੇ ਬਾਰੇ:
3. ਚੇਰਨੋਖੋਵ ਐਸ.ਏ. ਗ੍ਰਾਫਾਂ ਨੂੰ ਪ੍ਰਸਤੁਤ ਕਰਨ ਅਤੇ ਸਟੋਰ ਕਰਨ ਦੇ ਤਰੀਕਿਆਂ ਵਜੋਂ ਅਡਜੇਸੈਂਸੀ ਵੈਕਟਰ ਅਤੇ ਐਸੋਸੀਏਟਿਵ ਅਡਜੈਂਸੀ ਐਰੇ / SA ਚੇਰਨੋਹੋਵ। ਇੱਕ ਗ੍ਰਾਫ ਦੀ ਨੁਮਾਇੰਦਗੀ ਕਰਨ ਲਈ ਡੇਟਾ ਢਾਂਚੇ ਦੇ ਰੂਪ ਵਿੱਚ ਅਨੁਕੂਲਤਾ ਵੈਕਟਰ ਅਤੇ ਅਡਜੈਂਸੀ ਮੈਪ // ਅੰਤਰਰਾਸ਼ਟਰੀ ਵਿਗਿਆਨਕ ਅਤੇ ਪ੍ਰੈਕਟੀਕਲ ਕਾਨਫਰੰਸ ਦੇ ਲੇਖਾਂ ਦਾ ਸੰਗ੍ਰਹਿ "ਨਵੀਨਤਾਕਾਰੀ ਵਿਕਾਸ ਦੇ ਨਤੀਜਿਆਂ ਨੂੰ ਲਾਗੂ ਕਰਨ ਦੀਆਂ ਸਮੱਸਿਆਵਾਂ ਅਤੇ ਉਹਨਾਂ ਨੂੰ ਹੱਲ ਕਰਨ ਦੇ ਤਰੀਕੇ" (ਸਾਰਤੋਵ, ਸਤੰਬਰ 14.09.2019, 2019)। - ਸਟਰਲਿਟਾਮਕ: AMI, 65, p. 69-XNUMX
ਵਿਸ਼ੇ 'ਤੇ ਉਪਯੋਗੀ ਔਨਲਾਈਨ ਸਰੋਤ:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

ਸਰੋਤ: www.habr.com