ಗ್ರಾಫ್‌ಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಡೇಟಾ ರಚನೆಗಳು: ಅಸ್ತಿತ್ವದಲ್ಲಿರುವವುಗಳ ವಿಮರ್ಶೆ ಮತ್ತು ಎರಡು "ಬಹುತೇಕ ಹೊಸ"

ಎಲ್ಲರಿಗೂ ನಮಸ್ಕಾರ.

ಈ ಟಿಪ್ಪಣಿಯಲ್ಲಿ, ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ ಗ್ರಾಫ್‌ಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಬಳಸುವ ಮುಖ್ಯ ಡೇಟಾ ರಚನೆಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡಲು ನಾನು ನಿರ್ಧರಿಸಿದೆ ಮತ್ತು ನನಗೆ ಹೇಗಾದರೂ “ಸ್ಫಟಿಕೀಕರಿಸಿದ” ಅಂತಹ ಒಂದೆರಡು ರಚನೆಗಳ ಬಗ್ಗೆಯೂ ಮಾತನಾಡುತ್ತೇನೆ.

ಆದ್ದರಿಂದ, ಪ್ರಾರಂಭಿಸೋಣ. ಆದರೆ ಮೊದಲಿನಿಂದಲೂ ಅಲ್ಲ - ಗ್ರಾಫ್ ಎಂದರೇನು ಮತ್ತು ಅವು ಏನೆಂದು ನಮಗೆಲ್ಲರಿಗೂ ಈಗಾಗಲೇ ತಿಳಿದಿದೆ ಎಂದು ನಾನು ಭಾವಿಸುತ್ತೇನೆ (ನಿರ್ದೇಶನ, ನಿರ್ದೇಶಿತ, ತೂಕ, ತೂಕವಿಲ್ಲದ, ಬಹು ಅಂಚುಗಳು ಮತ್ತು ಕುಣಿಕೆಗಳೊಂದಿಗೆ ಅಥವಾ ಇಲ್ಲದೆ).

ಆದ್ದರಿಂದ, ಹೋಗೋಣ. "ಗ್ರಾಫ್ ಸಂಗ್ರಹಣೆ" ಗಾಗಿ ಡೇಟಾ ರಚನೆಗಳಿಗಾಗಿ ನಾವು ಯಾವ ಆಯ್ಕೆಗಳನ್ನು ಹೊಂದಿದ್ದೇವೆ?

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::multimap. ಸರಿ, "ಮ್ಯಾಟ್ರಿಕ್ಸ್" ರಚನೆಗಳಿಗಿಂತ ಕಡಿಮೆ ಮೆಮೊರಿಯನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಗ್ರಾಫ್‌ಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ರಚನೆಯನ್ನು ಹೊಂದಿದ್ದೇವೆ, ಬಹು ಲೂಪ್‌ಗಳು ಮತ್ತು ಅಂಚುಗಳೊಂದಿಗೆ ಗ್ರಾಫ್‌ಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು ಮತ್ತು ಶೃಂಗ ಸಂಖ್ಯೆಗಳ ಋಣಾತ್ಮಕವಲ್ಲದ ಕಟ್ಟುನಿಟ್ಟಾದ ಅವಶ್ಯಕತೆಗಳನ್ನು ಸಹ ಹೊಂದಿಲ್ಲ (ನನಗೆ ಗೊತ್ತಿಲ್ಲ ಯಾರಿಗೆ ಇದು ಬೇಕು, ಆದರೆ ಇನ್ನೂ).

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. ಕಾರ್ಮೆನ್, ಥಾಮಸ್ ಎಚ್., ಲೀಸರ್ಸನ್, ಚಾರ್ಲ್ಸ್ I., ರಿವೆಸ್ಟ್, ರೊನಾಲ್ಡ್ ಎಲ್., ಸ್ಟೀನ್, ಕ್ಲಿಫರ್ಡ್. ಕ್ರಮಾವಳಿಗಳು: ನಿರ್ಮಾಣ ಮತ್ತು ವಿಶ್ಲೇಷಣೆ, 2 ನೇ ಆವೃತ್ತಿ: ಟ್ರಾನ್ಸ್. ಇಂಗ್ಲೀಷ್ ನಿಂದ - ಎಂ.: ವಿಲಿಯಮ್ಸ್ ಪಬ್ಲಿಷಿಂಗ್ ಹೌಸ್, 2011.
2. ಹರಾರಿ ಫ್ರಾಂಕ್. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ. ಎಂ.: ಮೀರ್, 1973.
ಇದೇ ವೆಕ್ಟರ್ ಮತ್ತು ಅಸೋಸಿಯೇಟಿವ್ ಅರೇ ಅಡ್ಜೆಸೆನ್ಸಿಗಳ ಬಗ್ಗೆ ಲೇಖಕರ ವರದಿ:
3. ಚೆರ್ನೌಖೋವ್ ಎಸ್.ಎ. ಗ್ರಾಫ್‌ಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಮತ್ತು ಸಂಗ್ರಹಿಸುವ ವಿಧಾನಗಳಾಗಿ ಅಡ್ಜಸೆನ್ಸಿ ವೆಕ್ಟರ್ ಮತ್ತು ಅಸೋಸಿಯೇಟಿವ್ ಅಡ್ಜಸೆನ್ಸಿ ಅರೇ / ಎಸ್.ಎ. ಚೆರ್ನೌಹೋವ್. ಗ್ರಾಫ್ ಅನ್ನು ಪ್ರತಿನಿಧಿಸಲು ಡೇಟಾ ರಚನೆಗಳಾಗಿ ಪಕ್ಕದ ವೆಕ್ಟರ್ ಮತ್ತು ಪಕ್ಕದ ನಕ್ಷೆ // ಅಂತರಾಷ್ಟ್ರೀಯ ವೈಜ್ಞಾನಿಕ ಮತ್ತು ಪ್ರಾಯೋಗಿಕ ಸಮ್ಮೇಳನದ ಲೇಖನಗಳ ಸಂಗ್ರಹ "ನವೀನ ಬೆಳವಣಿಗೆಗಳ ಫಲಿತಾಂಶಗಳನ್ನು ಅನುಷ್ಠಾನಗೊಳಿಸುವ ಸಮಸ್ಯೆಗಳು ಮತ್ತು ಅವುಗಳನ್ನು ಪರಿಹರಿಸುವ ಮಾರ್ಗಗಳು" (ಸಾರಾಟೊವ್, ಸೆಪ್ಟೆಂಬರ್ 14.09.2019, 2019). - ಸ್ಟರ್ಲಿಟಮಾಕ್: AMI, 65, ಪು. 69-XNUMX
ವಿಷಯದ ಕುರಿತು ಉಪಯುಕ್ತ ಆನ್‌ಲೈನ್ ಮೂಲಗಳು:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

ಮೂಲ: www.habr.com