PythonnotJava.github.io/src/h5/sjjg/regraph.html at master · PythonnotJava/PythonnotJava.github.io

History

1721 lines (1592 loc) · 94.5 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744

745

746

747

748

749

750

751

752

753

754

755

756

757

758

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818

819

820

821

822

823

824

825

826

827

828

829

830

831

832

833

834

835

836

837

838

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

905

906

907

908

909

910

911

912

913

914

915

916

917

918

919

920

921

922

923

924

925

926

927

928

929

930

931

932

933

934

935

936

937

938

939

940

941

942

943

944

945

946

947

948

949

950

951

952

953

954

955

956

957

958

959

960

961

962

963

964

965

966

967

968

969

970

971

972

973

974

975

976

977

978

979

980

981

982

983

984

985

986

987

988

989

990

991

992

993

994

995

996

997

998

999

1000

<!DOCTYPE html>

<html>

<head>

<title>Regraph</title>

<style>

Arduino® Light Theme - Stefania Mellai <[email protected]>

.hljs {

display: block;

overflow-x: auto;

padding: 0.5em;

background: #FFFFFF;

}

.hljs,

.hljs-subst {

color: #434f54;

}

.hljs-keyword,

.hljs-attribute,

.hljs-selector-tag,

.hljs-doctag,

.hljs-name {

color: #00979D;

}

.hljs-built_in,

.hljs-literal,

.hljs-bullet,

.hljs-code,

.hljs-addition {

color: #D35400;

}

.hljs-regexp,

.hljs-symbol,

.hljs-variable,

.hljs-template-variable,

.hljs-link,

.hljs-selector-attr,

.hljs-selector-pseudo {

color: #00979D;

}

.hljs-type,

.hljs-string,

.hljs-selector-id,

.hljs-selector-class,

.hljs-quote,

.hljs-template-tag,

.hljs-deletion {

color: #005C5F;

}

.hljs-title,

.hljs-section {

color: #880000;

font-weight: bold;

}

.hljs-comment {

color: rgba(149,165,166,.8);

}

.hljs-meta-keyword {

color: #728E00;

}

.hljs-meta {

color: #434f54;

}

.hljs-emphasis {

font-style: italic;

}

.hljs-strong {

font-weight: bold;

}

.hljs-function {

color: #728E00;

}

.hljs-number {

color: #8A7B52;

}

</style>

<style>

/*---------------------------------------------------------------------------------------------

* Licensed under the MIT License. See License.txt in the project root for license information.

*--------------------------------------------------------------------------------------------*/

body {

font-family: "HelveticaNeue-Light", sans-serif, "宋体","Segoe WPC", "Segoe UI", "SFUIText-Light","Droid Sans Fallback";

font-size: 18px;

padding: 0 12px;

line-height: 1.6;

word-wrap: break-word;

color: #333333;

}

.content-wrapper{

max-width: 860px;

margin: 0 auto;

padding: 0 30px;

}

#code-csp-warning {

position: fixed;

top: 0;

right: 0;

color: white;

margin: 16px;

text-align: center;

font-size: 12px;

font-family: sans-serif;

background-color:#444444;

cursor: pointer;

padding: 6px;

box-shadow: 1px 1px 1px rgba(0,0,0,.25);

}

#code-csp-warning:hover {

text-decoration: none;

background-color:#007acc;

box-shadow: 2px 2px 2px rgba(0,0,0,.25);

}

body.scrollBeyondLastLine {

margin-bottom: calc(100vh - 22px);

}

body.showEditorSelection .code-line {

position: relative;

}

body.showEditorSelection .code-active-line:before,

body.showEditorSelection .code-line:hover:before {

content: "";

display: block;

position: absolute;

top: 0;

left: -12px;

height: 100%;

}

body.showEditorSelection li.code-active-line:before,

body.showEditorSelection li.code-line:hover:before {

left: -30px;

}

.vscode-light.showEditorSelection .code-active-line:before {

border-left: 3px solid rgba(0, 0, 0, 0.15);

}

.vscode-light.showEditorSelection .code-line:hover:before {

border-left: 3px solid rgba(0, 0, 0, 0.40);

}

.vscode-dark.showEditorSelection .code-active-line:before {

border-left: 3px solid rgba(255, 255, 255, 0.4);

}

.vscode-dark.showEditorSelection .code-line:hover:before {

border-left: 3px solid rgba(255, 255, 255, 0.60);

}

.vscode-high-contrast.showEditorSelection .code-active-line:before {

border-left: 3px solid rgba(255, 160, 0, 0.7);

}

.vscode-high-contrast.showEditorSelection .code-line:hover:before {

border-left: 3px solid rgba(255, 160, 0, 1);

}

img {

max-width: 100%;

max-height: 100%;

}

a {

color: #4080D0;

text-decoration: none;

}

a:focus,

input:focus,

select:focus,

textarea:focus {

outline: 1px solid -webkit-focus-ring-color;

outline-offset: -1px;

}

hr {

border: 0;

height: 2px;

border-bottom: 2px solid;

}

h1 {

padding-bottom: 0.3em;

line-height: 1.2;

border-bottom: 1px solid #eee;

}

h2{

padding-bottom: .3em;

font-size: 2em;

line-height: 1.225;

border-bottom: 1px solid #eee;

}

h3{

font-size: 1.75em;

line-height: 1.225;

}

h1, h2, h3 {

font-weight: bold;

}

h1 code,

h2 code,

h3 code,

h4 code,

h5 code,

h6 code {

font-size: inherit;

line-height: auto;

}

a:hover {

color: #4080D0;

text-decoration: underline;

}

table {

border-collapse: collapse;

}

table > thead > tr > th {

text-align: left;

border-bottom: 1px solid;

}

table > thead > tr > th,

table > thead > tr > td,

table > tbody > tr > th,

table > tbody > tr > td {

padding: 5px 10px;

}

table > tbody > tr + tr > td {

border-top: 1px solid;

}

blockquote {

margin: 0 7px 0 5px;

padding: 0 16px 0 10px;

border-left: 5px solid;

}

code {

font-family: Menlo, Monaco, Consolas, "Droid Sans Mono", "Courier New", monospace, "Droid Sans Fallback";

font-size: 14px;

line-height: 19px;

}

body.wordWrap pre {

white-space: pre-wrap;

}

.mac code {

font-size: 12px;

line-height: 18px;

}

pre:not(.hljs),

pre.hljs code > div {

padding: 16px;

border-radius: 3px;

overflow: auto;

}

/** Theming */

.vscode-light,

.vscode-light pre code {

color: rgb(30, 30, 30);

}

.vscode-dark,

.vscode-dark pre code {

color: #DDD;

}

.vscode-high-contrast,

.vscode-high-contrast pre code {

color: white;

}

