search
HomeJavajavaTutorialGraphs and Applications

Many real-world problems can be solved using graph algorithms. Graphs are useful in modeling and solving real-world problems. For example, the problem to find the least number of flights between two cities can be modeled using a graph, where the vertices represent cities and the edges represent the flights between two adjacent cities, as shown in Figure below. The problem of finding the minimal number of connecting flights
between two cities is reduced to finding a shortest path between two vertices in a graph.

Graphs and Applications

The study of graph problems is known as graph theory. Graph theory was founded by Leonhard Euler in 1736, when he introduced graph terminology to solve the famous Seven Bridges of Königsberg problem. The city of Königsberg, Prussia (now Kaliningrad, Russia), was divided by the Pregel River. There were two islands on the river. The city and islands were connected by seven bridges, as shown in Figure below (a). The question is, can one take a walk, cross each bridge exactly once, and return to the starting point? Euler proved that it is not possible.

Graphs and Applications

To establish a proof, Euler first abstracted the Königsberg city map by eliminating all streets, producing the sketch shown in Figure above (a). Next, he replaced each land mass with a dot, called a vertex or a node, and each bridge with a line, called an edge, as shown in Figure above (b). This structure with vertices and edges is called a graph.

Looking at the graph, we ask whether there is a path starting from any vertex, traversing all edges exactly once, and returning to the starting vertex. Euler proved that for such a path to exist, each vertex must have an even number of edges. Therefore, the Seven Bridges of Königsberg problem has no solution.

Graph problems are often solved using algorithms. Graph algorithms have many applications in various areas, such as in computer science, mathematics, biology, engineering, economics, genetics, and social sciences.

Basic Graph Terminologies

A graph consists of vertices, and edges that connect the vertices. This chapter does not assume that you have any prior knowledge of graph theory or discrete mathematics. We use plain and simple terms to define graphs.

Graphs and Applications

What is a graph? A graph is a mathematical structure that represents relationships among entities in the real world. For example, the graph in Figure above represents the flights among cities, and the graph in Figure below (b) represents the bridges among land masses.

Graphs and Applications

A graph consists of a nonempty set of vertices (also known as nodes or points), and a set of edges that connect the vertices. For convenience, we define a graph as G = (V, E), where V represents a set of vertices and E represents a set of edges. For example, V and E for the graph in Figure below are as follows:

Graphs and Applications

V = {"Seattle", "San Francisco", "Los Angeles",
"Denver", "Kansas City", "Chicago", "Boston", "New York",
"Atlanta", "Miami", "Dallas", "Houston"};

E = {{"Seattle", "San Francisco"},{"Seattle", "Chicago"},
{"Seattle", "Denver"}, {"San Francisco", "Denver"},
...
};

A graph may be directed or undirected. In a directed graph, each edge has a direction, which indicates that you can move from one vertex to the other through the edge. You can model parent/child relationships using a directed graph, where an edge from vertex A to B indicates that A is a parent of B. Figure below (a) shows a directed graph.

Graphs and Applications

In an undirected graph, you can move in both directions between vertices. The graph in Figure below is undirected.

Graphs and Applications

Edges may be weighted or unweighted. For example, you can assign a weight for each edge in the graph in Figure above to indicate the flight time between the two cities.

Two vertices in a graph are said to be adjacent if they are connected by the same edge. Similarly, two edges are said to be adjacent if they are connected to the same vertex. An edge in a graph that joins two vertices is said to be incident to both vertices. The degree of a vertex is the number of edges incident to it.

Two vertices are called neighbors if they are adjacent. Similarly, two edges are called neighbors if they are adjacent.

A loop is an edge that links a vertex to itself. If two vertices are connected by two or more edges, these edges are called parallel edges. A simple graph is one that has doesn’t have any loops or parallel edges. In a complete graph, every two pairs of vertices are connected, as shown in Figure below (b).

Graphs and Applications

A graph is connected if there exists a path between any two vertices in the graph. A subgraph of a graph G is a graph whose vertex set is a subset of that of G and whose edge set is a subset of that of G. For example, the graph in Figure above (c) is a subgraph of the graph in Figure above (b).