.vscode-light code {

color: #A31515;

}

.vscode-dark code {

color: #D7BA7D;

}

.vscode-light pre:not(.hljs),

.vscode-light code > div {

background-color: rgba(220, 220, 220, 0.4);

}

.vscode-dark pre:not(.hljs),

.vscode-dark code > div {

background-color: rgba(10, 10, 10, 0.4);

}

.vscode-high-contrast pre:not(.hljs),

.vscode-high-contrast code > div {

background-color: rgb(0, 0, 0);

}

.vscode-high-contrast h1 {

border-color: rgb(0, 0, 0);

}

.vscode-light table > thead > tr > th {

border-color: rgba(0, 0, 0, 0.69);

}

.vscode-dark table > thead > tr > th {

border-color: rgba(255, 255, 255, 0.69);

}

.vscode-light h1,

.vscode-light hr,

.vscode-light table > tbody > tr + tr > td {

border-color: rgba(0, 0, 0, 0.18);

}

.vscode-dark h1,

.vscode-dark hr,

.vscode-dark table > tbody > tr + tr > td {

border-color: rgba(255, 255, 255, 0.18);

}

.vscode-light blockquote,

.vscode-dark blockquote {

background: rgba(127, 127, 127, 0.1);

border-color: rgba(0, 122, 204, 0.5);

}

.vscode-high-contrast blockquote {

background: transparent;

border-color: #fff;

}

</style>

<style>

pre {

background-color: #f8f8f8;

border: 1px solid #cccccc;

border-radius: 3px;

overflow-x: auto;

white-space: pre-wrap;

overflow-wrap: break-word;

}

pre:not(.hljs) {

padding: 23px;

line-height: 19px;

}

blockquote {

background: rgba(127, 127, 127, 0.1);

border-color: rgba(0, 122, 204, 0.5);

}

.emoji {

height: 1.4em;

}

/* for inline code */

:not(pre):not(.hljs) > code {

color: #C9AE75; /* Change the old color so it seems less like an error */

font-size: inherit;

}

/* Page Break : use <div class="page"/> to insert page break

-------------------------------------------------------- */

.page {

page-break-after: always;

}

.table-of-contents li{

list-style-type: initial;

}

</style>

<style>

@font-face{font-family:KaTeX_AMS;font-style:normal;font-weight:400;src:url(fonts/KaTeX_AMS-Regular.woff2) format("woff2"),url(fonts/KaTeX_AMS-Regular.woff) format("woff"),url(fonts/KaTeX_AMS-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Caligraphic;font-style:normal;font-weight:700;src:url(fonts/KaTeX_Caligraphic-Bold.woff2) format("woff2"),url(fonts/KaTeX_Caligraphic-Bold.woff) format("woff"),url(fonts/KaTeX_Caligraphic-Bold.ttf) format("truetype")}@font-face{font-family:KaTeX_Caligraphic;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Caligraphic-Regular.woff2) format("woff2"),url(fonts/KaTeX_Caligraphic-Regular.woff) format("woff"),url(fonts/KaTeX_Caligraphic-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Fraktur;font-style:normal;font-weight:700;src:url(fonts/KaTeX_Fraktur-Bold.woff2) format("woff2"),url(fonts/KaTeX_Fraktur-Bold.woff) format("woff"),url(fonts/KaTeX_Fraktur-Bold.ttf) format("truetype")}@font-face{font-family:KaTeX_Fraktur;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Fraktur-Regular.woff2) format("woff2"),url(fonts/KaTeX_Fraktur-Regular.woff) format("woff"),url(fonts/KaTeX_Fraktur-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Main;font-style:normal;font-weight:700;src:url(fonts/KaTeX_Main-Bold.woff2) format("woff2"),url(fonts/KaTeX_Main-Bold.woff) format("woff"),url(fonts/KaTeX_Main-Bold.ttf) format("truetype")}@font-face{font-family:KaTeX_Main;font-style:italic;font-weight:700;src:url(fonts/KaTeX_Main-BoldItalic.woff2) format("woff2"),url(fonts/KaTeX_Main-BoldItalic.woff) format("woff"),url(fonts/KaTeX_Main-BoldItalic.ttf) format("truetype")}@font-face{font-family:KaTeX_Main;font-style:italic;font-weight:400;src:url(fonts/KaTeX_Main-Italic.woff2) format("woff2"),url(fonts/KaTeX_Main-Italic.woff) format("woff"),url(fonts/KaTeX_Main-Italic.ttf) format("truetype")}@font-face{font-family:KaTeX_Main;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Main-Regular.woff2) format("woff2"),url(fonts/KaTeX_Main-Regular.woff) format("woff"),url(fonts/KaTeX_Main-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Math;font-style:italic;font-weight:700;src:url(fonts/KaTeX_Math-BoldItalic.woff2) format("woff2"),url(fonts/KaTeX_Math-BoldItalic.woff) format("woff"),url(fonts/KaTeX_Math-BoldItalic.ttf) format("truetype")}@font-face{font-family:KaTeX_Math;font-style:italic;font-weight:400;src:url(fonts/KaTeX_Math-Italic.woff2) format("woff2"),url(fonts/KaTeX_Math-Italic.woff) format("woff"),url(fonts/KaTeX_Math-Italic.ttf) format("truetype")}@font-face{font-family:"KaTeX_SansSerif";font-style:normal;font-weight:700;src:url(fonts/KaTeX_SansSerif-Bold.woff2) format("woff2"),url(fonts/KaTeX_SansSerif-Bold.woff) format("woff"),url(fonts/KaTeX_SansSerif-Bold.ttf) format("truetype")}@font-face{font-family:"KaTeX_SansSerif";font-style:italic;font-weight:400;src:url(fonts/KaTeX_SansSerif-Italic.woff2) format("woff2"),url(fonts/KaTeX_SansSerif-Italic.woff) format("woff"),url(fonts/KaTeX_SansSerif-Italic.ttf) format("truetype")}@font-face{font-family:"KaTeX_SansSerif";font-style:normal;font-weight:400;src:url(fonts/KaTeX_SansSerif-Regular.woff2) format("woff2"),url(fonts/KaTeX_SansSerif-Regular.woff) format("woff"),url(fonts/KaTeX_SansSerif-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Script;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Script-Regular.woff2) format("woff2"),url(fonts/KaTeX_Script-Regular.woff) format("woff"),url(fonts/KaTeX_Script-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Size1;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Size1-Regular.woff2) format("woff2"),url(fonts/KaTeX_Size1-Regular.woff) format("woff"),url(fonts/KaTeX_Size1-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Size2;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Size2-Regular.woff2) format("woff2"),url(fonts/KaTeX_Size2-Regular.woff) format("woff"),url(fonts/KaTeX_Size2-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Size3;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Size3-Regular.woff2) format("woff2"),url(fonts/KaTeX_Size3-Regular.woff) format("woff"),url(fonts/KaTeX_Size3-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Size4;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Size4-Regular.woff2) format("woff2"),url(fonts/KaTeX_Size4-Regular.woff) format("woff"),url(fonts/KaTeX_Size4-Regular.ttf) format("truetype")}@font-face{font-family:KaTeX_Typewriter;font-style:normal;font-weight:400;src:url(fonts/KaTeX_Typewriter-Regular.woff2) format("woff2"),url(fonts/KaTeX_Typewriter-Regular.woff) format("woff"),url(fonts/KaTeX_Typewriter-Regular.ttf) format("truetype")}.katex{text-rendering:auto;font:normal 1.21em KaTeX_Main,Times New Roman,serif;line-height:1.2;text-indent:0}.katex *{-ms-high-contrast-adjust:none!important;border-color:currentColor}.katex .katex-version:after{content:"0.16.2"}.katex .katex-mathml{clip:rect(1px,1px,1px,1px);border:0;height:1px;overflow:hidden;padding:0;position:absolute;width:1px}.katex .katex-html>.newline{display:block}.katex .base{position:relative;white-space:nowrap;width:-webkit-min-content;width:-moz-min-content;width:min-content}.katex .base,.katex .strut{display:inline-block}.katex .textbf{font-weight:700}.katex .textit{font-style:italic}.katex .textrm{font-family:KaTeX_Main}.katex .textsf{font-family:KaTeX_SansSerif}.katex .texttt{font-family:KaTeX_Typewriter}.katex .mathnormal{font-family:KaTeX_Math;font-style:italic}.katex .mathit{font-family:KaTeX_Main;font-style:italic}.katex .mathrm{font-style:normal}.katex .mathbf{font-family:KaTeX_Main;font-weight:700}.katex .boldsymbol{font-family:KaTeX_Math;font-style:italic;font-weight:700}.katex .amsrm,.katex .mathbb,.katex .textbb{font-family:KaTeX_AMS}.katex .mathcal{font-family:KaTeX_Caligraphic}.katex .mathfrak,.katex .textfrak{font-family:KaTeX_Fraktur}.katex .mathtt{font-family:KaTeX_Typewriter}.katex .mathscr,.katex .textscr{font-family:KaTeX_Script}.katex .mathsf,.katex .textsf{font-family:KaTeX_SansSerif}.katex .mathboldsf,.katex .textboldsf{font-family:KaTeX_SansSerif;font-weight:700}.katex .mathitsf,.katex .textitsf{font-family:KaTeX_SansSerif;font-style:italic}.katex .mainrm{font-family:KaTeX_Main;font-style:normal}.katex .vlist-t{border-collapse:collapse;display:inline-table;table-layout:fixed}.katex .vlist-r{display:table-row}.katex .vlist{display:table-cell;position:relative;vertical-align:bottom}.katex .vlist>span{display:block;height:0;position:relative}.katex .vlist>span>span{display:inline-block}.katex .vlist>span>.pstrut{overflow:hidden;width:0}.katex .vlist-t2{margin-right:-2px}.katex .vlist-s{display:table-cell;font-size:1px;min-width:2px;vertical-align:bottom;width:2px}.katex .vbox{align-items:baseline;display:inline-flex;flex-direction:column}.katex .hbox{width:100%}.katex .hbox,.katex .thinbox{display:inline-flex;flex-direction:row}.katex .thinbox{max-width:0;width:0}.katex .msupsub{text-align:left}.katex .mfrac>span>span{text-align:center}.katex .mfrac .frac-line{border-bottom-style:solid;display:inline-block;width:100%}.katex .hdashline,.katex .hline,.katex .mfrac .frac-line,.katex .overline .overline-line,.katex .rule,.katex .underline .underline-line{min-height:1px}.katex .mspace{display:inline-block}.katex .clap,.katex .llap,.katex .rlap{position:relative;width:0}.katex .clap>.inner,.katex .llap>.inner,.katex .rlap>.inner{position:absolute}.katex .clap>.fix,.katex .llap>.fix,.katex .rlap>.fix{display:inline-block}.katex .llap>.inner{right:0}.katex .clap>.inner,.katex .rlap>.inner{left:0}.katex .clap>.inner>span{margin-left:-50%;margin-right:50%}.katex .rule{border:0 solid;display:inline-block;position:relative}.katex .hline,.katex .overline .overline-line,.katex .underline .underline-line{border-bottom-style:solid;display:inline-block;width:100%}.katex .hdashline{border-bottom-style:dashed;display:inline-block;width:100%}.katex .sqrt>.root{margin-left:.27777778em;margin-right:-.55555556em}.katex .fontsize-ensurer.reset-size1.size1,.katex .sizing.reset-size1.size1{font-size:1em}.katex .fontsize-ensurer.reset-size1.size2,.katex .sizing.reset-size1.size2{font-size:1.2em}.katex .fontsize-ensurer.reset-size1.size3,.katex .sizing.reset-size1.size3{font-size:1.4em}.katex .fontsize-ensurer.reset-size1.size4,.katex .sizing.reset-size1.size4{font-size:1.6em}.katex .fontsize-ensurer.reset-size1.size5,.katex .sizing.reset-size1.size5{font-size:1.8em}.katex .fontsize-ensurer.reset-size1.size6,.katex .sizing.reset-size1.size6{font-size:2em}.katex .fontsize-ensurer.reset-size1.size7,.katex .sizing.reset-size1.size7{font-size:2.4em}.katex .fontsize-ensurer.reset-size1.size8,.katex .sizing.reset-size1.size8{font-size:2.88em}.katex .fontsize-ensurer.reset-size1.size9,.katex .sizing.reset-size1.size9{font-size:3.456em}.katex .fontsize-ensurer.reset-size1.size10,.katex .sizing.reset-size1.size10{font-size:4.148em}.katex .fontsize-ensurer.reset-size1.size11,.katex .sizing.reset-size1.size11{font-size:4.976em}.katex .fontsize-ensurer.reset-size2.size1,.katex .sizing.reset-size2.size1{font-size:.83333333em}.katex .fontsize-ensurer.reset-size2.size2,.katex .sizing.reset-size2.size2{font-size:1em}.katex .fontsize-ensurer.reset-size2.size3,.katex .sizing.reset-size2.size3{font-size:1.16666667em}.katex .fontsize-ensurer.reset-size2.size4,.katex .sizing.reset-size2.size4{font-size:1.33333333em}.katex .fontsize-ensurer.reset-size2.size5,.katex .sizing.reset-size2.size5{font-size:1.5em}.katex .fontsize-ensurer.reset-size2.size6,.katex .sizing.reset-size2.size6{font-size:1.66666667em}.katex .fontsize-ensurer.reset-size2.size7,.katex .sizing.reset-size2.size7{font-size:2em}.katex .fontsize-ensurer.reset-size2.size8,.katex .sizing.reset-size2.size8{font-size:2.4em}.katex .fontsize-ensurer.reset-size2.size9,.katex .sizing.reset-size2.size9{font-size:2.88em}.katex .fontsize-ensurer.reset-size2.size10,.katex .sizing.reset-size2.size10{font-size:3.45666667em}.katex .fontsize-ensurer.reset-size2.size11,.katex .sizing.reset-size2.size11{font-size:4.14666667em}.katex .fontsize-ensurer.reset-size3.size1,.katex .sizing.reset-size3.size1{font-size:.71428571em}.katex .fontsize-ensurer.reset-size3.size2,.katex .sizing.reset-size3.size2{font-size:.85714286em}.katex .fontsize-ensurer.reset-size3.size3,.katex .sizing.reset-size3.size3{font-size:1em}.katex .fontsize-ensurer.reset-size3.size4,.katex .sizing.reset-size3.size4{font-size:1.14285714em}.katex .fontsize-ensurer.reset-size3.size5,.katex .sizing.reset-size3.size5{font-size:1.28571429em}.katex .fontsize-ensurer.reset-size3.size6,.katex .sizing.reset-size3.size6{font-size:1.42857143em}.katex .fontsize-ensurer.reset-size3.size7,.katex .sizing.reset-size3.size7{font-size:1.71428571em}.katex .fontsize-ensurer.reset-size3.size8,.katex .sizing.reset-size3.size8{font-size:2.05714286em}.katex .fontsize-ensurer.reset-size3.size9,.katex .sizing.reset-size3.size9{font-size:2.46857143em}.katex .fontsize-ensurer.reset-size3.size10,.katex .sizing.reset-size3.size10{font-size:2.96285714em}.katex .fontsize-ensurer.reset-size3.size11,.katex .sizing.reset-size3.size11{font-size:3.55428571em}.katex .fontsize-ensurer.reset-size4.size1,.katex .sizing.reset-size4.size1{font-size:.625em}.katex .fontsize-ensurer.reset-size4.size2,.katex .sizing.reset-size4.size2{font-size:.75em}.katex .fontsize-ensurer.reset-size4.size3,.katex .sizing.reset-size4.size3{font-size:.875em}.katex .fontsize-ensurer.reset-size4.size4,.katex .sizing.reset-size4.size4{font-size:1em}.katex .fontsize-ensurer.reset-size4.size5,.katex .sizing.reset-size4.size5{font-size:1.125em}.katex .fontsize-ensurer.reset-size4.size6,.katex .sizing.reset-size4.size6{font-size:1.25em}.katex .fontsize-ensurer.reset-size4.size7,.katex .sizing.reset-size4.size7{font-size:1.5em}.katex .fontsize-ensurer.reset-size4.size8,.katex .sizing.reset-size4.size8{font-size:1.8em}.katex .fontsize-ensurer.reset-size4.size9,.katex .sizing.reset-size4.size9{font-size:2.16em}.katex .fontsize-ensurer.reset-size4.size10,.katex .sizing.reset-size4.size10{font-size:2.5925em}.katex .fontsize-ensurer.reset-size4.size11,.katex .sizing.reset-size4.size11{font-size:3.11em}.katex .fontsize-ensurer.reset-size5.size1,.katex .sizing.reset-size5.size1{font-size:.55555556em}.katex .fontsize-ensurer.reset-size5.size2,.katex .sizing.reset-size5.size2{font-size:.66666667em}.katex .fontsize-ensurer.reset-size5.size3,.katex .sizing.reset-size5.size3{font-size:.77777778em}.katex .fontsize-ensurer.reset-size5.size4,.katex .sizing.reset-size5.size4{font-size:.88888889em}.katex .fontsize-ensurer.reset-size5.size5,.katex .sizing.reset-size5.size5{font-size:1em}.katex .fontsize-ensurer.reset-size5.size6,.katex .sizing.reset-size5.size6{font-size:1.11111111em}.katex .fontsize-ensurer.reset-size5.size7,.katex .sizing.reset-size5.size7{font-size:1.33333333em}.katex .fontsize-ensurer.reset-size5.size8,.katex .sizing.reset-size5.size8{font-size:1.6em}.katex .fontsize-ensurer.reset-size5.size9,.katex .sizing.reset-size5.size9{font-size:1.92em}.katex .fontsize-ensurer.reset-size5.size10,.katex .sizing.reset-size5.size10{font-size:2.30444444em}.katex .fontsize-ensurer.reset-size5.size11,.katex .sizing.reset-size5.size11{font-size:2.76444444em}.katex .fontsize-ensurer.reset-size6.size1,.katex .sizing.reset-size6.size1{font-size:.5em}.katex .fontsize-ensurer.reset-size6.size2,.katex .sizing.reset-size6.size2{font-size:.6em}.katex .fontsize-ensurer.reset-size6.size3,.katex .sizing.reset-size6.size3{font-size:.7em}.katex .fontsize-ensurer.reset-size6.size4,.katex .sizing.reset-size6.size4{font-size:.8em}.katex .fontsize-ensurer.reset-size6.size5,.katex .sizing.reset-size6.size5{font-size:.9em}.katex .fontsize-ensurer.reset-size6.size6,.katex .sizing.reset-size6.size6{font-size:1em}.katex .fontsize-ensurer.reset-size6.size7,.katex .sizing.reset-size6.size7{font-size:1.2em}.katex .fontsize-ensurer.reset-size6.size8,.katex .sizing.reset-size6.size8{font-size:1.44em}.katex .fontsize-ensurer.reset-size6.size9,.katex .sizing.reset-size6.size9{font-size:1.728em}.katex .fontsize-ensurer.reset-size6.size10,.katex .sizing.reset-size6.size10{font-size:2.074em}.katex .fontsize-ensurer.reset-size6.size11,.katex .sizing.reset-size6.size11{font-size:2.488em}.katex .fontsize-ensurer.reset-size7.size1,.katex .sizing.reset-size7.size1{font-size:.41666667em}.katex .fontsize-ensurer.reset-size7.size2,.katex .sizing.reset-size7.size2{font-size:.5em}.katex .fontsize-ensurer.reset-size7.size3,.katex .sizing.reset-size7.size3{font-size:.58333333em}.katex .fontsize-ensurer.reset-size7.size4,.katex .sizing.reset-size7.size4{font-size:.66666667em}.katex .fontsize-ensurer.reset-size7.size5,.katex .sizing.reset-size7.size5{font-size:.75em}.katex .fontsize-ensurer.reset-size7.size6,.katex .sizing.reset-size7.size6{font-size:.83333333em}.katex .fontsize-ensurer.reset-size7.size7,.katex .sizing.reset-size7.size7{font-size:1em}.katex .fontsize-ensurer.reset-size7.size8,.katex .sizing.reset-size7.size8{font-size:1.2em}.katex .fontsize-ensurer.reset-size7.size9,.katex .sizing.reset-size7.size9{font-size:1.44em}.katex .fontsize-ensurer.reset-size7.size10,.katex .sizing.reset-size7.size10{font-size:1.72833333em}.katex .fontsize-ensurer.reset-size7.size11,.katex .sizing.reset-size7.size11{font-size:2.07333333em}.katex .fontsize-ensurer.reset-size8.size1,.katex .sizing.reset-size8.size1{font-size:.34722222em}.katex .fontsize-ensurer.reset-size8.size2,.katex .sizing.reset-size8.size2{font-size:.41666667em}.katex .fontsize-ensurer.reset-size8.size3,.katex .sizing.reset-size8.size3{font-size:.48611111em}.katex .fontsize-ensurer.reset-size8.size4,.katex .sizing.reset-size8.size4{font-size:.55555556em}.katex .fontsize-ensurer.reset-size8.size5,.katex .sizing.reset-size8.size5{font-size:.625em}.katex .fontsize-ensurer.reset-size8.size6,.katex .sizing.reset-size8.size6{font-size:.69444444em}.katex .fontsize-ensurer.reset-size8.size7,.katex .sizing.reset-size8.size7{font-size:.83333333em}.katex .fontsize-ensurer.reset-size8.size8,.katex .sizing.reset-size8.size8{font-size:1em}.katex .fontsize-ensurer.reset-size8.size9,.katex .sizing.reset-size8.size9{font-size:1.2em}.katex .fontsize-ensurer.reset-size8.size10,.katex .sizing.reset-size8.size10{font-size:1.44027778em}.katex .fontsize-ensurer.reset-size8.size11,.katex .sizing.reset-size8.size11{font-size:1.72777778em}.katex .fontsize-ensurer.reset-size9.size1,.katex .sizing.reset-size9.size1{font-size:.28935185em}.katex .fontsize-ensurer.reset-size9.size2,.katex .sizing.reset-size9.size2{font-size:.34722222em}.katex .fontsize-ensurer.reset-size9.size3,.katex .sizing.reset-size9.size3{font-size:.40509259em}.katex .fontsize-ensurer.reset-size9.size4,.katex .sizing.reset-size9.size4{font-size:.46296296em}.katex .fontsize-ensurer.reset-size9.size5,.katex .sizing.reset-size9.size5{font-size:.52083333em}.katex .fontsize-ensurer.reset-size9.size6,.katex .sizing.reset-size9.size6{font-size:.5787037em}.katex .fontsize-ensurer.reset-size9.size7,.katex .sizing.reset-size9.size7{font-size:.69444444em}.katex .fontsize-ensurer.reset-size9.size8,.katex .sizing.reset-size9.size8{font-size:.83333333em}.katex .fontsize-ensurer.reset-size9.size9,.katex .sizing.reset-size9.size9{font-size:1em}.katex .fontsize-ensurer.reset-size9.size10,.katex .sizing.reset-size9.size10{font-size:1.20023148em}.katex .fontsize-ensurer.reset-size9.size11,.katex .sizing.reset-size9.size11{font-size:1.43981481em}.katex .fontsize-ensurer.reset-size10.size1,.katex .sizing.reset-size10.size1{font-size:.24108004em}.katex .fontsize-ensurer.reset-size10.size2,.katex .sizing.reset-size10.size2{font-size:.28929605em}.katex .fontsize-ensurer.reset-size10.size3,.katex .sizing.reset-size10.size3{font-size:.33751205em}.katex .fontsize-ensurer.reset-size10.size4,.katex .sizing.reset-size10.size4{font-size:.38572806em}.katex .fontsize-ensurer.reset-size10.size5,.katex .sizing.reset-size10.size5{font-size:.43394407em}.katex .fontsize-ensurer.reset-size10.size6,.katex .sizing.reset-size10.size6{font-size:.48216008em}.katex .fontsize-ensurer.reset-size10.size7,.katex .sizing.reset-size10.size7{font-size:.57859209em}.katex .fontsize-ensurer.reset-size10.size8,.katex .sizing.reset-size10.size8{font-size:.69431051em}.katex .fontsize-ensurer.reset-size10.size9,.katex .sizing.reset-size10.size9{font-size:.83317261em}.katex .fontsize-ensurer.reset-size10.size10,.katex .sizing.reset-size10.size10{font-size:1em}.katex .fontsize-ensurer.reset-size10.size11,.katex .sizing.reset-size10.size11{font-size:1.19961427em}.katex .fontsize-ensurer.reset-size11.size1,.katex .sizing.reset-size11.size1{font-size:.20096463em}.katex .fontsize-ensurer.reset-size11.size2,.katex .sizing.reset-size11.size2{font-size:.24115756em}.katex .fontsize-ensurer.reset-size11.size3,.katex .sizing.reset-size11.size3{font-size:.28135048em}.katex .fontsize-ensurer.reset-size11.size4,.katex .sizing.reset-size11.size4{font-size:.32154341em}.katex .fontsize-ensurer.reset-size11.size5,.katex .sizing.reset-size11.size5{font-size:.36173633em}.katex .fontsize-ensurer.reset-size11.size6,.katex .sizing.reset-size11.size6{font-size:.40192926em}.katex .fontsize-ensurer.reset-size11.size7,.katex .sizing.reset-size11.size7{font-size:.48231511em}.katex .fontsize-ensurer.reset-size11.size8,.katex .sizing.reset-size11.size8{font-size:.57877814em}.katex .fontsize-ensurer.reset-size11.size9,.katex .sizing.reset-size11.size9{font-size:.69453376em}.katex .fontsize-ensurer.reset-size11.size10,.katex .sizing.reset-size11.size10{font-size:.83360129em}.katex .fontsize-ensurer.reset-size11.size11,.katex .sizing.reset-size11.size11{font-size:1em}.katex .delimsizing.size1{font-family:KaTeX_Size1}.katex .delimsizing.size2{font-family:KaTeX_Size2}.katex .delimsizing.size3{font-family:KaTeX_Size3}.katex .delimsizing.size4{font-family:KaTeX_Size4}.katex .delimsizing.mult .delim-size1>span{font-family:KaTeX_Size1}.katex .delimsizing.mult .delim-size4>span{font-family:KaTeX_Size4}.katex .nulldelimiter{display:inline-block;width:.12em}.katex .delimcenter,.katex .op-symbol{position:relative}.katex .op-symbol.small-op{font-family:KaTeX_Size1}.katex .op-symbol.large-op{font-family:KaTeX_Size2}.katex .accent>.vlist-t,.katex .op-limits>.vlist-t{text-align:center}.katex .accent .accent-body{position:relative}.katex .accent .accent-body:not(.accent-full){width:0}.katex .overlay{display:block}.katex .mtable .vertical-separator{display:inline-block;min-width:1px}.katex .mtable .arraycolsep{display:inline-block}.katex .mtable .col-align-c>.vlist-t{text-align:center}.katex .mtable .col-align-l>.vlist-t{text-align:left}.katex .mtable .col-align-r>.vlist-t{text-align:right}.katex .svg-align{text-align:left}.katex svg{fill:currentColor;stroke:currentColor;fill-rule:nonzero;fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;display:block;height:inherit;position:absolute;width:100%}.katex svg path{stroke:none}.katex img{border-style:none;max-height:none;max-width:none;min-height:0;min-width:0}.katex .stretchy{display:block;overflow:hidden;position:relative;width:100%}.katex .stretchy:after,.katex .stretchy:before{content:""}.katex .hide-tail{overflow:hidden;position:relative;width:100%}.katex .halfarrow-left{left:0;overflow:hidden;position:absolute;width:50.2%}.katex .halfarrow-right{overflow:hidden;position:absolute;right:0;width:50.2%}.katex .brace-left{left:0;overflow:hidden;position:absolute;width:25.1%}.katex .brace-center{left:25%;overflow:hidden;position:absolute;width:50%}.katex .brace-right{overflow:hidden;position:absolute;right:0;width:25.1%}.katex .x-arrow-pad{padding:0 .5em}.katex .cd-arrow-pad{padding:0 .55556em 0 .27778em}.katex .mover,.katex .munder,.katex .x-arrow{text-align:center}.katex .boxpad{padding:0 .3em}.katex .fbox,.katex .fcolorbox{border:.04em solid;box-sizing:border-box}.katex .cancel-pad{padding:0 .2em}.katex .cancel-lap{margin-left:-.2em;margin-right:-.2em}.katex .sout{border-bottom-style:solid;border-bottom-width:.08em}.katex .angl{border-right:.049em solid;border-top:.049em solid;box-sizing:border-box;margin-right:.03889em}.katex .anglpad{padding:0 .03889em}.katex .eqn-num:before{content:"(" counter(katexEqnNo) ")";counter-increment:katexEqnNo}.katex .mml-eqn-num:before{content:"(" counter(mmlEqnNo) ")";counter-increment:mmlEqnNo}.katex .mtr-glue{width:50%}.katex .cd-vert-arrow{display:inline-block;position:relative}.katex .cd-label-left{display:inline-block;position:absolute;right:calc(50% + .3em);text-align:left}.katex .cd-label-right{display:inline-block;left:calc(50% + .3em);position:absolute;text-align:right}.katex-display{display:block;margin:1em 0;text-align:center}.katex-display>.katex{display:block;text-align:center;white-space:nowrap}.katex-display>.katex>.katex-html{display:block;position:relative}.katex-display>.katex>.katex-html>.tag{position:absolute;right:0}.katex-display.leqno>.katex>.katex-html>.tag{left:0;right:auto}.katex-display.fleqn>.katex{padding-left:2em;text-align:left}body{counter-reset:katexEqnNo mmlEqnNo}

</style>

</head>

<body>

<ul>

<li>V：顶点（数据元素）组成的有穷非空集合</li>

<li>{E}：边的有穷集合、</li>

<li>图的逻辑结构：多对多</li>

</ul>

<ul>

<li>

无向图：每条边都是无方向的，如下图1

</li>

<li>

有向图：每条边都是有方向的，如下图2

</li>

<li>

完全图：任意两个顶点都有边相连，分为无向完全图、有向完全图，如下图3、4

</li>

<li>

稀疏图：有很少边或者弧的图(e < n * log(2, n))

</li>

<li>

弧：带有方向的边也叫弧

</li>

<li>

稠密图：有较多的边或者弧的图

</li>

<li>

网：边或者弧带有权值的图

</li>

<li>

邻接：两个顶点被边或者弧相连称为邻接，无向图中使用(vi, vj)表示vi与vj互为邻接点；有向图中使用<vi, vj>，表示vi邻接到vj，vj邻接于vi

</li>

<li>

关联（依附）：边或者弧与顶点之间的关系，说白了就是这条边或者弧就是某两个顶点连一起得到的，这个关系就是关联

</li>

<li>

顶点的度：与顶点关联的边的数目；在有向图中，顶点的度等于顶点的出度和入度之和

</li>

<li>

入度：以当前顶点为终点的有向边的条数，图二中A的入度为2

</li>

<li>

出度：以当前顶点为起点的有向边的条数，图二中A的出度为1

</li>

<li>

有向树：仅有一个顶点入度为0，其余顶点的入度为1的有向图被称为有向树

</li>

<li>

路径：接续的边（不间断的边边相连）构成的顶点序列

</li>

<li>

路径长度：网的某路径的权值之和

</li>

<li>

回路（环）：第一个顶点和最后一个顶点具有相同的路径

</li>

<li>

简单路径：除了起点和终点是一样的，其他顶点均不同的路径

</li>

<li>

简单回路（简单环）：除了路径的起点和终点一样外，其余的顶点均不相同的路径

</li>

<li>

连通图（强连通图）：在无（有）向图G = (V, {E})中，若对任何两个顶点v、都存在从v到u的路径，则称G是连通图，图2就不是强连通图，因为A到D有路径，但是不存在D到A的路径

</li>

<li>

权：就是网的边上的权值

</li>

<li>

子图：G = (V, {E})，G1 = (V1, {E1})，若V1∈V，E1∈E，则称G1是G的子图

</li>

<li>

连通分量（强连通分量）：无向图G的极大连通子图称为G的连通分量

</li>

<li>

极大连通子图：该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不在连通

</li>

<li>

强连通分量：有向图G的极大连通子图称为G的强连通分量

</li>

<li>

极大强连通子图：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不在是强连通

</li>

<li>

极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边就不再连通

</li>

<li>

生成树：包含无向图G所有顶点的极小连通子图

</li>

<li>

生成森林：对非连通图，由各个连通分量的生成树的集合

</li>

</ul>

<h2 id="%E5%9B%BE%E7%9A%84%E9%87%8D%E8%A6%81%E6%93%8D%E4%BD%9C" tabindex="-1">图的重要操作</h2>

<pre class='hljs'><code><div>CreateGraph(&G, V, VR)

初始条件：V是图的顶点集，VR是图中弧的集合

操作结果：按V和VR的定义构造图G

</div></code></pre>

<h3 id="dfs%EF%BC%88%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86%EF%BC%89" tabindex="-1">DFS（深度优先遍历）</h3>

<pre class='hljs'><code><div>DFSTraverse(G)

初始条件：图存在

操作结果：对图进行深度优先遍历

</div></code></pre>

<h3 id="bfs%EF%BC%88%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86%EF%BC%89" tabindex="-1">BFS（广度优先遍历）</h3>

<pre class='hljs'><code><div>BFSTraverse(G)

初始条件：图G存在

操作结果：对图进行广度优先遍历

</div></code></pre>

<h2 id="%E5%9B%BE%E7%9A%84%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" tabindex="-1">图的存储结构</h2>

<ul>

<li>借助二维数组表示，称为数组表示法（邻接矩阵）</li>

<li>链式存储结构：使用多重链表（如邻接表、连接多重表、十字链表）</li>

</ul>

<h2 id="%E6%97%A0%E5%90%91%E5%9B%BE%E7%9A%84%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E8%A1%A8%E7%A4%BA%E6%B3%95" tabindex="-1">无向图的邻接矩阵表示法</h2>

<ul>

<li>建立一个顶点表（记录顶点信息）和一个邻接矩阵（顶点之间的关系）</li>

<li>用一维数组表示顶点表</li>

<li>邻接矩阵用二维数组，用1表示两点之间有边或者弧；用0表示两点之间不存在有边或者弧；默认顶点与自身为0

</ul>

上图的邻接矩阵为

<table>

<thead>

<tr>

</tr>

</thead>

<tbody>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</tbody>

</table>

</blockquote>

<ul>

<li>无向图的邻接矩阵是一个对称矩阵</li>

<li>顶点i的度是第i行或者列的1的个数</li>

</ul>

<h2 id="%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E8%A1%A8%E7%A4%BA%E6%B3%95" tabindex="-1">有向图的邻接矩阵表示法</h2>

<ul>

<li>vi到vj的弧记录为1，不存在的话记录0

</ul>

上图的邻接矩阵为

<table>

<thead>

<tr>

</tr>

</thead>

<tbody>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</tbody>

</table>

</blockquote>

<h2 id="%E7%BD%91%E7%9A%84%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E8%A1%A8%E7%A4%BA%E6%B3%95" tabindex="-1">网的邻接矩阵表示法</h2>

<ul>

<li>

如果两点之间存在边或者弧（因为网也分为有向网和无向网），则记录值，否则记录一个特殊数，比如说0，-1

上图的邻接矩阵为

</li>

</ul>

<table>

<thead>

<tr>

</tr>

</thead>

<tbody>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</tbody>

</table>

</blockquote>

<h2 id="%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E8%A1%A8%E7%A4%BA%E6%B3%95" tabindex="-1">代码实现邻接矩阵表示法</h2>

<pre class='hljs'><code><div>// 邻接矩阵存储法的思想是基于两个数组分别存储顶点（一维）和邻接矩阵（二维）

typedef char VertexType; // 顶点类型

typedef int ArcType; // 边的权值的类型

#define MAXSIZE 10 // 最大顶点数目

typedef struct {

VertexType vertex[MAXSIZE];

ArcType arcs[MAXSIZE][MAXSIZE];

// 记录当前顶点数、边数

int vernum, arcnum;

} AMGraph;

</div></code></pre>

<h2 id="%E5%AE%9E%E7%8E%B0%E6%97%A0%E5%90%91%E7%BD%91%E7%9A%84%E8%A1%A8%E7%A4%BA" tabindex="-1">实现无向网的表示</h2>

<ul>

<li>输入顶点数和边数</li>

<li>把顶点添加到顶点表</li>

<li>初始化邻接矩阵，默认权值全是0值（就是你设定的不存在的值）</li>

<li>构造邻接矩阵</li>

</ul>

<h2 id="%E4%BD%BF%E7%94%A8%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9" tabindex="-1">使用邻接矩阵的优缺点</h2>

<ul>

<li>方便检查任意对顶点是否存在关联</li>

<li>便于计算顶点的度</li>

</ul>

<ul>

<li>不便于删除和增加新顶点</li>

<li>边太少时，仍是一个是一个nxn（n是顶点个数）稀疏矩阵，浪费空间</li>

<li>统计稀疏图边数浪费时间</li>

</ul>

<pre class='hljs'><code><div>// 用于表示存在关联的两个顶点以权值

typedef struct {

VertexType vertex1;

VertexType vertex2;

ArcType weight;

} Linked;

// 辅助函数，用于获取顶点在顶点集的索引

int getIndex(AMGraph *graph, VertexType name);

// 建立无向网

// 参数依次是边的顶点个数、边的个数、网、顶点集、关联数组集

void create(int _vernum, int _arcnum, AMGraph *graph, VertexType vertexes[_vernum], Linked linked[_arcnum]);

// 直观的打印出邻接矩阵

void printMatrix(AMGraph *graph);

</div></code></pre>

<pre class='hljs'><code><div>//

// Created by 20281 on 2023/6/11.

//

#include "AdjacencyMatrix.h"

#include "stdio.h"

int getIndex(AMGraph *graph, VertexType name){

for (int i=0;i<graph->vernum;i++){

if (graph->vertex[i] == name) return i;

else continue;

}

return -1;

}

graph->vernum = _vernum;

graph->arcnum = _arcnum;

for (int i=0;i<_vernum;i++){

graph->vertex[i] = vertexes[i];

}

for (int i=0;i<_vernum;i++){

for (int j=0;j<_vernum;j++){

graph->arcs[i][j] = 0;

}

for (int i=0;i<_arcnum;i++){

int ver1 = getIndex(graph, linked[i].vertex1);

int ver2 = getIndex(graph, linked[i].vertex2);

ArcType weight = linked[i].weight;

graph->arcs[ver1][ver2] = weight;

graph->arcs[ver2][ver1] = weight;

}

void printMatrix(AMGraph *graph){

printf("\t");

for (int i=0;i<graph->vernum;i++){

printf("%c\t", graph->vertex[i]);

}

printf("\n");

for (int i=0;i<graph->vernum;i++){

printf("%c\t", graph->vertex[i]);

for (int j=0;j<graph->vernum;j++){

printf("%d\t", graph->arcs[i][j]);

}

printf("\n");

}

</div></code></pre>

对上面网的测试

<pre class='hljs'><code><div>//

// Created by 20281 on 2023/6/11.

//

#include "AdjacencyMatrix.h"

int main(){

// 创建img8中的网

Linked linkeds[6] = {

{'A', 'B', 4},

{'A', 'D', 6},

{'B', 'C', 3},

{'B', 'F', 10},

{'C', 'E', 7},

{'D', 'E', 11},

};

VertexType vertexes[6] = {'A', 'B', 'C', 'D', 'E', 'F'};

AMGraph amGraph;

create(6, 6, &amGraph, vertexes, linkeds);

// 打印

printMatrix(&amGraph);

return 0;

}

</div></code></pre>

输出结果

<pre class='hljs'><code><div> A B C D E F

A 0 4 0 6 0 0

B 4 0 3 0 0 10

C 0 3 0 0 7 0

D 6 0 0 0 11 0

E 0 0 7 11 0 0

F 0 10 0 0 0 0

</div></code></pre>

<h2 id="%E9%82%BB%E6%8E%A5%E8%A1%A8%E5%AD%98%E5%82%A8%E6%B3%95" tabindex="-1">邻接表存储法</h2>

<ul>

<li>由顶点构成的结点组成的一维数组</li>

<li>用线性链表存储关联同一顶点的边（或者以顶点为尾的弧）</li>

</ul>

直观展示无向图的邻接表存储法，空间复杂度O(n+2e)，其中n是顶点数，e是边数，下同

直观展示有向图的出度邻接表存储法，空间复杂度O(n+e)

<pre class='hljs'><code><div>typedef char VertexType; // 顶点类型

typedef int ArcType; // 边的权值的类型

#define MAXSIZE 10 // 最大顶点数目

// 被链接的顶点结构

typedef struct ArcNode{

// 当前顶点的索引

int index;

// 被链接的顶点的所在的顶点结构

struct ArcNode *next;

// 权值

ArcType weight;

}ArcNode ;

// 顶点集内的每个结点

typedef struct{

// 顶点数据

VertexType vert;

// 指向的第一个与之链接的顶点

ArcNode *firstArc;

} VNode, AdjList[MAXSIZE];

// 网的表示

typedef struct {

// 顶点集组成的一维数组 AdjList vertexes 相当于 VNode vnode[MAXSIZE]

AdjList vertexes;

int vernum, arcnum;

}ALGraph;

</div></code></pre>

<h2 id="%E5%AE%9E%E7%8E%B0%E9%82%BB%E6%8E%A5%E8%A1%A8%E7%9A%84%E8%A1%A8%E7%A4%BA" tabindex="-1">实现邻接表的表示</h2>

<ul>

<li>确定顶点数和边数</li>

<li>建立顶点表并初始化指针域为NULL</li>

<li>创建邻接表</li>

</ul>

<h2 id="%E9%82%BB%E6%8E%A5%E8%A1%A8%E8%A1%A8%E7%A4%BA%E6%B3%95%E7%9A%84%E4%BC%98%E7%BC%BA%E7%82%B9" tabindex="-1">邻接表表示法的优缺点</h2>

<ul>

<li>对稀疏图来说节约空间</li>

<li>对于无向图来说，每个顶点对应的链表结点数，就是该顶点的就、度</li>

</ul>

<ul>

<li>对于有向图需要构造出度表和入度表来计算顶点的度</li>

<li>不方便检查任意一对点是否关联</li>

</ul>

<h3 id="%E7%BB%8F%E8%BF%87%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5%E4%B8%8E%E9%82%BB%E6%8E%A5%E8%A1%A8%E7%9A%84%E5%AF%B9%E6%AF%94%EF%BC%8C%E7%A8%80%E7%96%8F%E5%9B%BE%EF%BC%88%E7%BD%91%EF%BC%89%E4%B8%80%E8%88%AC%E4%BD%BF%E7%94%A8%E9%82%BB%E6%8E%A5%E9%93%BE%E8%A1%A8%EF%BC%8C%E7%A8%A0%E5%AF%86%E5%9B%BE%EF%BC%88%E7%BD%91%EF%BC%89%E4%B8%80%E8%88%AC%E4%BD%BF%E7%94%A8%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5" tabindex="-1">经过邻接矩阵与邻接表的对比，稀疏图（网）一般使用邻接链表，稠密图（网）一般使用邻接矩阵</h3>

<h2 id="%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0%E9%82%BB%E6%8E%A5%E9%93%BE%E8%A1%A8%E7%9A%84%E6%93%8D%E4%BD%9C" tabindex="-1">代码实现邻接链表的操作</h2>

<pre class='hljs'><code><div>// 用于表示存在关联的两个顶点以权值

typedef struct {

VertexType vertex1;

VertexType vertex2;

ArcType weight;

} Linked2;

// 辅助函数，用于获取顶点在顶点集的索引

int getIndex2(ALGraph *graph, VertexType name);

// 初始化

// 传入参数依次是网本身、顶点个数、边数、顶点集、关联集

// 方法一是改变指针位置来更新链接更新

void createALG1(ALGraph *graph, int _vernum, int _arcnum, VertexType vertexes[_vernum], Linked2 linked[_arcnum]);

// 方法二是在链表尾部不断追加来更新链接更新

// 简单来说，createALG1 是将新节点直接插入链表的开头，而 createALG2 是将新节点插入链表的末尾。

void createALG2(ALGraph *graph, int _vernum, int _arcnum, VertexType vertexes[_vernum], Linked2 linked[_arcnum]);

// 直观的打印出邻接链表

void printLinkedList(ALGraph *graph);

// 释放链表

void freeLinkedList(ALGraph * graph);

</div></code></pre>

<pre class='hljs'><code><div>//

// Created by 20281 on 2023/6/12.

//

#include "AdjacentLinkedList.h"

#include "stdio.h"

#include "stdlib.h"

int getIndex2(ALGraph *graph, VertexType name){

for (int i=0;i<graph->vernum;i++){

if (graph->vertexes[i].vert == name){

return i;

} else continue;

}

return -1;

}

graph->arcnum = _arcnum;

graph->vernum = _vernum;

for (int i=0;i<_vernum;i++){

graph->vertexes[i].vert = vertexes[i];

graph->vertexes[i].firstArc = NULL;

}

for (int i=0;i<_arcnum;i++){

int index1 = getIndex2(graph, linked[i].vertex1);

int index2 = getIndex2(graph, linked[i].vertex2);

int weight = linked[i].weight;

ArcNode * newNode = (ArcNode* ) malloc(sizeof(ArcNode));

newNode->index = index2;

newNode->weight = weight;

newNode->next = graph->vertexes[index1].firstArc;

graph->vertexes[index1].firstArc = newNode;

ArcNode * newNode2 = (ArcNode* ) malloc(sizeof(ArcNode));

newNode2->index = index1;

newNode2->weight = weight;

newNode2->next = graph->vertexes[index2].firstArc;

graph->vertexes[index2].firstArc = newNode2;

View remainder of file in raw view

FilesExpand file tree

regraph.html

Latest commit

History

regraph.html

File metadata and controls