Assume that the graph is connected and undirected. A cycle is a closed path that starts from a vertex and ends at the same vertex. A connected graph is a tree if it does not have cycles. A spanning tree of a graph G is a connected subgraph of G and the subgraph is a tree that contains all vertices in G.

The above is the detailed content of Graphs and Applications. For more information, please follow other related articles on the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
JVM performance vs other languagesJVM performance vs other languagesMay 14, 2025 am 12:16 AM

JVM'sperformanceiscompetitivewithotherruntimes,offeringabalanceofspeed,safety,andproductivity.1)JVMusesJITcompilationfordynamicoptimizations.2)C offersnativeperformancebutlacksJVM'ssafetyfeatures.3)Pythonisslowerbuteasiertouse.4)JavaScript'sJITisles

Java Platform Independence: Examples of useJava Platform Independence: Examples of useMay 14, 2025 am 12:14 AM

JavaachievesplatformindependencethroughtheJavaVirtualMachine(JVM),allowingcodetorunonanyplatformwithaJVM.1)Codeiscompiledintobytecode,notmachine-specificcode.2)BytecodeisinterpretedbytheJVM,enablingcross-platformexecution.3)Developersshouldtestacross

JVM Architecture: A Deep Dive into the Java Virtual MachineJVM Architecture: A Deep Dive into the Java Virtual MachineMay 14, 2025 am 12:12 AM

TheJVMisanabstractcomputingmachinecrucialforrunningJavaprogramsduetoitsplatform-independentarchitecture.Itincludes:1)ClassLoaderforloadingclasses,2)RuntimeDataAreafordatastorage,3)ExecutionEnginewithInterpreter,JITCompiler,andGarbageCollectorforbytec

JVM: Is JVM related to the OS?JVM: Is JVM related to the OS?May 14, 2025 am 12:11 AM

JVMhasacloserelationshipwiththeOSasittranslatesJavabytecodeintomachine-specificinstructions,managesmemory,andhandlesgarbagecollection.ThisrelationshipallowsJavatorunonvariousOSenvironments,butitalsopresentschallengeslikedifferentJVMbehaviorsandOS-spe

Java: Write Once, Run Anywhere (WORA) - A Deep Dive into Platform IndependenceJava: Write Once, Run Anywhere (WORA) - A Deep Dive into Platform IndependenceMay 14, 2025 am 12:05 AM

Java implementation "write once, run everywhere" is compiled into bytecode and run on a Java virtual machine (JVM). 1) Write Java code and compile it into bytecode. 2) Bytecode runs on any platform with JVM installed. 3) Use Java native interface (JNI) to handle platform-specific functions. Despite challenges such as JVM consistency and the use of platform-specific libraries, WORA greatly improves development efficiency and deployment flexibility.

Java Platform Independence: Compatibility with different OSJava Platform Independence: Compatibility with different OSMay 13, 2025 am 12:11 AM

JavaachievesplatformindependencethroughtheJavaVirtualMachine(JVM),allowingcodetorunondifferentoperatingsystemswithoutmodification.TheJVMcompilesJavacodeintoplatform-independentbytecode,whichittheninterpretsandexecutesonthespecificOS,abstractingawayOS

What features make java still powerfulWhat features make java still powerfulMay 13, 2025 am 12:05 AM

Javaispowerfulduetoitsplatformindependence,object-orientednature,richstandardlibrary,performancecapabilities,andstrongsecurityfeatures.1)PlatformindependenceallowsapplicationstorunonanydevicesupportingJava.2)Object-orientedprogrammingpromotesmodulara

Top Java Features: A Comprehensive Guide for DevelopersTop Java Features: A Comprehensive Guide for DevelopersMay 13, 2025 am 12:04 AM

The top Java functions include: 1) object-oriented programming, supporting polymorphism, improving code flexibility and maintainability; 2) exception handling mechanism, improving code robustness through try-catch-finally blocks; 3) garbage collection, simplifying memory management; 4) generics, enhancing type safety; 5) ambda expressions and functional programming to make the code more concise and expressive; 6) rich standard libraries, providing optimized data structures and algorithms.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools